Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
cs.DS, math.CO
Submitted: 2026-04-04
Updated: 2026-11-12
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study algorithmic matroid intersection coloring.
Terminology
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χ colors suffice to color the intersection of two matroids, (2k-1)χ colors suffice for general k, where χ 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χ existential bound, yielding a 2-approximation for the Matroid Intersection Coloring problem. For k matroids we achieve a (k 2-k)χ coloring, which is the first O(1) -approximation for constant k. Our approach introduces a novel matroidal structure we call a 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 fully polynomial randomized approximation scheme (FPRAS) for coloring the intersection of two matroids when χ 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.
Sources
- Efficiently Coloring the Intersection of a General Matroid and Combinatorial Matroids
- Brooks' Vertex-Colouring Theorem in Linear Time
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time