Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

We present an tildeO(m10/7)=tildeO(m1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min(√m,n2/3)) time bound due to Even and Tarjan [EvenT75]. By well-known reductions, this also establishes an tildeO(m10/7)-time algorithm for the maximum-cardinality bipartite matching problem. That, in turn, gives an improvement over the celebrated celebrated O(m √n) time bound of Hopcroft and Karp [HK73] whenever the input graph is sufficiently sparse.