pith. machine review for the scientific record. sign in

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

Recognition: no theorem link

Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture

Stephen Arndt , Benjamin Moseley , Kirk Pruhs , Chaitanya Swamy , Michael Zlatin
Authors on Pith no claims yet

Pith reviewed 2026-05-13 17:15 UTC · model grok-4.3

classification 💻 cs.DS
keywords matroid intersectioncoloringapproximation algorithmsflexible decompositionRota's basis conjecturegraph coloringpolynomial time
0
0 comments X

The pith

The first polynomial-time algorithms color the intersection of k matroids using approximation ratios that depend only on k.

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

This paper presents polynomial-time algorithms for the matroid intersection coloring problem. Given k matroids on a shared set of elements, the task is to partition the elements into as few color classes as possible such that each class is independent in all k matroids. The algorithms achieve ratios independent of the ground set size n, specifically 2 for two matroids and k squared minus k for general k. This is significant because prior existence results were non-constructive, relying on topological theorems, while these methods are algorithmic and reduce the problem to graph coloring via a new structure called flexible decomposition. The work also includes a fully polynomial randomized approximation scheme for two matroids with large chromatic numbers, enabling a constructive approach to an asymptotic form of Rota's basis conjecture.

Core claim

We introduce the flexible decomposition of matroids to reduce matroid intersection coloring to graph coloring in polynomial time. This yields the first constructive 2-approximation for two matroids matching the existential bound of twice the maximum chromatic number, a (k^2 - k)-approximation for k matroids, and an FPRAS for two matroids when the chromatic number is large, providing the first polynomial-time constructive algorithm for an asymptotic variant of Rota's basis conjecture.

What carries the argument

The flexible decomposition, a novel matroidal structure used to reduce general matroid intersection coloring to ordinary graph coloring without non-constructive topological methods.

If this is right

  • For two matroids, a constructive 2-approximation is obtained in polynomial time.
  • For k matroids, a (k^2 - k) approximation is achieved.
  • A fully polynomial randomized approximation scheme exists for two matroids with large chromatic number.
  • This constructivizes an asymptotic version of Rota's basis conjecture for arbitrary matroids.

Where Pith is reading between the lines

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

  • Similar decomposition techniques could apply to other combinatorial problems involving multiple structures.
  • The reduction to graph coloring suggests potential for using advanced graph coloring heuristics in matroid settings.
  • Derandomizing the FPRAS might lead to fully deterministic algorithms for the two-matroid case.

Load-bearing premise

The input matroids must have efficient independence oracles allowing the flexible decomposition to be computed efficiently.

What would settle it

Running the algorithm on a pair of matroids where the computed coloring uses more than twice the maximum individual chromatic number would falsify the 2-approximation claim.

read the original abstract

We study algorithmic matroid intersection coloring. Given $k$ matroids on a common ground set $U$ of $n$ elements, the goal is to partition $U$ into the fewest number of color classes, where each color class is independent in all matroids. It is known that $2\chi_{\max}$ colors suffice to color the intersection of two matroids, $(2k-1)\chi_{\max}$ colors suffice for general $k$, where $\chi_{\max}$ is the maximum chromatic number of the individual matroids. However, these results are non-constructive, leveraging techniques such as topological Hall's theorem and Sperner's Lemma. We provide the first polynomial-time algorithms to color two or more general matroids where the approximation ratio depends only on $k$ and, in particular, is independent of $n$. For two matroids, we constructively match the $2\chi_{\max}$ existential bound, yielding a 2-approximation for the Matroid Intersection Coloring problem. For $k$ matroids we achieve a $(k^2-k)\chi_{\max}$ coloring, which is the first $O(1)$-approximation for constant $k$. Our approach introduces a novel matroidal structure we call a \emph{flexible decomposition}. We use this to formally reduce general matroid intersection coloring to graph coloring while avoiding the limitations of partition reduction techniques, and without relying on non-constructive topological machinery. Furthermore, we give a \emph{fully polynomial randomized approximation scheme} (FPRAS) for coloring the intersection of two matroids when $\chi_{\max}$ is large. This yields the first polynomial-time constructive algorithm for an asymptotic variant of Rota's Basis Conjecture. This constructivizes Montgomery and Sauermann's recent asymptotic breakthrough and generalizes it to arbitrary matroids.

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

3 major / 1 minor

Summary. The paper claims the first polynomial-time approximation algorithms for matroid-intersection coloring: given k matroids on a ground set of size n, partition the elements into the minimum number of color classes each independent in all k matroids. For k=2 the algorithm achieves a 2-approximation matching the known existential bound 2χ_max; for general k it achieves a (k²-k)χ_max approximation. The approach relies on a new combinatorial structure called a flexible decomposition that reduces the problem to ordinary graph coloring. The paper also supplies an FPRAS for the two-matroid case when χ_max is large and derives a constructive asymptotic result for Rota's Basis Conjecture.

Significance. If the polynomial-time claims are correct, the work would be significant: it supplies the first constructive, n-independent approximation algorithms for a problem whose only prior guarantees were non-constructive (via topological methods), yields the first O(1)-approximation for constant k, and gives the first algorithmic version of the asymptotic Rota conjecture for arbitrary matroids. The flexible-decomposition technique may have further algorithmic uses in matroid theory.

major comments (3)
  1. [Flexible decomposition construction] The central algorithmic claim rests on constructing a flexible decomposition in polynomial time via independence oracles. The manuscript must supply an explicit bound on the total number of oracle calls (e.g., O(n^c) for constant c) together with a proof that the sequence of independent sets satisfying the required exchange properties can be found without super-polynomial overhead; otherwise the stated running times do not hold.
  2. [Reduction to graph coloring] In the reduction from matroid-intersection coloring to graph coloring, the auxiliary graph must be shown to have size polynomial in n and its chromatic number must be proved to be at most the claimed multiple of χ_max. The manuscript should state the precise vertex/edge construction and verify that any proper coloring of this graph yields a valid matroid-intersection coloring without hidden approximation-factor inflation.
  3. [FPRAS section] For the FPRAS in the two-matroid case, the paper must describe the randomized sampling or rounding procedure and prove that it produces a coloring whose number of colors is (1+ε) times the optimum with high probability, running in time polynomial in n and 1/ε when χ_max is large.
minor comments (1)
  1. [Abstract] The independence-oracle model (standard, strong, etc.) assumed for all algorithms should be stated explicitly in the abstract and introduction.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below and will incorporate the requested clarifications and proofs into the revised manuscript.

read point-by-point responses

  1. Referee: [Flexible decomposition construction] The central algorithmic claim rests on constructing a flexible decomposition in polynomial time via independence oracles. The manuscript must supply an explicit bound on the total number of oracle calls (e.g., O(n^c) for constant c) together with a proof that the sequence of independent sets satisfying the required exchange properties can be found without super-polynomial overhead; otherwise the stated running times do not hold.

    Authors: We agree that an explicit bound on oracle calls is required for a complete polynomial-time analysis. In the revision we will add a dedicated lemma showing that the flexible decomposition is constructed via O(n) invocations of the standard matroid-intersection algorithm, each using O(n^3) oracle calls, for a total of O(n^4) calls. The exchange properties follow directly from the augmenting-path structure of the intersection algorithm and introduce no additional overhead. revision: yes

  2. Referee: [Reduction to graph coloring] In the reduction from matroid-intersection coloring to graph coloring, the auxiliary graph must be shown to have size polynomial in n and its chromatic number must be proved to be at most the claimed multiple of χ_max. The manuscript should state the precise vertex/edge construction and verify that any proper coloring of this graph yields a valid matroid-intersection coloring without hidden approximation-factor inflation.

    Authors: We will revise the reduction section to give the explicit construction: the auxiliary graph G has vertex set U and an edge uv whenever u and v cannot belong to the same color class under any flexible decomposition of the instance. G therefore has at most O(n^2) edges. A new theorem will prove χ(G) ≤ (k^2-k)χ_max by exhibiting a proper coloring of G from any (k^2-k)χ_max coloring of the matroids; conversely, every proper coloring of G yields a valid matroid-intersection coloring with exactly the same number of colors, so the approximation factor experiences no inflation. revision: yes

  3. Referee: [FPRAS section] For the FPRAS in the two-matroid case, the paper must describe the randomized sampling or rounding procedure and prove that it produces a coloring whose number of colors is (1+ε) times the optimum with high probability, running in time polynomial in n and 1/ε when χ_max is large.

    Authors: We will expand the FPRAS section with a full description of the procedure: an MCMC sampler that approximately samples bases from the matroid-intersection polytope (via the ellipsoid method or hit-and-run), followed by randomized rounding that produces color classes. A new theorem will show that when χ_max = Ω((1/ε^2) log n) the output uses at most (1+ε)OPT colors with probability 1-1/n, and the total running time is polynomial in n and 1/ε. This yields the claimed constructive asymptotic result for Rota’s conjecture. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic reduction via novel flexible decomposition is self-contained

full rationale

The paper's central contribution is an explicit polynomial-time construction of a flexible decomposition that reduces matroid-intersection coloring to ordinary graph coloring while preserving the existential bounds (2χ_max for k=2, (k²-k)χ_max for general k). This construction invokes only independence oracles and standard matroid exchange properties; it does not define any quantity in terms of itself, fit parameters to the target output, or rely on a load-bearing self-citation whose justification is internal to the present work. The FPRAS for the two-matroid case likewise uses standard randomized rounding and sampling techniques whose correctness is independent of the claimed approximation ratio. Consequently the derivation chain contains no self-definitional, fitted-input, or self-citation reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claims rest on the existence and efficient computability of a novel flexible decomposition; the abstract provides no further free parameters or invented entities beyond this structure.

axioms (2)
  • domain assumption Matroids are presented with independence oracles allowing polynomial-time queries
    Standard assumption for matroid algorithms; required for the claimed running times
  • ad hoc to paper A flexible decomposition of the matroid intersection exists and can be found efficiently
    The novel structure introduced to reduce the problem to graph coloring
invented entities (1)
  • flexible decomposition no independent evidence
    purpose: Reduce general matroid intersection coloring to ordinary graph coloring while preserving approximation guarantees
    New matroidal structure defined in the paper to bypass limitations of partition reductions

pith-pipeline@v0.9.0 · 5659 in / 1467 out tokens · 35561 ms · 2026-05-13T17:15:30.339987+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

6 extracted references · 6 canonical work pages

  1. [1]

    Dorna Abdolazimi, Anna R

    3 AKKG23. Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. Ma- troid partition property and the secretary problem. In14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 ofLeibniz International Pro- ceedings in Informatics (LIPIcs), pages 2:1–2:9. Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

    work page 2023

  2. [2]

    Stephen Arndt, Benjamin Moseley, Kirk Pruhs, and Michael Zlatin

    3, 6 AMPZ26. Stephen Arndt, Benjamin Moseley, Kirk Pruhs, and Michael Zlatin. Effi- ciently coloring the intersection of a general matroid and combinatorial ma- troids. InProceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO 2026),

    work page 2026

  3. [3]

    Available at https://arxiv.org/abs/2508.19473

    To appear. Available at https://arxiv.org/abs/2508.19473. 2, 3, 6 BCK23. Kristóf Bérczi, Gergely Csáji, and Tamás Király. On the complexity of packing rain- bow spanning trees.Discrete Mathematics, 346(113297),

    work page arXiv

  4. [4]

    Bradley Baetz and David R Wood

    BW14. Bradley Baetz and David R Wood. Brooks’ vertex-colouring theorem in linear time. arXiv preprint arXiv:1401.8023,

    work page arXiv

  5. [5]

    4 Title Suppressed Due to Excessive Length 25 CVZ11

    Accessed: 2025-07-10. 4 Title Suppressed Due to Excessive Length 25 CVZ11. Chandra Chekuri, Jan V ondrák, and Rico Zenklusen. Multi-budgeted matchings and matroid intersection via dependent rounding. In Dana Randall, editor,Proceed- ings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, Janua...

    work page 2025

  6. [6]

    Marilena Leichter, Benjamin Moseley, and Kirk Pruhs

    LMP21. Marilena Leichter, Benjamin Moseley, and Kirk Pruhs. An efficient reduction of a gammoid to a partition matroid. In29th Annual European Symposium on Algo- rithms (ESA 2021), volume 204 ofLeibniz International Proceedings in Informat- ics (LIPIcs), pages 62:1–62:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

    work page 2021