REVIEW
Maximum Matching-Match: Hardness and Approximation
Data Structures and Algorithms · Submitted 7 Sep 2026 · 6 references
Pith's verdict: A clean, correct paper on a specialized optimization puzzle: APX-hardness by a direct Max-Cut reduction plus sound approximation and exact DP results, worth refereeing and accepting after minor fixes.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
MaxMMP is APX-hard via Max-Cut reduction, admits randomized (1−1/e)/(2c)-approxmation for general graphs, and deterministic 1/(2c)-approxmation for fixed c, with exact algorithms on trees and cographs.
The reading
What carries the argument
Hardness is established via an L-reduction from Max-Cut with α=β=1, directly equating cut size to satisfied edges. For approximtion, the randomized algorithm reduces the second-stage coloring choice to a monotone submodular function maximi zation under a partition matroid, enabling the (1−1/e) guarantee. For fixed c, the deterministic algorithms use dynamic programming over a state space of size O($m^{{O(c^2)}}$) to optimally color uncrossed vertices once one side is fixed.
Extended reading notes
Core claim
The central discovery is that MaxMMP is APX-hard, which rules out a polynomial-time approximmation scheme (PTAS) unless P=NP. Moreover, the authors show that the problem admits approximtions with ratio Θ(1/c) through submodular maximzation techniques, and for fixed c, improved deterministic approxmations and exact solutions on structured graph classes are attainable. This provides a comprehensive picture of the problem's computational tractability.
Load-bearing premise
The APX-hardness proof relies on the known fact that Max-Cut is APX-complete on cubic graphs; if this result were incorrect, the hardness argument would collapse.
Editorial extensions
If this is right
- MaxMMP admits no PTAS unless P=NP, even in the simplest case of two colors and only bichromatic sticks.
- The Θ(1/c) approximtion ratio establishes a baseline; further improvements would require new techniques that go beyond the submodularity framework.
- The exact algorithms on trees and cographs immediately solve the feasibility problem FMMP on these classes in the same n^{O(c^2)} time.
- For small fixed c, the n^{O(c^2)} algorithms are plausibly practical for moderate-sized instances.
- The submodular framework may apply to other variants of colored motif realization and inverse network motif problems.
Reading between the lines
- If the hardness can be strengthened to show that the problem remains APX-hard when c is part of the input, the existing approximtions would be essentially tight up to constant factors.
- The submodular maximzation approach may extend to other constraints beyond partition matroids, such as laminar or cardinality constraints on vertex colors.
- The dynamic programming on trees hints at potential fixed-parameter tractability or XP algorithms parameterized by c, which the paper does not fully explore.
Original 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 compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | In this paper, we study \textsc{MaxMMP}, an optimization variant of the Matching-Match Puzzle introduced by Iburi and Uehara (FUN 2024). | background 0.53 | 0.55 | 0.03 | asserted 0.95 |
| s1 | 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. | background 0.97 | 0.12 | 0.03 | asserted 0.98 |
| s2 | We first prove that \textsc{MaxMMP} is APX-hard by an reduction from \textsc{Max-Cut}. | result 0.83 | 0.96 | 0.31 | asserted 1.00 |
| s3 | The hardness already holds with two colors, no precolored vertices, and only bichromatic sticks. | result 0.99 | 0.89 | 0.08 | asserted 1.00 |
| s4 | 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. | result 0.86 | 0.96 | 0.12 | asserted 1.00 |
| s5 | 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. | result 0.50 | 0.96 | 0.12 | asserted 1.00 |
| s6 | On bipartite graphs, the approximation ratio improves to $\frac{1-\frac{1}{e}}{c}$. | result 0.99 | 0.95 | 0.07 | asserted 1.00 |
| s7 | 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)}$. | result 0.73 | 0.96 | 0.08 | asserted 1.00 |
| s8 | 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. | result 0.87 | 0.96 | 0.13 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.