Ahuja-Orlin Algorithm

Purpose: A scaling maximum flow algorithm running in $O(nm+n^2\log U)$, where $U$ is the largest capacity. It is the excess-scaling refinement of push-relabel.

Capacity scaling in general

The idea behind every scaling algorithm: instead of pushing arbitrary amounts of flow, work in phases by bit significance.

• Phase $k$ considers only residual capacities $\ge \Delta =2^k$, starting with $\Delta =2^{\lfloor \log U\rfloor }$ and halving each phase.
• Within a phase, only “large” augmentations are made, so there are few of them.
• After $\log U$ phases $\Delta =1$ and the flow is exact.

Applied to Ford-Fulkerson this gives $O(m^2\log U)$; applied to Dinic it gives $O(nm\log U)$.

Ahuja-Orlin’s excess scaling

Rather than scaling capacities, scale the excess at active nodes:

1. Maintain the push-relabel invariants (a height function $h$ and excesses $e(v)$).
2. In phase $\Delta$, only process nodes with excess $e(v)\ge \Delta /2$ — the “large-excess” nodes.
3. Push from the large-excess node of smallest height, and never push more than $\Delta -e(w)$ into a node $w$ (so no node’s excess overshoots $\Delta$).
4. When no large-excess node remains, halve $\Delta$.

Capping the push amount is the key: it prevents the excess from ping-ponging and bounds the number of non-saturating pushes at $O(n^2)$ per phase — independently of $m$.

Complexity

• Time: $O(nm+n^2\log U)$
• Space: $O(n+m)$

The max-flow complexity table

Algorithm	Time
Ford-Fulkerson	$O(mF)$ — pseudo-polynomial
Edmonds-Karp	$O(n{m}^2)$
Capacity-scaling Ford-Fulkerson	$O(m^2\log U)$
Dinic	$O(n^{2}m)$; $O(m\sqrt{n})$ unit caps; $O(n^2\sqrt{m})$ unit…
MPM	$O(n^3)$
Push-relabel FIFO	$O(n^3)$
Push-relabel highest-label	$O(n^2\sqrt{m})$
Ahuja-Orlin (excess scaling)	$O(nm+n^2\log U)$
Goldberg-Tarjan	$O(nm\log (n^2/m))$
Orlin (with King-Rao-Tarjan)	$O(nm)$
Chen et al. 2022	$m^{1+o(1)}$

In a contest

Dinic’s algorithm with scaling as an optional add-on. It is short, it is $O(m\sqrt{n})$ on unit-capacity graphs (which is what bipartite matching needs), and it is fast in practice far beyond its worst-case bound. Ahuja-Orlin is a theoretical waypoint.

Variants / Use Cases

• Maximum Flow — the topic page with modelling patterns
• Push-relabel — the framework being refined
• Min-cost flow — cost scaling is the analogous idea for costs, and Ahuja-Orlin also produced the standard cost-scaling algorithm
• Gabow scaling — bit-scaling applied to matching and shortest paths