Breaking the Quadratic Barrier for Matroid Intersection
share
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 ℳ_1 = (V, ℐ_1) and ℳ_2 = (V, ℐ_2) on a comment ground set V of n elements, and then we have to find the largest common independent set S ∈ℐ_1 ∩ℐ_2 by making independence oracle queries of the form "Is S ∈ℐ_1?" or "Is S ∈ℐ_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 Nguyen [2019]. 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.
READ FULL TEXT