Breaking the quadratic barrier for matroid intersection

The matroid intersection problem is a fundamental problem that has been extensively studied for half a century. In the classic version of this problem, we are given two matroids M 1 = (V, I 1 ) and M 2 = (V, I 2 ) on a comment ground set V of n elements, and then we have to find the largest common independent set S ∈ I 1 ∩ I 2 by making independence oracle queries of the form "Is S ∈ I 1 ?" or "Is S ∈ I 2 ?" for S ⊆ V . The goal is to minimize the number of queries. Beating the existing Õ(n 2 ) bound, known as the quadratic barrier, is an open problem that captures the limits of techniques from two lines of work. The first one is the classic Cunningham's algorithm [SICOMP 1986], whose Õ(n 2 )-query implementations were shown by CLS+ [FOCS 2019] and Nguy ễn [2019]. 1 The other one is the general cutting plane method of Lee, Sidford, and Wong [FOCS 2015]. The only progress towards breaking the quadratic barrier requires either approximation algorithms or a more powerful rank oracle query [CLS+ FOCS 2019]. No exact algorithm with o(n 2 ) independence queries was known. In this work, we break the quadratic barrier with a randomized algorithm guaranteeing Õ(n 9/5 ) independence queries with high probability, and a deterministic algorithm guaranteeing Õ(n 11/6 ) independence queries. Our key insight is simple and fast algorithms to solve a graph reachability problem that arose in the standard augmenting path framework [Edmonds 1968]. Combining this with previous exact and approximation algorithms leads to our results. 1 More generally, these algorithms take Õ(nr) queries where r denotes the rank which can be as big as n.