Faster Matroid Intersection

In this paper we consider the classic matroid intersection problem: given two matroids M-1=(V, I-1) and M-2=(V, I-2) defined over a common ground set V, compute a set SI-1 ∩ I-2 of largest possible cardinality, denoted by r. We consider this problem both in the setting where each M-i is accessed through an independence oracle, i.e. a routine which returns whether or not a set S I-i in T-ind time, and the setting where each M-i is accessed through a rank oracle, i.e. a routine which returns the size of the largest independent subset of S in M-i in T-rank time. In each setting we provide faster exact and approximate algorithms. Given an independence oracle, we provide an exact O(nr log r⋅T-ind) time algorithm. This improves upon previous best known running times of O(nr1.5⋅T-ind) due to Cunningham in 1986 and Õ(n2⋅T-ind+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 Õ(n1.5/ϵ1.5⋅T-ind) and Õ((n2r-1ϵ-2+r1.5ϵ-4.5)⋅T-ind), respectively. These results improve upon the O(nr/ϵ⋅T-ind)-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√rlog n⋅T-rank)-Time exact algorithm and an O(nϵ-1 log n⋅T-rank)-Time algorithm which obtains a (1-ϵ)-Approximation to the matroid intersection problem. The former result improves over the Õ(nr⋅T-rank+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.