Graph coloring puzzle shown hard but approximate solutions developed
Maximum Matching-Match: Hardness and Approximation
Data Structures and AlgorithmsComputational Complexity
Summary
This paper looks at a puzzle involving coloring parts of a network and matching colored sticks to connections to make as many matches as possible. The researchers proved that figuring out the best solution is very hard, even in simple cases. They then created several ways to find approximate solutions that get close to the best answer, including some that work better on certain types of networks. For some special network shapes, their methods can even find the exact answer efficiently. These results help us understand the complexity of this coloring and matching problem and how to handle it in practice.
graphvertex coloringmatchingapproximation algorithmAPX-hardnessMax-Cut problemsubmodular maximizationpartition matroidbipartite graphcographs
Authors
Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
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.