pith. machine review for the scientific record. sign in

arxiv: 2604.25556 · v1 · submitted 2026-04-28 · 💻 cs.DS

Recognition: unknown

Grouped Color Deletion, Lasserre Exactness and Clique-Sum Locality for Rainbow Matching

Georgios Stamoulis
Authors on Pith no claims yet

Pith reviewed 2026-05-07 15:10 UTC · model grok-4.3

classification 💻 cs.DS
keywords rainbow matchingLasserre hierarchycolor deletionhereditary graph classesclique sumsaugmented conflict graphdynamic programming
0
0 comments X

The pith

Deleting k colors to reach a uniformly rank-r exact hereditary class makes the Lasserre hierarchy exact at level k+r for the rainbow matching polytope.

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

The paper introduces the deletion parameter kappa_X as the fewest colors to remove so that the residual augmented conflict graph lies in a given hereditary class X. It proves that when X is uniformly rank-r exact, this deletion number k directly controls the Lasserre level needed for exactness, giving level k+1 for perfect graphs and level k+r for h-perfect graphs of bounded odd-hole rank. On the structural side, the color-intersection graph encodes how articulation colors create clique-sum decompositions in the augmented graph, localizing obstructions to individual blocks. This yields a dynamic programming algorithm for computing the deletion number when blocks are small, plus an exact solver for rainbow matching by branching on the deleted colors. A reader cares because the results tie polyhedral exactness and structural decomposition together for a parameterized attack on an otherwise hard matching problem.

Core claim

For a hereditary class X that is uniformly rank-r exact, deleting k colors to place the residual augmented graph in X implies that the Lasserre hierarchy for rainbow matching is exact at level k+r. Separately, when X is clique-sum local, the color-intersection graph Gamma induces clique-sum decompositions in the augmented graph H, so membership in X can be tested blockwise and the deletion parameter can be computed exactly by dynamic programming whenever the blocks of Gamma have bounded size. Computing the parameter is NP-hard already for chordal targets but fixed-parameter tractable when X is defined by forbidden induced subgraphs of bounded size. Once a minimum deletion set is known, the r

What carries the argument

The color-intersection graph Gamma, which records pairwise intersections of color classes and forces clique-sum decompositions at articulation colors inside the augmented conflict graph H.

If this is right

  • Exactness of the Lasserre hierarchy at level k+1 follows immediately for deletion to perfect graphs.
  • Exactness at level k+r follows for deletion to h-perfect residual graphs whose odd holes have rank at most r.
  • An exact dynamic programming algorithm computes the minimum deletion number whenever the blocks of the color-intersection graph have bounded size.
  • Rainbow matching can be solved exactly by branching on the deleted color classes and solving the resulting residual instances inside the target class.
  • The deletion parameter is fixed-parameter tractable when the target class is defined by a finite set of forbidden induced subgraphs of bounded size.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the color-intersection graph itself has bounded treewidth, the blockwise dynamic program could be turned into a polynomial-time algorithm for the deletion number even without a bound on block size.
  • The same deletion-to-exactness link may extend to other lift-and-project hierarchies beyond Lasserre when the target class satisfies analogous rank-exactness properties.
  • Parameterized algorithms for rainbow matching could be obtained by treating the deletion number as the parameter and combining the branching step with known algorithms inside the target class X.

Load-bearing premise

The hereditary class X must be uniformly rank-r exact or clique-sum local, and the color-intersection graph must induce the claimed clique-sum decompositions in the augmented graph.

What would settle it

An explicit edge-colored graph and hereditary class X that is uniformly rank-r exact, together with a deletion of k colors placing the residual augmented graph in X, yet the Lasserre relaxation at level k+r still has a fractional optimum strictly larger than the integral optimum.

read the original abstract

We study the rainbow matching (RM) problem: given an edge-colored graph, find a maximum matching with at most one edge of each color. Rainbow matchings correspond to stable sets in the \emph{augmented} graph $H$ obtained from the line graph by completing each color class into a clique. For a hereditary graph class $\mathcal{X}$, we introduce the parameter $\kappa_{\mathcal{X}}$ to be the minimum number of colors whose deletion places the \emph{residual} augmented graph in $\mathcal{X}$. We show that this parameter has two complementary flavors. From a polyhedral side, if $\mathcal{X}$ is uniformly rank-$r$ exact, then deleting $k$ colors to obtain a residual augmented graph in $\mathcal{X}$ implies exactness of the Lasserre hierarchy at level $k+r$. This yields, in particular, exactness at level $k+1$ for deletion to perfect, and exactness at level $k+r$ for deletion to $h$-perfect residual graphs of bounded odd-hole rank $r$. Our second result is structural. We show that the right object in this case is the \emph{color-intersection} graph $\Gamma$ that impacts the topology of the conflict graph $H$ as follows: articulation colors in $\Gamma$ induce clique-sum decompositions in $H$, so residual obstructions for clique-sum-local hereditary classes $\mathcal{X}$ are embedded in individual blocks. Thus we can test membership of the residual graph in these target classes in a blockwise manner. As a consequence, we give an exact dynamic programming algorithm for computing the deletion parameter when $\Gamma$ has blocks of bounded size. Finally, once such a deletion set is given, RM can be solved by branching over the deleted color classes and solving residual instances. We also show that computing this parameter is \textbf{NP}-hard already in the chordal targets but it is FPT for classes $\mathcal{X}$ characterized by a set of forbidden induced subgraphs of bounded size.

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.

Referee Report

2 major / 2 minor

Summary. The paper studies the rainbow matching problem on edge-colored graphs by reducing it to stable sets in an augmented conflict graph H. It introduces the deletion parameter κ_X for a hereditary class X as the minimum number of colors to delete so the residual augmented graph lies in X. Polyhedrally, if X is uniformly rank-r exact then k deletions imply Lasserre exactness at level k+r (with corollaries for perfect and h-perfect targets). Structurally, the color-intersection graph Γ is shown to induce clique-sum decompositions of H at articulation colors, enabling blockwise membership testing for clique-sum-local X and an exact DP algorithm when Γ-blocks are bounded; the parameter is NP-hard for chordal X but FPT when X is defined by bounded-size forbidden induced subgraphs. Once a deletion set is found, RM is solved by branching on deleted colors and solving residuals.

Significance. If the lifting and structural claims hold, the work supplies a clean interface between Lasserre hierarchy exactness and hereditary graph classes for rainbow matching, together with a concrete FPT algorithm for computing κ_X on bounded-block instances. The introduction of the color-intersection graph Γ as the right auxiliary object for clique-sum locality is a useful structural contribution that may generalize beyond rainbow matching.

major comments (2)
  1. [Abstract / §2] Abstract and §2 (definition of uniform rank-r exactness): the central lifting claim—that k color deletions to a residual graph in X yield Lasserre exactness at level k+r—depends on the precise moment-matrix construction respecting the vertex-disjoint color cliques in the augmented graph H. The manuscript must supply the explicit inductive step or reference showing that the rank-r exactness of X carries over after the color-clique completion is removed.
  2. [§4] §4 (clique-sum locality via Γ): the claim that articulation colors in the color-intersection graph Γ induce clique-sum decompositions of H is load-bearing for the blockwise membership test and the subsequent DP. The manuscript must exhibit the explicit separator construction (i.e., how the cut-vertex in Γ corresponds to a clique separator in H) and verify that residual obstructions remain confined to individual blocks for any clique-sum-local hereditary X.
minor comments (2)
  1. [§2] Notation for the augmented graph H and the color-intersection graph Γ should be introduced with a small running example (e.g., a 4-edge colored C4) to clarify how color classes become cliques and how Γ is built from color intersections.
  2. [§5] The FPT result for forbidden-subgraph classes of bounded size is stated without an explicit dependence on the size of the forbidden set; a sentence clarifying the parameter dependence would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive major comments. We address each point below and will strengthen the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract / §2] Abstract and §2 (definition of uniform rank-r exactness): the central lifting claim—that k color deletions to a residual graph in X yield Lasserre exactness at level k+r—depends on the precise moment-matrix construction respecting the vertex-disjoint color cliques in the augmented graph H. The manuscript must supply the explicit inductive step or reference showing that the rank-r exactness of X carries over after the color-clique completion is removed.

    Authors: We agree that the lifting argument would benefit from an explicit inductive step. The current manuscript states the high-level polyhedral claim but does not spell out the moment-matrix construction that respects the vertex-disjoint color cliques. In the revision we will insert a short inductive lemma in §2 that shows how rank-r exactness of the residual graph in X lifts to Lasserre level k+r once the deleted color cliques are accounted for; the argument uses the fact that the added cliques are vertex-disjoint and therefore do not interfere with the existing moment-matrix relations. No change to the theorem statements is required. revision: yes

  2. Referee: [§4] §4 (clique-sum locality via Γ): the claim that articulation colors in the color-intersection graph Γ induce clique-sum decompositions of H is load-bearing for the blockwise membership test and the subsequent DP. The manuscript must exhibit the explicit separator construction (i.e., how the cut-vertex in Γ corresponds to a clique separator in H) and verify that residual obstructions remain confined to individual blocks for any clique-sum-local hereditary X.

    Authors: We concur that the separator construction and obstruction confinement are essential for the structural results. Section 4 sketches the correspondence but does not give the formal separator lemma or the blockwise confinement argument. In the revision we will add a proposition in §4 that (i) maps each cut-vertex (articulation color) of Γ to the corresponding clique of same-colored edges in H, which separates the blocks, and (ii) proves that, for any clique-sum-local hereditary class X, every forbidden induced subgraph of the residual graph lies entirely inside one block. This will directly justify the blockwise membership test and the DP algorithm. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations are self-contained implications from stated hypotheses

full rationale

The paper introduces the deletion parameter κ_X as the min colors to delete so the residual augmented graph lies in hereditary class X, then proves two results: (1) if X is uniformly rank-r exact then Lasserre exactness lifts to level k+r, and (2) articulation colors in the color-intersection graph Γ induce clique-sum decompositions allowing blockwise testing. Both follow directly from the hereditary property of X, the construction of the augmented conflict graph H, and the definition of Γ; no equation or claim reduces by construction to a fitted parameter, self-definition, or self-citation chain. The NP-hardness and FPT results are standard complexity arguments on the new parameter. All load-bearing steps are explicit hypotheses or standard polyhedral/graph-theoretic facts, yielding a self-contained derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The central claims rest on the newly introduced deletion parameter and color-intersection graph together with standard domain assumptions about hereditary classes and Lasserre hierarchy properties.

axioms (2)
  • domain assumption Uniform rank-r exactness of hereditary graph classes X
    Invoked to obtain the Lasserre exactness implication at level k+r.
  • domain assumption Hereditary and clique-sum local properties of the target classes X
    Used to guarantee that residual obstructions lie inside individual blocks of the decomposition.
invented entities (2)
  • kappa_X deletion parameter no independent evidence
    purpose: Minimum number of colors whose deletion places the residual augmented graph in X
    Newly defined quantity whose polyhedral and algorithmic consequences are studied.
  • Color-intersection graph Gamma no independent evidence
    purpose: Captures color interactions that induce clique-sum decompositions in the augmented conflict graph H
    Introduced to establish blockwise locality for membership testing and dynamic programming.

pith-pipeline@v0.9.0 · 5676 in / 1523 out tokens · 71530 ms · 2026-05-07T15:10:08.266231+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 23 canonical work pages

  1. [1]

    Abu-Khzam

    Faisal N. Abu-Khzam. A kernelization algorithm for d-hitting set.J. Comput. Syst. Sci., 76(7):524–531, 2010. URL: https://doi.org/10.1016/j.jcss.2009.09.002, doi: 10.1016/J.JCSS.2009.09.002

    work page doi:10.1016/j.jcss.2009.09.002 2010

  2. [2]

    Howard, and Paul D

    Ron Aharoni, Eli Berger, Maria Chudnovsky, David M. Howard, and Paul D. Seymour. Large rainbow matchings in general graphs.Eur. J. Comb., 79:222–227, 2019. URL: https://doi.org/10.1016/j.ejc.2019.01.012,doi:10.1016/J.EJC.2019.01.012

    work page doi:10.1016/j.ejc.2019.01.012 2019

  3. [3]

    Thilikos, and Sebastian Wiederrecht

    St´ ephane Bessy, Marin Bougeret, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Kernelization for graph packing problems via rainbow matching. In Nikhil Bansal and Viswanath Nagarajan, editors,Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 3654–3663. SIAM, 2023. URL: https://do...

    work page doi:10.1137/1.9781611977554.ch139 2023

  4. [4]

    Bianchi, Mariana S

    Silvia M. Bianchi, Mariana S. Escalante, Graciela L. Nasini, and Levent Tun¸ cel. Lov´ asz- schrijver sdp-operator, near-perfect graphs and near-bipartite graphs.Math. Program., 162(1-2):201–223, 2017. URL: https://doi.org/10.1007/s10107-016-1035-1, doi:10. 1007/S10107-016-1035-1

    work page doi:10.1007/s10107-016-1035-1 2017

  5. [5]

    Tree-width and the sherali-adams operator.Dis- cret

    Daniel Bienstock and Nuri ¨Ozbay. Tree-width and the sherali-adams operator.Dis- cret. Optim., 1(1):13–21, 2004. URL: https://doi.org/10.1016/j.disopt.2004.03.002, doi:10.1016/J.DISOPT.2004.03.002

    work page doi:10.1016/j.disopt.2004.03.002 2004

  6. [6]

    Fixed-parameter tractability of graph modification problems for heredi- tary properties.Inf

    Leizhen Cai. Fixed-parameter tractability of graph modification problems for heredi- tary properties.Inf. Process. Lett., 58(4):171–176, 1996. doi:10.1016/0020-0190(96) 00050-6

    work page doi:10.1016/0020-0190(96 1996

  7. [7]

    The complexity of general-valued constraint satisfaction problems seen from the other side.SIAM J

    Cl´ ement Carbonnel, Miguel Romero, and Stanislav Zivn´ y. The complexity of general-valued constraint satisfaction problems seen from the other side.SIAM J. Comput., 51(1):19–69,

  8. [8]

    URL:https://doi.org/10.1137/19m1250121,doi:10.1137/19M1250121

    work page doi:10.1137/19m1250121

  9. [9]

    On certain polytopes associated with graphs.Journal of Combinatorial Theory, Series B, 18(2):138–154, 1975

    Vaˇ sek Chv´ atal. On certain polytopes associated with graphs.Journal of Combinatorial Theory, Series B, 18(2):138–154, 1975

    1975

  10. [10]

    Arthur A. Drisko. Transversals in row-latin rectangles.J. Comb. Theory A, 84(2):181– 195, 1998. URL: https://doi.org/10.1006/jcta.1998.2894, doi:10.1006/JCTA.1998. 2894

    work page doi:10.1006/jcta.1998.2894 1998

  11. [11]

    Fomin, Petr A

    Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Saket Saurabh. Stability in graphs with matroid constraints. In Hans L. Bodlaender, editor,19th Scandinavian 23 Symposium and Workshops on Algorithm Theory, SWAT 2024, Helsinki, Finland, June 12-14, 2024, LIPIcs, pages 22:1–22:16. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik,

    2024

  12. [12]

    SWAT.2024.22

    URL: https://doi.org/10.4230/LIPIcs.SWAT.2024.22, doi:10.4230/LIPICS. SWAT.2024.22

    work page doi:10.4230/lipics.swat.2024.22 2024

  13. [13]

    Parrilo, and Rekha R

    Jo˜ ao Gouveia, Pablo A. Parrilo, and Rekha R. Thomas. Theta bodies for polynomial ideals.SIAM Journal on Optimization, 20(4):2097–2118, 2010. arXiv:https://doi.org/ 10.1137/090746525,doi:10.1137/090746525

    work page doi:10.1137/090746525 2097

  14. [14]

    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

  15. [15]

    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. URL: https://doi.org/ 10.1007/s00453-019-00618-0,doi:10.1007/S00453-019-00618-0

    work page doi:10.1007/s00453-019-00618-0 2020

  16. [16]

    Pinar Heggernes, Pim van ’t Hof, Bart M. P. Jansen, Stefan Kratsch, and Yngve Villanger. Parameterized complexity of vertex deletion into perfect graph classes.Theor. Comput. Sci., 511:172–180, 2013. URL: https://doi.org/10.1016/j.tcs.2012.03.013, doi: 10.1016/J.TCS.2012.03.013

    work page doi:10.1016/j.tcs.2012.03.013 2013

  17. [17]

    Tanimoto

    Alon Itai, Michael Rodeh, and Steven L. Tanimoto. Some matching problems for bipartite graphs.J. ACM, 25(4):517–525, 1978.doi:10.1145/322092.322093

    work page doi:10.1145/322092.322093 1978

  18. [18]

    Integrality gaps of linear and semi-definite programming relaxations for knapsack

    Anna R Karlin, Claire Mathieu, and C Thach Nguyen. Integrality gaps of linear and semi-definite programming relaxations for knapsack. InInternational Conference on Integer Programming and Combinatorial Optimization, pages 301–314. Springer, 2011

    2011

  19. [19]

    Integrality gaps for colorful matchings.Discret

    Steven Kelk and Georgios Stamoulis. Integrality gaps for colorful matchings.Discret. Optim., 32:73–92, 2019. URL: https://doi.org/10.1016/j.disopt.2018.12.003, doi: 10.1016/J.DISOPT.2018.12.003

    work page doi:10.1016/j.disopt.2018.12.003 2019

  20. [20]

    Parameterized complexity of domination problems using restricted modular partitions

    Manuel Lafond and Weidong Luo. Parameterized complexity of domination problems using restricted modular partitions. In J´ erˆ ome Leroux, Sylvain Lombardy, and David Peleg, editors,48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, Bordeaux, France, August 28 - September 1, 2023, LIPIcs, pages 61:1–61:14. Schloss Dags...

    work page doi:10.4230/lipics.mfcs.2023.61 2023

  21. [21]

    Lasserre

    Jean B. Lasserre. An explicit exact SDP relaxation for nonlinear 0-1 programs. In Karen I. Aardal and Bert Gerards, editors,Integer Programming and Combinatorial Optimization, 8th International IPCO Conference, Utrecht, The Netherlands, June 13-15, 2001, Proceedings, Lecture Notes in Computer Science, pages 293–303. Springer, 2001. doi:10.1007/3-540-45535-3\_23

    work page doi:10.1007/3-540-45535-3 2001

  22. [22]

    SIAM Journal on Optimization 11(3), 796–817 (2001) https://doi.org/10.1137/S1052623400366802

    Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim., 11(3):796–817, 2001.doi:10.1137/S1052623400366802

    work page doi:10.1137/s1052623400366802 2001

  23. [23]

    A comparison of the sherali-adams, lov´ asz-schrijver, and lasserre relaxations for 0–1 programming.Mathematics of Operations Research, 28(3):470–496, 2003

    Monique Laurent. A comparison of the sherali-adams, lov´ asz-schrijver, and lasserre relaxations for 0–1 programming.Mathematics of Operations Research, 28(3):470–496, 2003. 24

    2003

  24. [24]

    Complexity results for rainbow matchings.Theor

    Van Bang Le and Florian Pfender. Complexity results for rainbow matchings.Theor. Comput. Sci., 524:27–33, 2014. URL: https://doi.org/10.1016/j.tcs.2013.12.013, doi:10.1016/J.TCS.2013.12.013

    work page doi:10.1016/j.tcs.2013.12.013 2014

  25. [25]

    Cones of matrices and set-functions and 0–1 optimization.SIAM journal on optimization, 1(2):166–190, 1991

    L´ aszl´ o Lov´ asz and Alexander Schrijver. Cones of matrices and set-functions and 0–1 optimization.SIAM journal on optimization, 1(2):166–190, 1991

    1991

  26. [26]

    Chordal deletion is fixed-parameter tractable.Algorithmica, 57(4):747– 768, 2010

    D´ aniel Marx. Chordal deletion is fixed-parameter tractable.Algorithmica, 57(4):747– 768, 2010. URL: https://doi.org/10.1007/s00453-008-9233-8, doi:10.1007/ S00453-008-9233-8

    work page doi:10.1007/s00453-008-9233-8 2010

  27. [27]

    Bi-criteria and approximation algorithms for restricted matchings.Theor

    Monaldo Mastrolilli and Georgios Stamoulis. Bi-criteria and approximation algorithms for restricted matchings.Theor. Comput. Sci., 540:115–132, 2014. URL: https://doi.org/ 10.1016/j.tcs.2013.11.027,doi:10.1016/J.TCS.2013.11.027

    work page doi:10.1016/j.tcs.2013.11.027 2014

  28. [28]

    Refined parameterizations for computing colored cuts in edge-colored graphs.Theory Comput

    Nils Morawietz, Niels Gr¨ uttemeier, Christian Komusiewicz, and Frank Sommer. Refined parameterizations for computing colored cuts in edge-colored graphs.Theory Comput. Syst., 66(5):1019–1045, 2022. URL: https://doi.org/10.1007/s00224-022-10101-z, doi:10.1007/S00224-022-10101-Z

    work page doi:10.1007/s00224-022-10101-z 2022

  29. [29]

    The lasserre hierarchy in approximation algorithms.Lecture Notes for the MAPSP, pages 1–25, 2013

    Thomas Rothvoß. The lasserre hierarchy in approximation algorithms.Lecture Notes for the MAPSP, pages 1–25, 2013

    2013

  30. [30]

    Najiba Sbihi and J. P. Uhry. A class of h-perfect graphs.Discret. Math., 51(2):191–205, 1984.doi:10.1016/0012-365X(84)90071-2

    work page doi:10.1016/0012-365x(84)90071-2 1984

  31. [31]

    Approximation algorithms for bounded color matchings via convex decompositions

    Georgios Stamoulis. Approximation algorithms for bounded color matchings via convex decompositions. In Erzs´ ebet Csuhaj-Varj´ u, Martin Dietzfelbinger, and Zolt´ an´Esik, editors, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, Lecture Notes in Compu...

    work page doi:10.1007/978-3-662-44465-8 2014

  32. [32]

    Treewidth-based conditions for exactness of the sherali-adams and lasserre relaxations

    Martin J Wainwright and Michael I Jordan. Treewidth-based conditions for exactness of the sherali-adams and lasserre relaxations. Technical report, Technical Report 671, University of California, Berkeley, 2004. 25

    2004