Orlin's Maximum Flow Algorithm

Purpose: Compute maximum flow in $O(nm)$ time — for many years the best strongly polynomial bound, and the resolution of a long-standing open problem (James Orlin, 2013).

The result

Combined with the earlier King-Rao-Tarjan algorithm, Orlin’s work gives $O(nm)$ for all densities:

• Orlin’s algorithm handles sparse graphs, $m=O(n^{16/15-\epsilon })$;
• King-Rao-Tarjan handles the rest, $m=\Omega (n^{1+\epsilon })$, in $O(nm)$;
• together: $O(nm)$ unconditionally.

This removed the last logarithmic factor from the $O(nm\log (n^2/m))$ bound of Goldberg-Tarjan that had stood since 1988.

How it works

Orlin’s algorithm is a careful combination of several ideas rather than one new trick:

1. Compaction. Repeatedly contract portions of the network whose flow is already determined, shrinking $n$ geometrically. The bookkeeping ensures the contracted problem is equivalent.
2. Excess scaling in the style of Ahuja-Orlin, to bound the number of non-saturating pushes.
3. Dynamic trees (link-cut trees) to perform blocking-flow-like operations in amortized logarithmic time.
4. An abundance argument: arcs carrying enough flow relative to the current scaling parameter can be fixed permanently and removed from consideration.

The analysis shows the total work across all contractions and phases telescopes to $O(nm)$.

Complexity

• Time: $O(nm)$, strongly polynomial (no dependence on capacity magnitudes)
• Space: $O(n+m)$

Where the field went next

In 2022, Chen, Kyng, Liu, Peng, Probst Gutenberg and Sachdeva gave an $m^{1+o(1)}$ algorithm for max flow and min-cost flow, using interior-point methods with dynamic data structures for the linear algebra. That is almost linear — asymptotically far better than $O(nm)$ — but is currently entirely theoretical, with constants and machinery that put it well out of reach of implementation.

The practical picture is unchanged

Situation	What to write
General max flow, contest sizes	Dinic
Bipartite matching	Hopcroft-Karp or Dinic ($O(m\sqrt{n})$)
Dense graphs, large capacities	Push-relabel with highest-label and gap heuristics
Min cost flow	SSP with potentials, or cost scaling

Dinic with the standard heuristics is essentially never the bottleneck at contest scale, despite its worse asymptotic bound.

Variants / Use Cases

• Maximum Flow — the topic page
• Ahuja-Orlin — the excess-scaling predecessor
• Goldberg-Tarjan — the $O(nm\log (n^2/m))$ bound this improved on
• Complexity Theory — strongly vs weakly polynomial, and why the distinction matters here