Robust Sparsification for Matroid Intersection with Applications

Matroid intersection is a classical optimization problem where given two matroids over the same ground set, the goal is to find the largest common independent set. In this paper, we show that there exists a certain “sparsifer”: a subset of elements of size $O(|S^{\mathit{\text{opt}}}|·1/\epsilon )$, where $S^{\mathit{\text{opt}}}$ denotes the optimal solution, that is guaranteed to contain a $3/2+\epsilon$ approximation while guaranteeing certain robustness properties. We call such a small subset a density constrained subset, which is inspired by the edge-degree constrained subgraph, originally designed for the maximum cardinality matching problem in a graph. Our proof is constructive and hinges on a greedy decomposition of matroids, which we call the density-based decomposition. We show that this sparsifier has certain robustness properties that can be used in one-way communication and random-order streaming models.

Funding: This research was supported by the Agence Nationale de la Recherche [Grant ANR-19-CE48-0016].