arXiv · Oct 23, 2026
Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs
By Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
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.