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

Li Chen; Rasmus Kyng; Yang P. Liu; Richard Peng; Maximilian Probst Gutenberg; Sushant Sachdeva

Source-linked AI summary

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

Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

arXiv:2203.00671v2Mar 1, 2022cs.DS

TL;DR

General-graph min-cost flow lacked an almost-linear-time algorithm. The paper reduces flow computation to dynamic approximate minimum-ratio cycle problems and obtains almost-linear-time exact min-cost and maximum-flow algorithms.

Problem
General-graph min-cost flow had running-time bounds far from linear despite prior algorithmic progress.
Source: §1 · p. 4
Method
A potential-reduction IPM builds flows through slowly changing undirected minimum-ratio cycle instances supported by a randomized dynamic data structure.
Source: §1.2 · pp. 6–7
Results
Exact min-cost flow runs in m^1+o(1) log U log C time, while maximum flow runs in m^1+o(1) log U time, both with high probability.
Source: §1 · pp. 4–5
Takeaways & Limitations
The work establishes almost-linear-time exact flow algorithms for general directed graphs.
Source: §1 · pp. 4–5
The precise data structure initially works only against oblivious adversaries, requiring additional treatment for adaptive instance sequences.
Source: §1.2 · p. 7, §2.5 · p. 17

Abstract

from arXiv · show

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.

1 Introduction

The paper presents the first almost-linear-time exact min-cost flow algorithm in general graphs, with a reduction to stable undirected minimum-ratio cycle problems and dynamic graph data structures. It also develops broad applications and extensions to convex flow objectives.

1 Introduction

m1+o(1) log U log C time computes exact min-cost flow with high probability, and m1+o(1) log U time computes maximum flow.The max-flow result follows by direct reduction from min-cost flow.Source: §1 · p. 5

1.1 Applications

The results yield almost-linear algorithms for bipartite matching, shortest paths with negative-cycle detection, connectivity problems, directed min-cut, and approximate sparsest cuts.They also extend to edge-separable convex objectives, covering regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression.Source: §1.1 · p. 5, §1.3 · p. 8

1.2 Key Technical Contributions

A new ℓ1 interior-point method reduces min-cost flow to m1+o(1) stable undirected minimum-ratio cycle instances, while randomized structures solve them in amortized mo(1) time.The data structures combine hidden stable-flow chasing with dynamic spanners and explicit embeddings, including adaptive update sequences.Source: §1.2 · pp. 6–7

1.3 Paper Organization

The paper develops its min-cost flow algorithm through the ℓ1-IPM, dynamic spanner, and stable-cycle data structure, then extends the analysis to general edge-separable convex objectives.The main min-cost flow construction occupies Sections 4–9, while Section 10 treats nonlinear objectives.Source: §1.3 · pp. 7–8

2 Overview

This section develops a dynamic data-structure framework for approximate undirected minimum-ratio cycle computations, combining low-stretch decompositions, core graphs, spanners, recursive maintenance, and adaptive rebuilding. It also presents dynamic spanner-maintenance procedures that preserve sparse, short-path embeddings with low amortized recourse under graph updates.

2 Overview

The overview reduces min-cost flow to m1+o(1) approximate undirected minimum-ratio cycle computations, maintained with mo(1) amortized update time for an m1+o(1) total runtime.The construction uses a recursive graph hierarchy, online handling of adaptive updates, and dynamic spanners to reduce edges at each level.Source: §2 · p. 8

2.1 Computing Min-Cost Flows via Undirected Min-Ratio Cycles

Using ℓ1 subproblems in a potential-reduction interior-point method preserves high-accuracy convergence while yielding cycle-form optimal solutions and tolerating mo(1)-factor approximations.The witness circulation f*−f provides κ = eΩ(1), so approximate cycle solutions still make m−o(1) progress per iteration.Source: §2.1 · pp. 9–10

2.2 High Level Overview of the Data Structure for Dynamic Min-Ratio Cycle

A dynamic hierarchy maintains mo(1) approximate min-ratio cycles through spanning trees, vertex-reducing core graphs, edge-reducing spanners, and rebuilding strategies tailored to the adaptive witness circulation.Against oblivious updates, the construction achieves mo(1) query time; for the adaptive IPM, it exploits the witness form f*−f and controls stretch and failure-triggered rebuilds.Source: §2.2 · pp. 11–13

2.3 Building Core Graphs

The core-graph construction contracts low-stretch forests and uses portal routing to reduce vertices to eO(m/k) while preserving the witness circulation within an mo(1) stretch factor.It supports eO(m/k) edge updates before rebuilding and assigns core-graph lengths and gradients so solutions lift back to the original graph with controlled quality.Source: §2.3 · pp. 13–14
Low-stretch decompositions construct sampled core graphs whose solutions provide approximate solutions for the original graph while controlling recursive stretch accumulation.A single decomposition can incur eO(k) stretch per level, so multiple weighted decompositions achieve eO(1) average stretch and sampling eO(1) of them suffices.Source: §2.3 · p. 16

2.4 Maintaining a Branching Tree Chain

The branching tree chain recursively combines core graphs and spanners, achieving m^o(1) total stretch, recourse, and approximation factors with suitable parameters.It samples B = O(log n) decompositions, recurses for d levels with k^d = m, and rebuilds deeper levels when update thresholds are reached.Source: §2.4 · pp. 16–17

2.5 Going Beyond Oblivious Adversaries by using IPM Guarantees

IPM witness-flow guarantees overcome the oblivious-adversary limitation by tracking slowly changing width and recomputing decompositions only when approximation quality fails.Each recomputation reduces the width’s ℓ1 norm by a constant factor, so only eO(1) recomputations are needed, adding an eO(1) runtime factor.Source: §2.5 · pp. 17–18

2.6 The Rebuilding Game

The rebuilding game converts hidden-width failures into a level-rebuilding strategy that processes T cycle updates in O(m^o(1)(m + T)) total cost.A losing rebuild halves an overly large level width, enabling repeated level tests and yielding amortized m^o(1) cost per cycle update in the stable-flow setting.Source: §2.6 · pp. 19–20

2.7 Dynamic Embeddings into Spanners of Decremental Graphs

The dynamic spanner construction maintains sparse, low-recourse spanners with short explicit embeddings and amortized update time k m^o(1), including under vertex splits.A static construction partitions the graph into expanders, sparsifies them by sampling, and uses dynamic shortest paths to obtain embedding paths.Source: §2.7 · pp. 20–21
The constructed spanner has nearly linear size and embedding paths of length m^{o(1)}, because sampled sparsifiers are sparse and each vertex participates in at most e^{O(1)} auxiliary graphs.The spanner is formed by taking the union of the sampled graphs and their embeddings.Source: §2.7 · p. 21
After an update batch, the algorithm builds a graph on touched vertices, sparsifies it, and adds the corresponding pre-images to repair invalid embedding paths.Only paths intersecting the touched-vertex set require repair, whose size is at most 2|U|.Source: §2.7 · pp. 21–22
The repair causes e^{O}(|U|) spanner recourse and increases embedding-path lengths by only an e^{O(1)} factor, with the affected auxiliary-path set also of size e^{O}(|U|).Standard batching yields m^{o(1)} amortized recourse per update and comparable amortized path-set size.Source: §2.7 · p. 22
With vertex congestion bounded by γ_cΔ_max(G/F_i), the auxiliary graph has maximum degree γ_cΔ_max(G/F_i), so sparsifier computation takes |U|^{m^{o(1)}}k time and k^{m^{o(1)}} amortized time per update.The congestion bound follows from expander embeddings, shortest-path data structures, and batching; γ_c=m^{o(1)}.Source: §2.7 · pp. 22, 24

3 Preliminaries

This section establishes notation for directed multigraphs, flows, paths, embeddings, and dynamic graphs, then records low-stretch tree and dynamic-tree tools used by the algorithms.

Graphs

Graphs use implicitly directed multigraph edges, with incidence matrix B; a flow f routes demand d when B^T f = d.For edge e=(u,v), b_e denotes the demand vector for one unit routed from u to v.Source: §3 · p. 24

Dynamic Graphs

Dynamic graphs evolve through batched edge insertions, deletions, and encoded vertex splits, with stages and polynomially bounded total update-encoding size.Vertex splits are implemented by deleting and reinserting incident edges, with the split-off vertex no larger in degree than the original.Source: §3 · pp. 24–25

Paths, Flows, and Trees

Path and forest notation represents unit flows along tree paths, while low-stretch spanning trees provide efficiently constructible trees with polylogarithmic average stretch.The path-flow vectors compose additively across consecutive path segments, and the stretch convention ensures values are at least one.Source: §3 · p. 25

Graph Embeddings

Graph embeddings map each source edge to a path in the target graph and characterize edge congestion, vertex congestion, path length, flow vectors, and edge preimages.The embedding flow for an edge e=(u,v) routes one unit from u to v, satisfying B^T Π(e)=b_e.Source: §3 · pp. 25–26

Dynamic trees

Dynamic trees support amortized eO(1) updates and queries for tree edges, path inner products, signed flows, positive flows, and edge-gradient detection.Detect runs in eO(|S(t)|) time and identifies when gradients and lengths must change in the interior-point method.Source: §3 · p. 26

4 Potential Reduction Interior Point Method

The section develops a primal-only potential-reduction interior-point method for min-cost flow using an x^-α barrier, approximate minimum-ratio cycles, and slowly changing lengths and gradients. It establishes near-optimality after eO(mκ^-2) iterations and gives linear-time initialization and exact-solution recovery.

4 Potential Reduction Interior Point Method

The method replaces the logarithmic barrier with x^-α, where α = 1/(1000 log mU), because quasipolynomial length bounds are unavailable for the logarithmic barrier.The algorithm assumes knowledge of F*, which can be obtained by binary search.Source: §4 · p. 27
After eO(mκ2) iterations, the method obtains c^T f^(t) ≤ c^T f* + (mU)^−10.At each iteration, for Δ satisfying B^TΔ = 0 and eĝ^TΔ/eLΔ_1 ≤ −κ, it uses η = κ^2/(50 · |eĝ^TΔ|).Source: §4 · p. 28

4.1 One Step Analysis

An approximate minimum-ratio cycle decreases the potential by Ω(κ^2) per iteration, while a m^o(1)-approximation yields κ ≥ m^-o(1) and termination in m^1+o(1) iterations.The same guarantee supports data structures because the iteration problems are not fully adaptive.Source: §4 · p. 28, §4.1 · p. 30

4.2 Stability Bounds

Lengths and gradients remain stable under the updates: residual costs change by at most a 1/m factor per iteration, and bounded residual-capacity changes preserve lengths and gradients up to controlled multiplicative error.These stability bounds enable approximate length and gradient representations to be updated only m^o(1) times per iteration across the algorithm.Source: §4 · p. 28, §4.2 · pp. 32–33

4.3 Initial and Final Point

The construction initializes an O(m)-edge augmented instance with potential at most 200m log mU and recovers an exact optimum or infeasibility in O(m) time.For perturbed costs, rounding a solution within 1/(12m^3U^3) of optimum gives an optimal original flow with probability at least 1/2.Source: §4.3 · p. 34

5 Decremental Spanner and Embedding

This section develops decremental algorithms that maintain sparse graph structures together with short, bounded-size, low-congestion path embeddings under updates. It presents multilevel batching and static sparsification techniques, including expander decomposition, edge sampling, and decremental expander path queries, with low recourse, almost-sublinear update guarantees, and high-probability correctness.

5 Decremental Spanner and Embedding

Theorem 5.1 maintains H as a subgraph of G with eO(n) edges, while embedding G into H with length (γl)O(L) and vertex congestion (γc)O(L)∆max(G).Here γl and γc equal exp(O(√log m · log log m)).Source: §5 · p. 34
The algorithm reports a changed-edge set D(t) whose amortized size is roughly bounded by the number of updates in batch U(t), enabling low-recourse re-embedding.The guarantee is measured by update count rather than the potentially larger encoding size of U(t).Source: §5 · pp. 34–35
Initialization takes eO(mγl), while processing batch U(t) takes amortized eO(Enc(U(t))·n1/L(γcγl)O(L)∆max(G)) time with probability at least 1 − n−C.Choosing L = (log m)1/4 makes runtime, embedding lengths, and amortized |D(t)| all O(γs), where γs = exp(O(log3/4 m log log m)).Source: §5 · pp. 34–35

5.1 The Algorithm

The multilevel algorithm maintains H0,…,HL and corresponding embeddings, periodically recomputing shallower levels less often while deeper levels repair embeddings affected by deletions and vertex splits.Affected embedding paths are projected onto recently touched vertices, sparsified in an auxiliary graph J, and translated back into the maintained hierarchy.Source: §5.1 · pp. 35–36
The initialization procedure Sparsify(G) produces a sparse H0 and an embedding with vertex congestion at most 2γc∆max(G), length at most γl, and running time eO(mγl).The generalized Sparsify(H′, J, ΠJ→H′) similarly returns a sparsifier with eO(|V(J)|) edges in time eO(|E(J)| · γl), with high probability.Source: §5.1 · pp. 35–36
The decremental algorithm maintains a sparsifier H with at most eO(n) edges, eO(n^(1/L)) amortized edge changes per update, and the stated bounds on auxiliary data structure size, initialization, and update time.Its success probability follows by a union bound over the randomized Sparsify calls.Source: §5.1 · pp. 39–40

5.2 Implementing the Sparsification Procedure

Sparsify returns a sparsifier with eO(|V(J)|) edges and an embedding, in eO(|E(J)| · γ_l) time, with probability at least 1 − n^-C.The construction first decomposes J into near-uniform-degree expanders, samples edges, and embeds unsampled edges using decremental expander path queries while removing overly congested edges.Source: §5.2 · pp. 40, 42
The sampled local graphs remain ψ/4-expanders, each embedding loop embeds at least a 1/16-fraction of remaining edges, and the resulting composition satisfies the stated congestion and length bounds.These properties support at most O(log(m)) embedding iterations and complete the runtime and correctness analysis of Theorem 5.5.Source: §5.2 · pp. 42–44

6 Data Structure Chain

Section 6 develops a dynamic data-structure chain for maintaining approximate undirected minimum-ratio cycles under hidden stable-flow chasing updates. It combines low-stretch decompositions, multiplicative-weights tree distributions, sparsified core graphs, and recursive branching chains.

6 Data Structure Chain

The main data structure maintains approximate minimum-ratio cycles under hidden stable-flow chasing updates, using O(log n)^d spanning trees and succeeding with high probability over τ stages.Its total runtime is m^o(1)(m + Q), and queries return a cycle represented by m^o(1) tree paths and off-tree edges.Source: §6 · p. 45

6.1 Dynamic Low-Stretch Decompositions (LSD)

Dynamic low-stretch decompositions maintain a rooted forest with controlled stretch, few growing components, bounded piece volume, and total runtime eO(m).New edges have stretch 1, while after q total update-encoding size the forest has O(q log^2 n) additional components and edge stretch is bounded by O(kγLSST log^4 n).Source: §6.1 · pp. 46–47

6.2 Worst-Case Average Stretch via Multiplicative Weights

A deterministic multiplicative-weights procedure constructs spanning trees and rooted forests whose uniform distribution gives eO(1) average stretch, in eO(mk) time.A fixed flow has average stretch O(γLSST log^2 n) under a sampled tree distribution, enabling a high-probability good tree among O(log n) samples.Source: §6.2 · p. 47

6.3 Sparsified Core Graphs and Path Embeddings

Sparsified core graphs contract forest components while preserving lengths and gradients, reduce each core to at most mγs/k edges, and retain embeddings for recursive processing.The construction is designed for dynamic maintenance because edge deletions from the forest do not change core lengths or gradients.Source: §6.3 · pp. 47–48

6.4 Full Data Structure Chain

The full branching tree-chain recursively reduces graphs by factors of k across d levels, branches into O(log n) sampled trees, and rebuilds levels at approximately m/k^i update intervals.This yields O(log n)^d tree-chains corresponding to spanning trees of the top-level graph; Section 7 first proves a weaker guarantee that Section 8 later strengthens.Source: §6.4 · pp. 48–49

7 Routings and Cycle Quality Bounds

This section develops and maintains dynamic branching tree-chains and sparsified core graphs for routing and circulation-passing updates. It establishes witness and length bounds, update and rebuild strategies, and high-probability running-time guarantees for the resulting structured circulations.

7 Routings and Cycle Quality Bounds

Theorem 7.1 maintains an O(log n)-branching tree chain and outputs a circulation Δ represented by exp(O(log^7/8 m log log m)) off-tree edges and tree paths, with high-probability runtime (m + Q)m^o(1).The output satisfies B^TΔ = 0, and branching-tree levels can be rebuilt in m^1+o(1)/k_i time.Source: §7 · p. 49

7.1 Passing Circulations and Length Upper Bounds Through a Tree-Chain

A valid pair consists of a circulation c and positive length upper bounds w satisfying |ℓ_e c_e| ≤ w_e, and the section passes these objects down the tree-chain.The construction first transfers valid pairs to core graphs and then to sparsified core graphs while preserving validity.Source: §7.1 · p. 50, §7.1.1 · p. 50, §7.1.2 · p. 53

7.1.1 Passing Circulations and Length Upper Bounds to the Core Graph

Passing a valid pair to a core graph preserves circulation and length-bound validity, while dynamic maintenance provides bounded recourse, small widths with high probability, and total time eO(mk).The core-graph construction uses decremental forests and maintains O(log n) tree instances under bounded update encoding.Source: §7.1.1 · pp. 50–52

7.1.2 Passing Circulations and Length Upper Bounds to the Sparsified Core Graph

Passing a valid pair to a sparsified core graph preserves validity and increases total update size by at most m^o(1), enabling transitions between consecutive tree-chain levels.The dynamic sparsified-core construction guarantees low recourse, hidden stable-flow chasing updates, and small widths for its maintained graphs.Source: §7.1.2 · pp. 53–54
The sparsified-core maintenance algorithm runs in total time eO(m^k · γ_r).Dynamic spanners are applied after splitting core-graph vertices so their maximum degree is Θ(k), with per-spanner time O(m^kγ_r).Source: §7.1.2 · pp. 54, 58
Sparsified core graphs are maintained under vertex splits and edge updates, resolving high-degree core-graph changes through low-recourse dynamic spanners.The construction represents updates with total encoding size O(m^o(1) · Σ_t Enc(U(t))) and maintains sparse core graphs while satisfying the required flow-chasing conditions.Source: §7.1.2 · pp. 54, 56, 57

7.1.3 Maintaining a Branching Tree-Chain

A dynamic branching tree-chain explicitly maintains the recursively defined graph hierarchy from top-level gradients, lengths, hidden circulations, and widths.The algorithm maintains previous rebuild times across levels and constructs the tree-chain when the level-wise quantities satisfy the recursive definitions.Source: §7.1.3 · p. 58
m^(1/d)eO(γ_sγ_r)O(d)(m + Q) is the total running time for the branching tree-chain algorithm, which succeeds with high probability.The broader construction can also be modified to support vertex splits because its component data structures support them.Source: §7.1.3 · p. 58
The data structure must be periodically rebuilt because each Lemma 7.8 instance supports only up to m/(k log2 n) updates while the graph has at most m edges.Rebuilding all levels i ≥ i0 is triggered when a level-i0 graph accumulates approximately m/k^i0 updates, with rebuilding costs amortized over dynamic updates.Source: §7.1.3 · p. 58
At every level i, the maintained hierarchy contains at most O(log n)^i graphs at any stage.Source: §7.1.3 · p. 58
Algorithm 5 maintains the branching tree-chain with d = log_1/8 n levels, reduction factor k = m^1/d, and B = O(log n) sparsified core graphs.It initializes the level-zero graph, supports rebuilding from a specified level and stage, and adds sparsified graphs to the next level.Source: §7.1.3 · p. 59

G .DynamicSparseCore(G, U(t)

The section bounds dynamic sparse-core rebuilding and establishes how tree-chains yield approximate minimum-ratio cycles. It maintains cycle-gradient information and length overestimates while achieving the stated quality and runtime guarantees.

G .DynamicSparseCore(G, U(t)

Rebuilding level i0 is amortized over updates, and setting k = m^1/d yields the overall runtime bound.Rebuilds occur only after sufficiently many updates to level i0, limiting their total cost.Source: G .DynamicSparseCore(G, U(t) · p. 59

7.2 Finding Approximate Min-Ratio Cycles in a Tree-Chain

The tree-chain algorithm explicitly maintains fundamental-chain-cycle gradients and length overestimates, returning the cycle with the best quality ratio.It updates only m^o(1) cycle gradients per iteration on average and uses overestimates because exact dynamic lengths may be expensive.Source: §7.2 · pp. 60–61
Core-graph cycles preserve the total gradient of their lifted fundamental chain cycles, while the maintained lengths overestimate the corresponding original-cycle lengths.These properties are established by Lemmas 7.13 and 7.14 through repeated cycle lifting.Source: §7.2 · p. 61
With the stated parameter choices, the extracted cycle achieves quality κ = exp(−O(log^7/8 m log log m)).The branching tree-chain is maintained dynamically, and the resulting quality follows from the tree-chain guarantee.Source: §7.2 · p. 64

8 Rebuilding Data Structure Levels

This part develops a rebuilding-game model for hidden multilevel weights and a deterministic strategy with almost-linear total fixing cost. The analysis yields an amortized cost bound and, combined with Theorem 7.1, a dynamic min-ratio-cycle data structure with the stated total runtime.

8 Rebuilding Data Structure Levels

The rebuilding game represents each successful cycle as a round and handles failures by adversarially forced or voluntary fixes across levels.The adversary chooses a hidden weight W^(t) with log W^(t) ∈ (−K, K), and fixing level i rebuilds every level j ≥ i.Source: §8 · pp. 64–65
The deterministic strategy completes T rebuilding-game rounds in time O(CrK^d/γ_g (m + T)).The game models adversarially hidden weights, while fixes rebuild all levels at or above the selected level and cost C_rm/k^i.Source: §8 · pp. 65–66
Algorithm 6 tracks round and fixing counts, declaring wins at scheduled rebuild thresholds and losses at the largest eligible level when the adversary forces a fix.A win resets counts for rebuilt levels, while losses are limited by the 2K threshold used to select levels.Source: §8 · p. 66

8.1 Analyzing the rebuilding game algorithm

The analysis maintains an invariant that every fixing step is explained either by a larger lower-level weight or by the absence of a sufficiently large higher-level weight.These are Cases (A) and (B); repeated Case (B) reduces the selected level’s weight, while the 2K threshold prevents excessive rebuilding before moving downward.Source: §8.1 · pp. 66–67
Lemma 8.5 proves fix_0 < 2K always, giving tight control over adversarial fixing steps because higher-level counts are also bounded by 2K.The proof uses prefix-maximizing levels and an induction hypothesis tracking the correctness of each fix_i counter.Source: §8.1 · pp. 67–68
The case analysis establishes the rebuilding-game induction invariant, including the required weight reduction when a LOSS occurs at a currently active level.For LOSS at level i, rebuilding removes activity at levels j ≥ i; when i ∈ I(s), it also ensures a reduction in W(prev(s+1)_i) relative to W(prev(s)_i).Source: §8.1 · p. 69
The rebuilding game has total cost O(KC_r d/γ_g (T + m)) by amortizing WIN fixes, LOSS-counter resets, and bounded leftover counter costs.WIN fixes cost at most C_r/γ_g per round per level, while Lemma 8.5 bounds each fix_j counter by 2K and controls unrecovered LOSS costs.Source: §8.1 · pp. 70–71

8.2 Dynamic Min-Ratio Cycle Using the Rebuilding Game

(m+Q) exp(O(log^(7/8) m log log m)) total runtime follows for the dynamic min-ratio-cycle data structure.The construction combines Theorem 7.1 with the rebuilding-game strategy of Lemma 8.3 and implements tree-supported cycle updates in amortized m^o(1) time.Source: §8.2 · p. 71

9 Computing the Min-Cost Flow via Min-Ratio Cycles

This section presents MinCostFlow, which maintains approximate lengths and gradients while dynamically updating tree structures and min-ratio cycles. Its hidden stable-flow chasing analysis establishes high-accuracy convergence and m^{1+o(1)} total runtime, yielding Theorem 1.1.

Implementation

The implementation updates approximate lengths ℓ(t) and gradients g(t), while D(HSFC) dynamically maintains trees and a min-ratio cycle under hidden stable-flow chasing updates.When accumulated edge changes trigger updates, the algorithm refreshes ℓ(t) and g(t), rebuilds D(HSFC) when the residual cost changes substantially, and applies returned cycle updates through dynamic trees.Source: §9 · pp. 71–72

Stability

The maintained lengths, gradients, and residual-cost estimate remain approximately correct throughout execution, with the residual cost changing by at most a 1+ε factor between rebuilds.The stability proof uses Detect’s per-tree guarantees and resets the residual-cost estimate every floor(εm) iterations.Source: §9 · p. 73

Hidden stable-flow chasing

Defining c(t)=f*−f(t) and w(t)=50+|ℓ(t)∘c(t)| makes the algorithm’s quantities satisfy hidden stable-flow chasing, so D(HSFC) succeeds with high probability.This property supplies the conditions needed to apply the main interior-point analysis and bound the iteration count.Source: §9 · pp. 73–74

Main result

MinCostFlow computes a min-cost flow to high accuracy in eO(mκ^-2α^-2) iterations and, after initialization and rounding, supports Theorem 1.1’s exact result.The algorithm terminates when c^T f − F* ≤ (mU)^-10; initial and final processing are supplied by Lemmas 4.11 and 4.12.Source: §9 · pp. 73–75

Runtime

The total update-batch size is bounded using the scaled cycle progress and Detect’s per-update contribution, enabling D(HSFC) and the remaining dynamic-tree operations to run in m^{1+o(1)} time.The runtime combines Q=Σ_t|U(t)|≤m^{1+o(1)} with ε^-1(m+Q)m^{o(1)} time for D(HSFC).Source: §9 · p. 75

10 General Convex Objectives · A Previous Works

This section extends the framework to single-commodity flows with general decomposable convex objectives, developing almost-linear-time approximation algorithms based on self-concordant barriers and a potential-based method. It applies these results to normed flows, isotonic regression, entropy-regularized optimal transport, and matrix scaling, while briefly reviewing prior work on max-flow and min-cost-flow algorithms.

10 General Convex Objectives

The framework minimizes h(f)=∑_e h_e(f_e) over flows satisfying B^T f=d, for convex edge functions h_e.The method assumes access to gradients and Hessians of ν-self-concordant barriers for the epigraph domains of the edge objectives.Source: §10 · p. 75, §10.1 · p. 75

10.1 General Setup for General Convex Objectives

Under Assumption 10.2, the algorithm outputs a feasible flow in m^{1+o(1)} time with h(f)≤min_{B^T f*=d}h(f*)+exp(−log^C m) for any fixed constant C>0.The assumptions include quasipolynomial bounds, efficiently computable barrier derivatives, a feasible initialization, and controlled Hessians.Source: §10.1 · p. 76
The algorithm eliminates each epigraph variable by minimizing its barrier coordinate, proves α^{-1}ζ_e/4 is self-concordant, and uses phased potential reduction with approximate minimum-ratio cycles.Each phase approximately reduces the potential until the duality gap threshold is met, then doubles the path parameter; lazy updates preserve the almost-linear runtime.Source: §10.1 · pp. 77, 78, 80, 82

10.2 Applications: p-Norms, Entropy-Regularized Optimal Transport, and Matrix Scaling

The result yields algorithms for normed flows, isotonic regression, entropy-regularized optimal transport, and matrix scaling; p-norm flows allow sums of arbitrarily weighted power terms with powers at most e^{O(1)}.For p-norm flows, the edge objectives are sums of e^{O(1)} p-norm terms and demands have entries bounded by exp(log^{O(1)} m).Source: §10.2 · p. 82
For separable convex objectives satisfying the stated conditions, the framework computes a feasible flow within exp(−logC m) of optimum in m1+o(1) time.The guarantee applies for any constant C > 0 under the specified bounds on exponents, weights, and objective components.Source: §10.2 · p. 82
The method yields m1+o(1)-time ℓp isotonic regression on directed acyclic graphs by reducing the dual problem to a q-norm flow with nonnegative edge flows.The reduction adds an auxiliary vertex and convex edge functions, then recovers the desired vertex potentials from a high-accuracy flow solution.Source: §10.2 · pp. 82–83
Entropy-regularized optimal transport with objective c_e f_e + w_e f_e log f_e is solvable in m1+o(1) time to additive exp(−logC m) accuracy.The construction handles the linear and entropy terms with self-concordant barriers and applies the general convex-objective theorem.Source: §10.2 · pp. 83–84
For matrices with polynomially bounded nonzero entries, the algorithm computes positive diagonal scalings in nnz(A)1+o(1) time whose row and column sums are within exp(−logC n) of 1.Matrix scaling is connected to entropy-regularized optimal transport through duality and the KKT relation f = W exp(Bz).Source: §10.2 · pp. 83–84

A Previous Works

The previous-works discussion provides a brief, explicitly incomplete overview of approaches to max-flow and min-cost-flow problems, directing readers to Goldberg and Tarjan for broader coverage.The authors note that the literature is vast and invite pointers for future updates.Source: A Previous Works · p. 93

A.1 Maximum Flow … B.1 Proof of Lemma 4.12

The paper situates its flow algorithms among augmenting-path, push-relabel, pseudo-flow, and numerical approaches, emphasizing dynamic tree-like data structures and undirected minimum-ratio cycles. It also relates minimum-cost flow to prior cycle and scaling methods and proves a reduction using an auxiliary vertex with penalized edges.

A.1 Maximum Flow

Strongly polynomial maximum-flow algorithms primarily use augmenting paths, push-relabel methods, or pseudo-flows.These three approaches are presented as the main longstanding categories.Source: §A.1 · p. 94
Dynamic trees enable quick bottleneck identification and support strongly polynomial max-flow runtimes of eO(nm), near the flow-decomposition barrier.The paper’s approach instead uses dynamic tree-like structures to identify more complicated approximate bottlenecks motivated by interior-point methods.Source: §A.1 · p. 94
Numerical flow methods split between faster approximation algorithms and reduced-iteration high-accuracy methods, including eO(mϵ−1) approximate max-flow.Interior-point progress reduced iteration complexity from m1/2 to n1/2, or m1/3+o(1) for unit-capacity max-flow.Source: §A.1 · pp. 94–95
The paper’s method differs from recent electrical-flow data structures by starting from dynamic tree-like structures and using undirected minimum-ratio cycles, requiring Ω(m) iterations.Later methods commonly use m1/2 or n1/2 iterations, whereas this approach modifies interior-point methods toward dynamic trees.Source: §A.1 · p. 95

A.2 Minimum-Cost Flows

Minimum-cost flow research spans the Hungarian algorithm, network simplex, out-of-kilter, strongly polynomial, and scaling algorithms, with prior strongly polynomial runtimes around eO(nm).Prior cycle methods use directed minimum-mean cycles, while the paper uses closely related undirected minimum-ratio cycles.Source: §A.2 · p. 95
Previous scaling arguments generally handle either capacities or costs, while runtimes beyond the Θ(nm) flow-decomposition barrier previously came through interior-point methods.Scaling algorithms achieve runtimes of the form eO(m1.5 log U) and also extend to non-bipartite matching.Source: §A.2 · p. 95

B.1 Proof of Lemma 4.12

Lemma 4.12 constructs an auxiliary graph with one vertex and at most m+n edges, adding directed edges that route the initial demand discrepancy.New edges receive capacities based on discrepancy, initial flow values equal those discrepancies, and costs are set to 4mU2; if the original graph is feasible, optimal flow uses none of these edges because one unit costs 4mU2 while original-edge costs lie within ±mU2.Source: §B.1 · pp. 95–96

B.2 Proof of Theorem 5.11

This section proves Theorem 5.11 by recursively decomposing graphs using an expander-decomposition theorem from [SW19] and establishing edge-count invariants. The proof shows each initialized graph G_i has at most 2^i n edges, while the supplied passage begins the minimum-degree argument for i > 0.

Prerequisite expander decomposition

The expander decomposition from [SW19] partitions an unweighted undirected m-edge graph into ψ-expanders with ψ = Ω(1/log^3(m)), leaves at most m/4 inter-set edges, runs in O(m log^7(m)) time, and succeeds with probability at least 1 − n^−C.The guarantee holds for any fixed constant C chosen before the algorithm starts.Source: §B.2 · p. 96

Recursive decomposition

Algorithm 8 is run to obtain the graphs Gi as required by Theorem 5.11.Gi denotes the graph after adding 2i self-loops to each vertex.Source: §B.2 · p. 96

Edge-count invariant

Each initialized graph G_i contains at most 2^i n edges, proved inductively from the base case and the expander decomposition’s bound on edges crossing its parts.The proof uses that graphs only have edges deleted after initialization; for the recursive step, at most 2^(i+1)n/4 = 2^(i−1)n crossing edges remain to form G_{i−1}.Source: §B.2 · p. 96

Minimum-degree property

The proof then begins establishing the minimum-degree property of each G_i for i > 0 by relating vertex degrees within expander parts to the corresponding induced subgraphs.The supplied passage truncates this argument after introducing the degree identity.Source: §B.2 · p. 97

B.3 Proof of Lemma 6.5

The proof constructs a low-stretch forest from branch-free roots by deleting congestion-ordered edges between adjacent roots, then maintains valid stretch overestimates dynamically using a heavy-light tree and decomposition-based initialization. A reduction from weighted to unweighted edge copies extends the argument to general weights.

B.3 Proof of Lemma 6.5

For branch-free roots R, the forest F_T(R,π) deletes the π-smallest edge on each path between adjacent roots, yielding |R| components with unique roots.Branch-freeness guarantees exactly |R|−1 adjacent root pairs, while each component contains one root.Source: §B.3 · p. 97
Ordering tree edges by increasing congestion makes F_T(R,π) have low total stretch.This ordering is the valid permutation established by Lemma B.6.Source: §B.3 · p. 97
The proof initializes O(m/k) roots using the tree decomposition [ST04], preserving branch-freeness and bounding each component’s adjacent edge weight.Uniform weights yield the required degree bound for item 4 of Lemma 6.5.Source: §B.3 · pp. 98, 101
A heavy-light-derived auxiliary tree of height O(log^2 n) adds ancestors of updated endpoints, keeping roots branch-free while assigning each edge to only O(log^2 n) roots.This supports decremental forest maintenance and valid stretch overestimates under edge insertions and deletions.Source: §B.3 · pp. 98, 99, 101
For weighted graphs, replacing each edge by ⌈m v_e/||v||_1⌉ unweighted copies preserves the relevant tree and forest stretches, allowing the unweighted proof to establish Lemma 6.5.The resulting graph has at most 2m edges.Source: §B.3 · p. 100

B.4 Proof of Lemma 6.6 · C Cost and Capacity Scaling for Min-Cost Flows

The proof constructs multiplicative-weight sequences and associated trees, forests, and stretch estimates, then bounds their growth to establish the desired inequality. Cost and capacity scaling reduces exact min-cost flow to polynomially bounded instances, yielding an almost-linear-time algorithm when such instances can be solved efficiently.

B.4 Proof of Lemma 6.6

The proof constructs t = 10kW log2 n = eO(k) weight vectors, trees, forests, and stretch overestimates sequentially via Lemma 6.5.Here W = O(γLSST log2 n), and the construction uses multiplicative weight updates.Source: §B.4 · p. 101
The distribution λ is defined uniformly over the indices {1, . . . , t}.This distribution is part of the final construction used in the proof.Source: §B.4 · p. 102
The proof bounds ∥v_i∥_1 inductively from the initial value ∥v_1∥_1 = m, using e^x ≤ 1 + 2x for 0 ≤ x ≤ 0.1.The condition e^kW = 0.1t enables iterative application of the inequality, with the stretch bound supplying the first inequality.Source: §B.4 · p. 102
Taking logarithms of the resulting norm bound establishes the desired bound (25).The argument also relates the target bound to ∥v_{t+1}∥, although v_{t+1} is defined only for the proof and is never used by the algorithm.Source: §B.4 · p. 102

C Cost and Capacity Scaling for Min-Cost Flows

Cost and capacity scaling reduces exact min-cost flow with integral demands, costs, and lower/upper capacities bounded by U and C to O(log mU log C) instances with polynomially bounded parameters.If algorithm A solves the bounded-parameter problem in T_A(m) time, the scaled algorithm runs in O(T_A(m) log m log mU log C) time.Source: C Cost and Capacity Scaling for… · p. 102
The reduction works through an equivalent min-cost circulation formulation and defines residual graphs with forward and reverse arcs carrying residual capacities and opposite costs.The circulation formulation has costs in {−C, . . . , C}^E and capacities in {1, . . . , U}^E.Source: C Cost and Capacity Scaling for… · pp. 102–103
TMCC(m, poly(m), poly(m)) = m1+o(1), so exact min-cost circulation with polynomially bounded costs and capacities is solvable in almost-linear time with high probability.TMCC denotes the exact-solution time for the circulation formulation on graphs with at most m arcs.Source: C Cost and Capacity Scaling for… · p. 103

C.1 Reduction to Polynomially Bounded Cost Instances

This section presents a cost-scaling scheme that reduces instances with costs in [-C, C] to O(log C) polynomially bounded-cost instances, while preserving exact solvability. It repeatedly halves ε-optimality until integrality certifies exact optimality, yielding O(TA(m, U) log C + m log C) time.

Reduction guarantee

O(TA(m, U) log C + m log C) time solves costs in [-C, C] using an algorithm for m^10-bounded costs and U-bounded capacities.Algorithm 9 reduces the problem to O(log C) rounded residual instances, giving TMCC(m, C, U) = O((TMCC(m, m^10, U) + m) log C).Source: §C.1 · pp. 103, 106

Exactness

After O(log C) iterations, ε falls below 1/(n + 1), and the resulting integral circulation is an exact minimizer.Lemma C.5 establishes that 1/(n + 1)-optimality certifies exact optimality for integral costs.Source: §C.1 · pp. 104, 106

Cost scaling

The update transforms an ε-optimal integral circulation into an ε/2-optimal circulation with an updated potential.This is the key invariant used to reduce the optimality tolerance geometrically.Source: §C.1 · p. 104
Each iteration solves a cost-rounded residual instance whose integer costs lie in {-m^10, ..., m^10}, then updates the primal flow and dual potential.Reduced costs are rounded to multiples of ε/m^8 and only relevant costs in [-ε, εm] are retained before rescaling.Source: §C.1 · pp. 104, 106

Dual recovery

A separate O(TMCC(m, C, U))-time routine extracts optimal dual variables from the computed primal optimum.It uses shortest-path distance labels in the residual graph and constructs the dual slack variables.Source: §C.1 · p. 105

C.2 Reduction to Polynomially Bounded Capacity Instances

Capacity scaling reduces min-cost flow instances with polynomially bounded costs and potentially large capacities to polynomially bounded-capacity instances. The scheme combines bottleneck-cycle approximation, capacity rounding, and repeated residual augmentations to recover an exact integral optimum with logarithmic overhead.

C.2 Reduction to Polynomially Bounded Capacity Instances

Capacity scaling solves capacities up to U exactly in O(T_A(m) log m log(mU) + m log m log(mU)) time, assuming an exact solver for m^40-bounded capacities.The reduction applies to m-edge graphs with costs in [-m^10,m^10] and integral capacities in [1,U].Source: §C.2 · pp. 106, 109
Repeatedly augmenting the integral circulation with an approximately optimal rounded residual circulation reduces the residual optimum geometrically, reaching exact optimality after O(log(mU)) iterations.Because the residual optimum is integral and therefore either 0 or at most -1, the final residual gap must be zero.Source: §C.2 · pp. 106, 109
An m^12-approximate integral solution can be computed in O(T_A(m) log m) time by finding a negative-cost cycle with maximum bottleneck through binary search over capacities.Each bottleneck check reduces to unit-capacity min-cost circulation, and the resulting cycle provides the approximation guarantee.Source: §C.2 · pp. 106–107
Given any B > 0, rounding edge capacities down to integral multiples of B/m20 and removing edges above mB yields a rounded optimum feasible in the original instance and a constant approximation.After scaling down by ⌈B/m20⌉, rounded capacities are positive integers at most m40, and the rounded-instance optimum can be recovered by integral scaling up.Source: §C.2 · p. 107

D Applications

The paper derives almost-linear-time algorithms for diverse flow-related applications, including generalized flows, optimal transport, shortest paths, connectivity, expanders, dynamic strong connectivity, and isotonic regression. These applications improve prior polynomial-time bounds and extend the framework to broader cost functions and graph settings.

Extensions of Theorem 1.1

The framework supports vertex capacities and costs, flow diffusion, and p-norm flows in near-linear time, including arbitrary weight matrices rather than only identity weights.Vertex capacities and costs follow by standard transformations, while diffusion is reduced by adding source and sink edges; p-norm flows are solved up to polynomially small error.Source: D Applications · p. 110

Bipartite Matching & Optimal Transport

Worker assignment runs in m1+o(1) log^2 U time, while entropically regularized optimal transport and matrix scaling are solvable in almost-linear time to high accuracy.The transport result is the first almost-linear-time algorithm for an optimal transportation plan and improves over current low-accuracy solvers; matrix scaling remains almost-linear even when scaling entries are exponentially large.Source: D Applications · pp. 110–111

Negative Shortest-Paths and Cycle Detection

The paper gives the first almost-linear-time algorithms for negative-weight single-source shortest paths and negative directed-cycle detection, with shortest paths running in m1+o(1) log W time.Negative cycles are recovered from a nonzero negative-cost circulation using Cut-Link Trees.Source: D Applications · p. 111

Connectivity & Gomory-Hu Trees

Flow reductions yield polynomial-factor runtime improvements across connectivity problems, including global and Steiner min-cuts, vertex min-cuts, connectivity oracles, and Gomory-Hu trees.The results include m1+o(1) time for Steiner min-cut, global vertex min-cut, and Gomory-Hu trees in unweighted graphs, plus (1 + ϵ)-approximation for weighted Gomory-Hu trees.Source: D Applications · p. 111

Directed Expanders

For φ ∈ (0, 1/O(log^2 m)], the expander algorithm runs in m1+o(1) time and either finds an O(φ log^2 m)-out-sparse cut or certifies a φ-expander.It improves over the previous eO(m/φ) bound for sparse graphs, and enables adaptive-adversary decremental strong connectivity in mn0.5+o(1) total time versus mn2/3+o(1).Source: D Applications · pp. 111–112

Isotonic Regression

On arbitrary DAGs, isotonic regression for every p ∈ [1, ∞) is solved to 1/poly(n) additive accuracy in almost-linear time in the number of edges.This can be substantially smaller than the transitive-closure size governing some prior algorithms.Source: D Applications · p. 112

Iterative Bregman Projections for Regularized Transportation Problems2014