Efficiently Coloring the Intersection of a General Matroid and Combinatorial Matroids

Jul 16, 2026

Upload by Himbo

This paper presents a polynomial-time algorithm for matroid intersection coloring when one matroid is general and the remaining matroids are partition matroids. Given a general matroid M1 and k−1 partition matroids M2,…,Mk, it colors the intersection M=∩i=1kMi using at most 1+∑i=1k(χ(Mi)−1) colors. It is the first polynomial-time O(k)-approximation for this setting, and it extends to standard combinatorial matroid types via reductions to partition matroids.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages26

Reading Time1 h 6 min

Introduction

Matroid intersection coloring definition

Prior existential results and bounds

Algorithmic landscape for polynomial-time coloring

arXiv :2508 . 19473v2 [ cs .DS] 13 Jul 2026 Efficiently Coloring the Intersection of a General Matroid and Combinatorial Matroids Stephen Arndt 1 [0009-0008-2847-0721], Benjamin Moseley 1 [0000-0001-8162-017X], Kirk Pruhs2 [0000-0001-5680-1753], and Michael Zlatin3 [0000-0003-1773-1152] 1 Carnegie Mellon University, Pittsburgh, PA, USA {sarndt,[moseleyb}@andrew.cmu.edu](moseleyb}@andrew.cmu.edu)[ ](moseleyb}@andrew.cmu.edu)2 University of Pittsburgh, Pittsburgh, PA, [USA](USA kirk@cs.pitt.edu)[ kirk@cs.pitt.edu](USA kirk@cs.pitt.edu)[ ](USA kirk@cs.pitt.edu)3 Pomona College, Claremont, CA, [USA](USA michael.zlatin@pomona.edu)[ michael.zlatin@pomona.edu](USA michael.zlatin@pomona.edu) [Abstract](Abstract). This paper shows a polynomial-time algorithm that, given a general matroid M1 and k−1 partition matroids M2 , . . . , Mk , produces a coloring of the intersection M = ∩ki=1 Mi using at most 1 +Pki=1 (χ(Mi) − 1) colors. This is the first polynomial-time O (k)-approximation algorithm for matroid intersection coloring where one of the matroids may be a general matroid. Leveraging the fact that most of the standard combinatorial matroids reduce to partition matroids ata loss of a factor of two in the chromatic number, this algorithm also yields a polynomial-time O (k)-approximation algorithm for matroid intersection coloring in the case where each of the matroids M2 , . . . , Mk are one of these standard combinatorial types. Even when k = 2, the previous best-known approximation ratio was O(log n) via a reduction to Set Cover. 1 Introduction Some of the most generally applicable tools in an algorithmist’s toolkit are efficient algorithms for various standard matroid-related optimization problems. In particular, a reasonable number of natural optimization problems can be viewed as set cover problems, in which the constraints can be partitioned into parts that induce a matroid [30,38] . Such problems can be viewed as matroid intersection coloring problems, defined as follows: – The input is a collection of matroids M1 = (X, I1 ) ,..., Mk = (X, Ik) on common ground set X. The intersection M = ∩ki=1 Mi is defined to be the set system 􀀀X, ∩ki=1Ii 􀀁 . – A feasible solution is a coloring of the elements of X such that, for every color, theset of elements assigned that color is independent in M , i.e. independent in each matroid Mi for i ∈ [k] . – The objective is to minimize the number of colors used. For any set system M, we use χ (M) to denote the chromatic number of M , that is the minimum number of colors necessary for the existence of a feasible coloring. There is a significant literature within the combinatorics/mathematics community that establishes existential results related in some way to matroid intersection coloring 2 Stephen Arndt , Benjamin Moseley , Kirk Pruhs, and Michael Zlatin (and/or packing) [3,8,2, 13,22, 19,32, 11] . However, most of the proofs of these results are nonconstructive, in that they are not readily adaptable to yield polynomial-time coloring algorithms. In particular, many of these results are established with topological fixed-point arguments that employ Sperner’s lemma [3,8,2] . We now highlight some of these existential results that are most relevant for this paper. Theorem 1. [3] For k general matroids M1 ,..., Mk, it is the case that χ 􀀀∩ki=1 Mi 􀀁 ≤(2k − 1)maxki=1 χ (Mi). For the intersection of two general matroids (k = 2), this can be improved to the following. Theorem 2. [8] For two general matroids M1 and M2 it is the case that χ(M1 ∩M2 ) ≤χ (M1 ) + χ(M2 ). The proofs of Theorems 1 and 2 both hinge on topological fixed-point arguments, deriving from an influential earlier paper by Aharoni and Berger [2] that shows that χ (M1 ∩ M2 ) ≤ 2max{χ(M1 ) ,χ (M2 )} . These theorems show that in some sense the chromatic number of the intersection of k matroids grows at most linearly with k. Further, there is a lower bound that rules out the possibility of many natural typ

FAQs

What problem does the paper address?

The paper studies matroid intersection coloring: assigning elements a minimum number of colors so that each color class is independent in every matroid in the intersection.

What is the main algorithmic result?

It gives a polynomial-time algorithm that, for one general matroid and k−1 partition matroids, produces a coloring using at most 1+∑i=2k(χ(Mi)−1) colors.

How does the paper improve over previous approximation ratios?

It provides the first polynomial-time O(k)-approximation algorithm in this setting; prior work for k=2 achieved only O(log n) using a reduction to Set Cover.

Jul 16, 2026

Upload by Himbo