Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

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

We obtain these results by combining and advancing recent lines of research in interior point methods (IPMs) and dynamic graph algorithms. First, we simplify and improve the IPM of [v.d.Brand-Lee-Sidford-Song 2020], providing a general primal-dual IPM framework and new sampling-based techniques for handling infeasibility induced by approximate linear system solvers. Second, we provide a simple sublinear-time algorithm for detecting and sampling highenergy edges in electric flows on expanders and show that when combined with recent advances in dynamic expander decompositions, this yields efficient data structures for maintaining the iterates of both [v.d.Brand et al.] and our new IPMs. Combining this general machinery yields a simpler Oe(n √ m) time algorithm for matching based on the logarithmic barrier function, and our state-of-the-art Oe(m + n 1.5 ) time algorithm for matching based on the [Lee-Sidford 2014] barrier (as regularized in [v.d.Brand et al.]).