Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs

Abstract

We give a combinatorial algorithm that computes an exact minimum-cost flow in $n^{2+o(1)}$ time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87], and is almost optimal in dense graphs. All previous faster algorithms, including the almost-linear-time algorithm of Chen et al. [CKL+22], rely on interior-point methods. Our main conceptual contribution is a black-box reduction from exact minimum-cost flow on general graphs to its approximation on DAGs, with only an $n^{o(1)}$ loss on the running time. This reduction allows future work on combinatorial minimum-cost flow to focus on DAGs, typically much easier to handle than general graphs. Our $n^{2+o(1)}$-time algorithm follows by combining this reduction with a simple augmenting-path-based approximation algorithm on DAGs. The reduction is based on a new structural result, called a flow-cost-preserving DAG projection. Given an arbitrary directed graph, this construction produces a DAG that approximately preserves both the congestion of flows and their cost up to a small loss.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.