Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

We present an $\tilde O(m+n^{1.5})$-time randomized algorithm for maximum bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, and optimal transport) on $m$-edge and $n$-node graphs. For maximum bipartite matching on moderately dense graphs, i.e. $m = \Omega(n^{1.5})$, our algorithm runs in time nearly linear in the input size and constitutes the first improvement over the classic $O(m\sqrt{n})$-time [Dinic 1970; Hopcroft-Karp 1971; Karzanov 1973] and $\tilde O(n^\omega)$-time algorithms [Ibarra-Moran 1981] (where currently $\omega\approx 2.373$). On sparser graphs, i.e. when $m = n^{9/8 + \delta}$ for any constant $\delta>0$, our result improves upon the recent advances of [Madry 2013] and [Liu-Sidford 2020b, 2020a] which achieve an $\tilde O(m^{4/3})$ runtime.

We obtain this result by several techniques of independent interest. First, we provide a simple sublinear-time algorithm for detecting high-energy edges in electric flows on expanders. Second, we combine this technique with recent advances in dynamic expander decompositions to provide a data structure for efficiently maintaining the iterates of the interior point method of [v.d.Brand-Lee-Sidford-Song 2020]. Finally, we simplify and improve this method by providing new sampling-based techniques for handling loss of feasibility due to approximate linear system solvers. Combining these results yields our $\tilde O(m+n^{1.5})$-time algorithm.

• Algorithms and Theory