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 S is an element of I-1 boolean AND 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 is an element of 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(nr(1.5).T-ind) due to Cunningham in 1986 and (O) over tilde (n(2) . T-Ind + n(3)) due to Lee, Sidford, and Wong in 2015. We also provide two algorithms which compute a (1 - epsilon)-approximate solution to matroid intersection running in times (O) over tilde (n(1.5)/epsilon T-ind) and (O) over tilde (n(2)r(-1)epsilon(-2)+r(1.5)epsilon(-4.5)).T-ind), respectively. These results improve upon the O(nr/epsilon.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 root rlog n. T-rank)-time exact algorithm and an O(n(epsilon-1) log n.T-rank)-time algorithm which obtains a (1 - epsilon)-approximation to the matroid intersection problem. The former result improves over the (O) over tilde (nr . Trank + n(3))-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.