Faster Matroid Intersection

In this paper we consider the classic matroid intersection problem: given two matroids M
₁
= (V, I
₁
) and M
₂
= (V, I
₂
) defined over a common ground set V , compute a set S ∈ I
₁
∩ I
₂
of 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 ∈ I
_i
in T
_ind
time, 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 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 O(n
²
·T
_ind
in 1986 and + n
³
) 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(n
^1.5
/ε
^1.5
· Tind) and O((n
²
r
^-1
ε
^-2
+ r
^1.5
ε
^-4.5
) · Tind), 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√r log n · T
_rank
)time exact algorithm and an O(nε
^-1
log n · T
_rank
)-time algorithm which obtains a (1 - 0)-approximation to the matroid intersection problem. The former result improves over the O(nr · T
_rank
+ n
³
)-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.