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 $mathcal{M}_1 = (V, mathcal{I}_1)$ and $mathcal{M}_2 = (V, mathcal{I}_2)$ on a comment ground set $V$ of $n$ elements, and then we have to find the largest common independent set $S in mathcal{I}_1 cap mathcal{I}_2$ by making independence oracle queries of the form Is $S in mathcal{I}_1$? or Is $S in mathcal{I}_2$? for $S subseteq V$. The goal is to minimize the number of queries. Beating the existing $tilde O(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 Cunninghams algorithm [SICOMP 1986], whose $tilde O(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 $tilde O(n^{9/5})$ independence queries with high probability, and a deterministic algorithm guaranteeing $tilde O(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.
تحميل البحث