Maxmmp problem is hard but admits approximation methods
Maximum Matching-Match: Hardness and Approximation
Data Structures and AlgorithmsComputational Complexity
Summary
This paper looks at a puzzle where you color parts of a network and match colored sticks to its connections to satisfy as many connections as possible. The authors show that even when using only two colors and simple rules, finding the best way to do this is a hard problem. They provide approximation methods that give solutions close to the best one, with better results for simpler types of networks. For certain network types like trees and cographs, they even show ways to find the exact optimal solution efficiently when the number of colors is fixed.
What this means in practice
- •For graph algorithm designers: Use the new hardness results and approximation bounds to understand limits and possibilities when optimizing matchings with color constraints in graphs.
- •For network optimization teams: Apply approximation strategies from the paper to handle optimization problems involving assignment of colored resources on networks under constraints.
A theory result. No direct application yet.
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.