Capacity Scaling is a twelfth Network Flow entry, and
another path-choice rule fed into Ford-Fulkerson's general
method — like Edmonds-Karp's breadth-first rule, it turns "any
augmenting path is correct" into "here's a fast one," but from a different direction entirely. Edmonds-Karp's
O(VE) bound comes purely from the graph's own size — how many nodes and edges — and never depends
on the actual capacity values at all. Capacity Scaling's bound goes the other way: only ever use an edge whose
residual capacity clears a threshold, Δ, that starts at the largest power of two no bigger than
the network's biggest capacity and halves every time the current threshold runs dry. Minimum-Cost Maximum Flow's own Pitfalls section names this
exact technique as "the standard fix" for a gap that page leaves open on purpose — its cheapest-path-first
rule has no graph-size-only bound the way Edmonds-Karp's does, since a network with many equally-cheap paths
and small bottlenecks can force augmentation counts that scale with the capacities themselves. This page
builds the technique in its native, simpler setting: plain max flow, no costs anywhere, path choice driven by
capacity magnitude alone.
Same four nodes and path-search order as Ford-Fulkerson's
own demo — source S, sink T, and a thin bridge A→B that
a fixed, deliberately bridge-preferring candidate order always tries first, whenever it's usable. What changes
here is that "usable" now also means "residual capacity at least the current Δ," shown at the top
of the stats line. Pick a scenario, then Step or Run through it:
On the symmetric network (all four outer edges set to the same C, bridge fixed
at capacity 1), the bridge-preferring order never actually gets to use the bridge: at the starting threshold
(the largest power of two ≤ C), the bridge's own residual capacity of 1 never clears it, so the
two direct paths S→A→T and S→B→T are all that's left — found and fully saturated in exactly
2 augmentations, for every C in the dropdown above, verified directly rather than
assumed. Compare that to Ford-Fulkerson's own page: the identical bridge-preferring order, with no threshold
at all, needs 2C augmentations on this exact graph — 8 at C=4, scaling linearly with C from
there. Same candidate order, same graph, same final answer — the only thing standing between 2 augmentations
and 2C is whether a capacity threshold gets to filter which paths are even eligible.
Every phase fixes one threshold Δ and only uses an edge if its current residual capacity is at
least Δ — not just for the one path found, but repeatedly, until no Δ-eligible path
remains at all. Only then does Δ halve and the next phase begin, continuing down to
Δ = 1 (at which point every remaining edge is eligible, same as plain Ford-Fulkerson, and any
last few units of flow get mopped up). Two facts make this fast, not just eventually correct:
Δ' exists, a cut argument bounds
exactly how much flow is still missing: the source-reachable side of that residual graph is a real cut, every
edge crossing it has residual under Δ', and there are at most E such edges — so the
gap between the current flow and the true maximum is strictly less than Δ' · E.Δ-phase begins, with Δ' = 2Δ
(the threshold that just ran dry). Every augmentation inside the new Δ phase pushes at least
Δ units — that's what "residual ≥ Δ" guarantees — so at most (2Δ · E) / Δ = 2E
augmentations can happen before that gap closes.So every phase costs at most 2E augmentations, a bound that depends only on the edge count,
never on the capacities — the same flavor of guarantee Edmonds-Karp's BFS rule gives, reached by an entirely
different mechanism (thresholding by size, not searching by hop count). What Edmonds-Karp buys with "always
shortest," this buys with "always big enough for now" — and unlike Edmonds-Karp's rule, "big enough for now"
transfers directly onto Minimum-Cost Maximum Flow's own
cheapest-path-first search: among several equally-cheap augmenting paths, breaking the tie toward the biggest
bottleneck first is exactly this same threshold idea, layered on top of cost instead of replacing it.
The threshold check lives entirely inside findPath; everything else is Ford-Fulkerson's own
augment-and-repeat loop, unchanged:
function capacityScaling(numNodes, edges, s, t) {
const cap = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));
edges.forEach(e => { cap[e.a][e.b] += e.cap; });
const flow = Array.from({ length: numNodes }, () => new Array(numNodes).fill(0));
let total = 0;
const U = Math.max(...edges.map(e => e.cap));
let delta = 1;
while (delta * 2 <= U) delta *= 2; // largest power of two <= U
while (delta >= 1) {
while (true) {
const path = findPathAtLeast(cap, flow, s, t, delta); // only edges with residual >= delta
if (!path) break;
let bottleneck = Infinity;
for (let i = 0; i < path.length - 1; i++) {
bottleneck = Math.min(bottleneck, cap[path[i]][path[i + 1]] - flow[path[i]][path[i + 1]]);
}
for (let i = 0; i < path.length - 1; i++) {
const u = path[i], v = path[i + 1];
flow[u][v] += bottleneck;
flow[v][u] -= bottleneck;
}
total += bottleneck; // bottleneck itself is unthresholded -- could exceed delta
}
delta = Math.floor(delta / 2); // 0 after the delta=1 phase ends the outer loop
}
return total;
}The scaling has to actually start high — running the exact same threshold loop from
Δ=1 throws away the entire guarantee, not just some of the speed. Verified directly with
the Buggy — Δ starts at 1 option above, using the identical bridge-preferring candidate order
as the correct run: for every C in the dropdown, it reproduces Ford-Fulkerson's own
2C augmentations exactly (8 at C=4, 16 at C=8, 32 at C=16, 64 at C=32) — because a single
Δ=1 phase makes every edge eligible from the very first step, so which path gets found first goes
right back to depending on search order alone, with no threshold left to rule the bridge out. The fix isn't
"loop until Δ reaches 1" by itself — it's specifically starting Δ as high as the
network's own capacities allow, so the biggest, most useful paths get first claim regardless of what order a
particular findPath happens to try them in.
Stopping the phase loop one halving too early is a genuine wrong answer, not just a missed
optimization — verified with the Buggy — stops before Δ=1 option, on the
asymmetric network (S→A=4, A→T=3, S→B=3, B→T=4, bridge A→B=1, true max flow 7).
The two direct paths only carry 3 units each before their tighter leg saturates, leaving exactly one more unit
reachable only by routing through the bridge — S→A→B→T, the path's own bottleneck capped at 1. A loop that
stops once Δ > 1 fails, rather than continuing while Δ ≥ 1, never runs the phase
where that threshold would finally admit the bridge, and settles for 6 — a real answer, just
the wrong one, with nothing in the run signaling that anything was skipped. The correct loop reaches all the
way down to Δ = 1 and finds the bridge path there, landing on the true 7.
| C | Bridge-preferring, no threshold (Ford-Fulkerson) | Capacity Scaling, same order |
|---|---|---|
| 4 | 8 | 2 |
| 8 | 16 | 2 |
| 16 | 32 | 2 |
| 32 | 64 | 2 |
Time: O(E² log U), where U is the largest edge capacity — each
Δ-phase runs at most 2E augmentations (see above), each costing O(E) to
search for a path in an adjacency-list residual graph, and there are O(log U) phases from the
starting threshold down to 1. This demo represents the graph as a dense capacity matrix, same choice
Ford-Fulkerson's and Edmonds-Karp's own demos make, so each search costs O(V²) here instead.
Space: O(V²) for the capacity and flow matrices as implemented here, or
O(V + E) with adjacency lists. The key contrast with Edmonds-Karp's O(VE)
augmentation count: that bound can't get any worse no matter how large the capacities are, while this one
can't get any worse no matter how large the graph is relative to log U — two different axes to be
independent of, useful in different situations.
See Choosing a Network Flow Algorithm for how this compares against the site's other eleven Network Flow entries side by side.