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 [Formula: see text], where [Formula: see text] denotes the optimal solution, that is guaranteed to contain a [Formula: see text] 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].