Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

2022/03/01 by Li Chen, Rasmus Kyng, Chen, Li +9 · 4 voices · 50 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods #Optimization and Search Problems #cs.DS

paper · pdf · doi:10.48550/arxiv.2203.00671

openalex publication_date 2022/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in m^1+o(1) time. Our algorithm builds the flow through a sequence of m^1+o(1) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized m^o(1) time using a new dynamic graph data structure. Our framework extends to algorithms running in m^1+o(1) time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression on arbitrary directed acyclic graphs.

Cited by

• Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
• The Limits of Quantum Computers for Power Flow
• Bellman-Ford in Almost-Linear Time
• On the Computational Complexity of Local and Global Covering Numbers
• Beyond Stability: Improved Efficiency Guarantees for α-Stable Matchings
• Matching Composition and Efficient Weight Reduction in Dynamic Matching
• Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
• Constrained Cuts, Flows, and Lattice-Linearity
• A Differentiable Digital Twin of Distributed Link Scheduling for Contention-Aware Networking
• Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
• Quantum Algorithm for Estimating Ollivier-Ricci Curvature
• Dynamic Graph Coloring: Sequential, Parallel, and Distributed
• Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
• Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization
• Approximating Directed Connectivity in Almost-Linear Time
• Greedy Algorithms for Shortcut Sets and Hopsets
• From Hop Reduction to Sparsification for Negative Length Shortest Paths
• Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
• Shortcutting for Negative-Weight Shortest Path
• Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
• Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
• Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation
• Deterministic Padded Decompositions and Negative-Weight Shortest Paths
• Acceleration for Distributed Transshipment and Parallel Maximum Flow
• Faster Weak Expander Decompositions and Approximate Max Flow
• A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
• Limitation of Quantum Walk Approach to the Maximum Matching Problem
• A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
• Reviving Thorup's Shortcut Conjecture
• Efficient Network Reconfiguration by Randomized Switching
• Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
• Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
• Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
• Minimum s--t Cuts with Fewer Cut Queries
• Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
• Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
• All-Pairs Minimum Cut using O(n^7/4) Cut Queries
• Near-Optimal Fault-Tolerant Strong Connectivity Preservers
• FORWARD: A Feasible Radial Reconfiguration Algorithm for Multi-Source Distribution Networks
• Accelerated Price Adjustment for Fisher Markets with Exact Recovery of Competitive Equilibrium
• Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
• A Faster Directed Single-Source Shortest Path Algorithm
• Constant time enumeration of perfect bipartite matchings
• Reusing Samples in Variance Reduction
• A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
• Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
• Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
• Deterministic Almost-Linear-Time Gomory-Hu Trees
• Maximum flow problem [wikipedia]
• Shortest path problem [wikipedia]

Discussions

• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time [hn, 230 points, 40 comments]
• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time [hn, 7 points, 0 comments]
• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time [lobsters, 4 points, 0 comments]
• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time [hn, 2 points, 0 comments]

Related

• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
• A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
• Partial Implementation of Max Flow and Min Cost Flow in Almost-Linear Time
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected\n Graphs, and its Multicommodity Generalizations
• Nearly Maximum Flows in Nearly Linear Time