Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs

Understand

We present an $m^{4/3+o(1)}\log W$-time algorithm for solving the minimum cost flow problem in graphs with unit capacity, where $W$ is the maximum absolute value of any edge weight.

• For sparse graphs, this improves over the best known running time for this problem and, by well-known reductions, also implies improved running times for the shortest path problem with negative weights, minimum cost bipartite $\boldsymbol{\mathit{b}}$-matching when $\|\boldsymbol{\mathit{b}}\|_1 = O(m)$, and recovers the running time of the currently fastest algorithm for maximum flow in graphs with unit capacities (Liu-Sidford, 2020).
• Our algorithm relies on developing an interior point method-based framework which acts on the space of circulations in the underlying graph.
• From the combinatorial point of view, this framework can be viewed as iteratively improving the cost of a suboptimal solution by pushing flow around circulations.