Metraipolis › archive › dc_862a9aa2cf53

Maximum Matching-Match: Hardness and Approximation — arXiv:2609.07193

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.07193
License (as archived)
CC0-1.0
Archived
2026-10-16T15:31:50.103Z
SHA-256 of the archived text
6666f93fa7c8b7441a6ac60d5df79cc9e65bcb4cdf465a43122adfad68286a58
Stable URL of this page
https://metraipolis.com/documento/dc_862a9aa2cf53

How to cite

Maximum Matching-Match: Hardness and Approximation — arXiv:2609.07193 — arXiv (en), https://arxiv.org/abs/2609.07193 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_862a9aa2cf53 (Metraipolis archive dc_862a9aa2cf53, sha256 6666f93fa7c8b7441a6ac60d5df79cc9e65bcb4cdf465a43122adfad68286a58)
BibTeX
@misc{dc862a9aa2cf53,
  title = {Maximum Matching-Match: Hardness and Approximation — arXiv:2609.07193},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.07193},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_862a9aa2cf53; sha256 6666f93fa7c8b7441a6ac60d5df79cc9e65bcb4cdf465a43122adfad68286a58},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07193. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.07193 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T15:15:08.342Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).