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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Data Structures & Algorithms

• arXiv preprint · 23 October 2026

  Beyond 3SUM-Hardness for Geometric Problems

  Nick Fischer
• arXiv preprint · 24 October 2026

  Approximation algorithms for identical parallel machine scheduling with assignment costs

  Wei Li
• arXiv preprint · 23 October 2026

  The Exact Robustness of Smith's Rule with Predicted Processing Times

  Ohad Ayalon and Ilan Reuven Cohen
• arXiv preprint · 24 October 2026

  A Factor-6 Truthful-in-Expectation Mechanism for Cascade Position Auctions

  Qiuyu Chen and Baao Xie
• arXiv preprint · 23 October 2026

  Exact Algorithms and Complexity of the Smallest Grammar Problem

  Xiangle Chen

All new papers in Data Structures & Algorithms