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.