arxiv: 2604.21025 · v1 · submitted 2026-04-22 · 💻 cs.DM

Recognition: unknown

A Complexity Dichotomy for Generalized Rainbow Matchings Based on Color Classes

Felix Hommelsheim, Moritz M\"uhlenthaler, Pia Jehmlich

Authors on Pith no claims yet

Pith reviewed 2026-05-09 22:23 UTC · model grok-4.3

classification 💻 cs.DM

keywords rainbow matchingcomplexity dichotomycomplete multipartite graphsNP-hardnesscolor-closed graph classesedge-colored graphsmaximum matching

0 comments

The pith

Maximum Rainbow Matching is polynomial-time solvable when almost every color class is a complete multipartite graph, and NP-hard otherwise.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a complexity dichotomy for Maximum Rainbow Matching in edge-colored graphs based on the structure of the color classes. It proves that the problem admits a polynomial-time algorithm if nearly every color class forms a complete multipartite graph, but is NP-hard in all other cases. This classification matters because it identifies precisely when one can efficiently find a largest possible matching that uses each color at most once. Hardness is first shown for color classes limited to three small graphs on four vertices, then extended to all non-complete-multipartite graphs through color-closed classes; the tractable side reduces the problem to maximum (l,u)-matchings.

Core claim

We provide the following complexity dichotomy for this problem based on the structure of the color classes: Maximum Rainbow Matching admits a polynomial-time algorithm if almost every color class is a complete multipartite graph and it is NP-hard otherwise. To prove the NP-hardness-part of the dichotomy, we first show that the problem remains NP-hard even if every color class is a subgraph on four vertices that is either a matching of size two, a path on four vertices or a paw. We then leverage this result to all color classes that are not complete multipartite graphs. For this purpose, we introduce color-closed graph classes, which seem to be an appropriate notion for obtaining complexity 1

What carries the argument

Color-closed graph classes that propagate hardness from three specific four-vertex graphs to all non-complete-multipartite color classes, paired with a reduction to maximum (l,u)-matching when almost all color classes are complete multipartite.

Load-bearing premise

That hardness for the three small forbidden color-class graphs extends to every non-complete-multipartite class via the color-closed property without further restrictions.

What would settle it

A polynomial-time algorithm for the problem on an instance where at least one color class is a non-complete-multipartite graph such as a triangle, or a reduction proving NP-hardness when all color classes are complete multipartite graphs.

Figures

Figures reproduced from arXiv: 2604.21025 by Felix Hommelsheim, Moritz M\"uhlenthaler, Pia Jehmlich.

**Figure 2.** Figure 2: Three graphs on four vertices. problem, where we are allowed to pick at most mi edges from color class i. We reduce this problem to the Maximum (l, u)-Matching problem, which admits a polynomial-time algorithm [34] and is defined as follows: Given a graph G = (V, E) and two functions l, u : V → N such that l(v) ≤ u(v) for all v ∈ V , the problem Maximum (l, u)-Matching asks for an edge set X ⊆ E of maximum… view at source ↗

**Figure 3.** Figure 3: Variable and clause gadgets of the graph [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

**Figure 4.** Figure 4: The i-th positive and negative matching for a variable gadget Xi of the graph Gϕ, fϕ constructed in Lemma 5. and {rj,3, r′ j,3 }. But then the vertices rj,2 and r ′ j,2 are not matched, so the matching is not maximum. Recall that these three edges correspond to the three literals of the clause Cj . We now define matchings that correspond to the values True and False of the variables xi . For each variable… view at source ↗

**Figure 5.** Figure 5: Illustration of the graph G′ ϕ . 3.1.2 Each color class is a path on four vertices We adapt the reduction from Section 3.1.1 in order to show the following. Lemma 6. Rainbow Matching is NP-hard on edge-colored graphs, where each color class is a P4. To prove Lemma 6, we first construct from a 3-occurrence 3SAT formula ϕ the graph Gϕ, fϕ as described in Section 3.1.1. Recall that any color class of Gϕ, fϕ i… view at source ↗

**Figure 6.** Figure 6: Illustration of the two steps in the construction of the graph [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗

**Figure 7.** Figure 7: Example of the construction used in the reduction of Theorem 4. [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗

read the original abstract

Given an edge-colored graph, the Maximum Rainbow Matching problem asks for a maximum-cardinality matching of the graph that contains at most one edge from each color. We provide the following complexity dichotomy for this problem based on the structure of the color classes: Maximum Rainbow Matching admits a polynomial-time algorithm if almost every color class is a complete multipartite graph and it is NP-hard otherwise. To prove the NP-hardness-part of the dichotomy, we first show that the problem remains NP-hard even if every color class is a subgraph on four vertices that is either a matching of size two, a path on four vertices or a paw. We then leverage this result to all color classes that are not complete multipartite graphs. For this purpose, we introduce color-closed graph classes, which seem to be an appropriate notion for obtaining complexity classifications for rainbow problems and may be of independent interest. To prove the positive part of the dichotomy, we show that the problem essentially reduces to computing a maximum $(l, u)$-matching, where we heavily exploit that almost all color classes are complete multipartite graphs. In the case where all color classes are complete multipartite, we provide a polynomial-time algorithm that computes a maximum matching containing at most $m_i$ edges from each color class $i$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a clean dichotomy for rainbow matching hardness based on color class structure, with a new lifting tool that looks workable.

read the letter

The main claim is that maximum rainbow matching is polynomial-time solvable when almost every color class is a complete multipartite graph and NP-hard in all other cases. They prove the hard side first for three small 4-vertex color classes (double edge, P4, paw) and then extend via color-closed graph classes. The easy side reduces to (l,u)-matching and gives an explicit algorithm when every class is complete multipartite. The color-closed notion is presented as potentially reusable for other rainbow problems. The positive reduction exploits the multipartite structure to bound choices per color without introducing free parameters, which is a straightforward and effective move. The base hardness cases are small and rest on standard reductions from known matching problems. The citation pattern draws on established matching algorithms rather than self-referential claims. The soft spot is the extension step. The color-closed closure must preserve both the non-multipartite property and the NP-hardness without creating auxiliary structures that could be solved by the same (l,u)-matching technique used on the positive side. The abstract sketches how they do this, but the details of how the closure composes with the reductions determine whether the dichotomy is fully tight. If those steps hold without leaks, the result stands; otherwise the boundary cases need extra checking. This is useful for anyone working on edge-colored matching variants or complexity classifications in discrete math. A reader who needs to decide between algorithmic and hardness approaches for rainbow constraints would get direct guidance. The work shows clear thinking on how to organize the problem space. Send it to peer review. The dichotomy is sharp enough and the techniques are grounded enough to justify referee time.

Referee Report

1 major / 2 minor

Summary. The manuscript presents a complexity dichotomy for the Maximum Rainbow Matching problem in edge-colored graphs. The central claim is that the problem is polynomial-time solvable when almost every color class is a complete multipartite graph, and NP-hard otherwise. Hardness is first shown for the case where every color class is one of three specific 4-vertex graphs (matching of size two, P4, or paw), then extended to arbitrary non-complete-multipartite color classes using the new notion of color-closed graph classes. The positive direction reduces the problem to computing a maximum (l, u)-matching and gives an explicit polynomial-time algorithm when all color classes are complete multipartite.

Significance. If correct, the dichotomy provides a clean structural classification for the tractability of rainbow matching, a natural generalization of matching problems. The reduction to (l, u)-matching and the explicit algorithm for the complete-multipartite case are strengths. The introduction of color-closed graph classes is a potentially reusable tool for complexity results on rainbow or colored-graph problems and is credited as such.

major comments (1)

[Section introducing and applying color-closed graph classes] The extension step (following the hardness result for the three 4-vertex color classes): the argument that color-closed classes lift the NP-hardness to every non-complete-multipartite color class must explicitly verify that the closure operation does not introduce auxiliary colors or structures to which the (l, u)-matching reduction from the positive side could be applied, thereby creating a loophole. A concrete reduction or invariant showing that hardness is preserved under closure without violating the non-multipartite condition is required.

minor comments (2)

[Abstract and Introduction] The phrase 'almost every color class' in the dichotomy statement should be given a precise formal definition (e.g., all but a constant number, or all but o(n)) already in the introduction or abstract.
[Positive-result section] Notation for the (l, u)-matching parameters and the precise bound on the number of non-multipartite classes should be introduced consistently before the algorithmic section.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful and constructive review. The single major comment identifies a point where the argument for lifting hardness via color-closed classes can be made more explicit, and we will strengthen the manuscript accordingly.

read point-by-point responses

Referee: [Section introducing and applying color-closed graph classes] The extension step (following the hardness result for the three 4-vertex color classes): the argument that color-closed classes lift the NP-hardness to every non-complete-multipartite color class must explicitly verify that the closure operation does not introduce auxiliary colors or structures to which the (l, u)-matching reduction from the positive side could be applied, thereby creating a loophole. A concrete reduction or invariant showing that hardness is preserved under closure without violating the non-multipartite condition is required.

Authors: We agree that an explicit invariant is needed to rule out any interaction with the positive-side reduction. In the revised version we will insert a new lemma immediately after the definition of color-closed classes. The lemma states that if C is the color-closed class generated by a non-complete-multipartite graph H, then every member of C contains at least one color class that is not complete multipartite, and moreover the closure operation never produces an instance in which all but a bounded number of color classes become complete multipartite. The proof proceeds by observing that the only auxiliary colors added by the closure are subgraphs of the original non-multipartite color classes (matchings of size two, P4s, or paws) or disjoint unions thereof; none of these auxiliary colors are complete multipartite, so the resulting instance always retains a positive number of non-multipartite color classes. Consequently the (l,u)-matching algorithm, which requires that almost every color class be complete multipartite, cannot be invoked. We also verify that the concrete hardness reduction from the three 4-vertex graphs stays inside this invariant. This addition closes the potential loophole while leaving the rest of the proof unchanged. revision: yes

Circularity Check

0 steps flagged

No circularity in the dichotomy derivation chain

full rationale

The paper first proves NP-hardness directly for the three base 4-vertex color classes (matching of size 2, P4, paw) via explicit reductions. It then defines color-closed classes as a technical device to lift the hardness result to arbitrary non-complete-multipartite color classes while preserving the relevant structural restrictions. The algorithmic direction reduces the problem to maximum (l,u)-matching by exploiting the complete-multipartite structure of almost all color classes, using standard matching algorithms. No step equates a claimed prediction or theorem to its own inputs by construction, no parameters are fitted and then renamed as predictions, and no load-bearing premise rests on a self-citation chain. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on standard graph-theoretic assumptions plus the newly introduced color-closed classes. No numerical free parameters are present. The color-closed notion is an invented definitional tool rather than a physical entity.

axioms (1)

standard math Standard definitions and properties of matchings, edge colorings, complete multipartite graphs, and NP-hardness reductions hold.
Invoked throughout the hardness and algorithmic arguments as background.

invented entities (1)

color-closed graph classes no independent evidence
purpose: To extend the NP-hardness result from three specific small graphs to all non-complete-multipartite color classes.
Introduced in the paper as a technical device for the classification; no independent evidence outside the paper is provided.

pith-pipeline@v0.9.0 · 5533 in / 1240 out tokens · 27584 ms · 2026-05-09T22:23:15.085411+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

37 extracted references

[1]

Rainbow matchings inr-partiter-graphs.Electronic Journal of Combinatorics, 16(1), 2009

Ron Aharoni and Eli Berger. Rainbow matchings inr-partiter-graphs.Electronic Journal of Combinatorics, 16(1), 2009

2009
[2]

Howard, and Paul D

Ron Aharoni, Eli Berger, Maria Chudnovsky, David M. Howard, and Paul D. Seymour. Large rainbow matchings in general graphs.European Journal of Combinatorics, 79:222–227, 2019

2019
[3]

On a generalization of the Ryser-Brualdi-Stein conjecture.Journal of Graph Theory, 78(2):143–156, 2015

Ron Aharoni, Pierre Charbit, and David Howard. On a generalization of the Ryser-Brualdi-Stein conjecture.Journal of Graph Theory, 78(2):143–156, 2015

2015
[4]

Color-coding.Journal of the ACM, 42(4):844–856, 1995

Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding.Journal of the ACM, 42(4):844–856, 1995

1995
[5]

More on the rainbow disconnection in graphs.Discuss

Xuqing Bai, Renying Chang, Zhong Huang, and Xueliang Li. More on the rainbow disconnection in graphs.Discuss. Math. Graph Theory, 42(4):1185–1204, 2022

2022
[6]

Fomin, Petr A

Aritra Banik, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Satyabrata Jana, and Saket Saurabh. Cuts in graphs with matroid constraints. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors,32nd Annual European Symposium on Algorithms, ESA 2024, September 2-4, 2024, Royal Holloway, London, United Kingdom, volume 308 ofLIPIcs...

2024
[7]

S´ ark¨ ozy

J´ anos Bar´ at, Andr´ as Gy´ arf´ as, and G´ abor N. S´ ark¨ ozy. Rainbow matchings in bipartite multigraphs. Periodica Mathematica Hungarica, 74(1):108–111, 2017

2017
[8]

Spanning trees with many or few colors in edge-colored graphs

Hajo Broersma and Xueliang Li. Spanning trees with many or few colors in edge-colored graphs. Discussiones mathematicae. Graph theory, 17(2):259–269, 1997. 14

1997
[9]

Springer, 1991

Richard A Brualdi, Herbert John Ryser, et al.Combinatorial matrix theory, volume 39. Springer, 1991

1991
[10]

On the complexity of rainbow spanning forest problem.Optimization Letters, 12(3):443–454, 2018

Francesco Carrabs, Carmine Cerrone, Raffaele Cerulli, and Selene Silvestri. On the complexity of rainbow spanning forest problem.Optimization Letters, 12(3):443–454, 2018

2018
[11]

The complexity of determining the rainbow vertex- connection of a graph.Theoretical Computer Science, 412(35):4531–4535, 2011

Lily Chen, Xueliang Li, and Yongtang Shi. The complexity of determining the rainbow vertex- connection of a graph.Theoretical Computer Science, 412(35):4531–4535, 2011

2011
[12]

An improved bound on the sizes of matchings guaranteeing a rainbow matching.The Electronic Journal of Combinatorics, 23(2):2, 2016

Dennis Clemens and Julia Ehrenm¨ uller. An improved bound on the sizes of matchings guaranteeing a rainbow matching.The Electronic Journal of Combinatorics, 23(2):2, 2016

2016
[13]

Short proofs of rainbow matchings results.International Mathematics Research Notices, 2023(14):12441–12476, 2023

David Munh Correia, Alexey Pokrovskiy, and Benny Sudakov. Short proofs of rainbow matchings results.International Mathematics Research Notices, 2023(14):12441–12476, 2023

2023
[14]

Solving the maximum popular matching problem with matroid constraints.SIAM Journal on Discrete Mathematics, 38(3):2226–2242, 2024

Gergely K´ al Cs´ aji, Tam´ as Kir´ aly, and Yu Yokoi. Solving the maximum popular matching problem with matroid constraints.SIAM Journal on Discrete Mathematics, 38(3):2226–2242, 2024

2024
[15]

Maximizing a submodu- lar set function subject to a matroid constraint (extended abstract)

Gruia Cualinescu, Chandra Chekuri, Martin P´ al, and Jan Vondr´ ak. Maximizing a submodu- lar set function subject to a matroid constraint (extended abstract). In Matteo Fischetti and David P. Williamson, editors,Integer Programming and Combinatorial Optimization, 12th Interna- tional IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings, volume...

2007
[16]

Arthur A. Drisko. Transversals in row-latin rectangles.Journal of Combinatorial Theory, Series A, 84(2):181–195, 1998

1998
[17]

A tight combinatorial algorithm for submodular maximization subject to a matroid constraint

Yuval Filmus and Justin Ward. A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. In53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 659–668. IEEE Com- puter Society, 2012

2012
[18]

Harold N. Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors,Proceedings of the 15th Annual ACM Symposium...

1983
[19]

How many colors guarantee a rainbow matching? The Electronic Journal of Combinatorics, 21(1):1, 2014

Roman Glebov, Benny Sudakov, and Tibor Szab´ o. How many colors guarantee a rainbow matching? The Electronic Journal of Combinatorics, 21(1):1, 2014

2014
[20]

Mouawad, Vijayaragunathan Ramamoor- thi, Daniel Schmand, and Sebastian Siebertz

Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoor- thi, Daniel Schmand, and Sebastian Siebertz. Solution discovery via reconfiguration for problems in P. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors,51st Inter- national Colloquium on Automata, Languages, and Programming, ICALP 2024, July...

2024
[21]

Parameterized algorithms and kernels for rainbow matching.Algorithmica, 81(4):1684–1698, 2019

Sushmita Gupta, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. Parameterized algorithms and kernels for rainbow matching.Algorithmica, 81(4):1684–1698, 2019

2019
[22]

Quadratic vertex kernel for rainbow matching.Algorithmica, 82(4):881–897, 2020

Sushmita Gupta, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. Quadratic vertex kernel for rainbow matching.Algorithmica, 82(4):881–897, 2020

2020
[23]

Approximation schemes for the restricted shortest path problem.Mathematics of Operations research, 17(1):36–42, 1992

Refael Hassin. Approximation schemes for the restricted shortest path problem.Mathematics of Operations research, 17(1):36–42, 1992

1992
[24]

Pooya Hatami and Peter W. Shor. A lower bound for the length of a partial transversal in a latin square.Journal of Combinatorial Theory, Series A, 115(7):1103–1113, 2008. 15

2008
[25]

Cor A. J. Hurkens and Alexander Schrijver. On the size of systems of sets every t of which have an sdr, with an application to the worst-case ratio of heuristics for packing problems.SIAM J. Discret. Math., 2(1):68–72, 1989

1989
[26]

Matching problems with delta-matroid constraints

Naonori Kakimura and Mizuyo Takamatsu. Matching problems with delta-matroid constraints. SIAM Journal on Discrete Mathematics, 28(2):942–961, 2014

2014
[27]

The popular matching and condensation problems under matroid constraints

Naoyuki Kamiyama. The popular matching and condensation problems under matroid constraints. Journal of Combinatorial Optimization, 32(4):1305–1326, 2016

2016
[28]

Popular matchings with ties and matroid constraints.SIAM Journal on Discrete Mathematics, 31(3):1801–1819, 2017

Naoyuki Kamiyama. Popular matchings with ties and matroid constraints.SIAM Journal on Discrete Mathematics, 31(3):1801–1819, 2017

2017
[29]

On stable matchings with pairwise preferences and matroid constraints

Naoyuki Kamiyama. On stable matchings with pairwise preferences and matroid constraints. In Amal El Fallah Seghrouchni, Gita Sukthankar, Bo An, and Neil Yorke-Smith, editors,Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, Auckland, New Zealand, May 9-13, 2020, pages 584–592. International Foundation...

2020
[30]

Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey.Graphs Comb., 24(4):237–263, 2008

Mikio Kano and Xueliang Li. Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey.Graphs Comb., 24(4):237–263, 2008

2008
[31]

Large matchings in bipartite graphs have a rainbow matching.European Journal of Combinatorics, 38:97–101, 2014

Daniel Kotlar and Ran Ziv. Large matchings in bipartite graphs have a rainbow matching.European Journal of Combinatorics, 38:97–101, 2014

2014
[32]

Complexity results for rainbow matchings.Theoretical Computer Science, 524:27–33, 2014

Van Bang Le and Florian Pfender. Complexity results for rainbow matchings.Theoretical Computer Science, 524:27–33, 2014

2014
[33]

Restricted t-Matchings via Half-Edges

Katarzyna Paluch and Mateusz Wasylkiewicz. Restricted t-Matchings via Half-Edges. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors,29th Annual European Symposium on Al- gorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 73:1–73:17. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2021

2021
[34]

Springer Berlin, Heidelberg, 1 edition, 2003

Alexander Schrijver.Combinatorial Optimization: Polyhedra and Efficiency, volume 24 ofAlgo- rithms and Combinatorics. Springer Berlin, Heidelberg, 1 edition, 2003

2003
[35]

Another look at the degree constrained subgraph problem.Information Processing Letters, 12(2):89–92, 1981

Yossi Shiloach. Another look at the degree constrained subgraph problem.Information Processing Letters, 12(2):89–92, 1981

1981
[36]

Transversals of latin squares and their generalizations.Pacific Journal of Math- ematics, 59(2):567–575, 1975

Sherman K Stein. Transversals of latin squares and their generalizations.Pacific Journal of Math- ematics, 59(2):567–575, 1975

1975
[37]

On the rainbow connec- tivity of graphs: Complexity and FPT algorithms.Algorithmica, 67(2):161–179, 2013

Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, and Xiao Zhou. On the rainbow connec- tivity of graphs: Complexity and FPT algorithms.Algorithmica, 67(2):161–179, 2013. 16

2013