Faster Matroid Intersection
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong · 2019
In this paper we consider the classic matroid intersection problem: given two matroids M1= (V, I1) and M2= (V, I2) defined over a common ground set V , compute a set S ∈ I1∩ I2of largest possible cardinality, denoted by r. We consider this problem both in the setting where each Mi is accessed through an independence oracle, i.e. a routine which returns whether or not a set S ∈ Iiin Tindtime, and the setting where each Mi is accessed through a rank oracle, i.e. a routine which returns the size of the largest independent subset of S in Miin Tranktime. In each setting we provide faster exact and approximate algorithms. Given an independence oracle, we provide an exact O(nr log r · Tind) time algorithm. This improves upon previous best known running times of O(nr1.5·Tind) due to Cunningham O(n2·Tindin 1986 and + n3) due to Lee, Sidford, and Wong in 2015. We also provide two algorithms which compute a (1- ε-approximate solution to matroid intersection running in times O(n1.5/ε1.5· Tind) and O((n2r-1ε-2+ r1.5ε-4.5) · Tind), respectively. These results improve upon the O(nr/ε · Tind)time algorithm of Cunningham (noted recently by Chekuri and Quanrud). Given a rank oracle, we provide algorithms with even better dependence on n and r. We provide an O(n√r log n · Trank)time exact algorithm and an O(nε-1log n · Trank)-time algorithm which obtains a (1 - 0)-approximation to the matroid intersection problem. The former result improves over the O(nr · Trank+ n3)-time algorithm by Lee, Sidford, and Wong. The rank oracle is of particular interest as the matroid intersection problem with this oracle is a special case (via Edmond's minimax characterization of matroid intersection) of the submodular function minimization (SFM) problem with an evaluation oracle, and understanding SFM query complexity is an outstanding open question.