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

arXiv: https://arxiv.org/abs/1307.2205 · HTML: https://mlsanity.com/paper/1307.2205/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2013.

## Built on by (most cited first, 7 of 7)

- [Training Overparametrized Neural Networks in Sublinear Time](https://mlsanity.com/paper/2208.04508/) (2022)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Decomposable Submodular Function Minimization via Maximum Flow](https://mlsanity.com/paper/2103.03868/) (2021)
- [The Complexity of Dynamic Least-Squares Regression](https://mlsanity.com/paper/2201.00228/) (2022)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)
- [Binary Hypothesis Testing for Softmax Models and Leverage Score Models](https://mlsanity.com/paper/2405.06003/) (2024)
- [Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation](https://mlsanity.com/paper/2505.03955/) (2025)

## Abstract (arXiv)

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.