arXiv preprint ·
Maximum Matching-Match: Hardness and Approximation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In this paper, we study \textsc{MaxMMP}, an optimization variant of the Matching-Match Puzzle introduced by Iburi and Uehara (FUN 2024). Given a graph, a partial vertex coloring, and a multiset of colored sticks, the goal is to complete the coloring and assign the sticks to graph edges so as to maximize the number of satisfied edges. We first prove that \textsc{MaxMMP} is APX-hard by an reduction from \textsc{Max-Cut}. The hardness already holds with two colors, no precolored vertices, and only bichromatic sticks. We then give a simple deterministic $\frac{2}{c(c+1)}$-approximation for completely uncolored instances, improving to $\frac{2}{c(c-1)}$ when all sticks are bichromatic. Next, we obtain a randomized $\frac{1-\frac{1}{e}}{2c}$-approximation for arbitrary instances with $c$ colors by reducing the remaining coloring choices to monotone submodular maximization under a partition matroid. On bipartite graphs, the approximation ratio improves to $\frac{1-\frac{1}{e}}{c}$. For every fixed $c$, we further obtain deterministic $\frac{1}{2c}$ and $\frac{1}{c}$-approximations on general and bipartite graphs, respectively, in time $n^{O(c^2)}$. Finally, for every fixed number of colors, we show that \textsc{MaxMMP} can be solved exactly in time $n^{O(c^2)}$ on trees and on cographs.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
On the Parameterized Complexity of Coloring Discovery
Algorithms for Finite Group Epimorphism Testing
Subexponential Approximation of the Permanent in Deterministic Polynomial Time
A construction of F-irregular graphs
Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.