Capacity Scaling
What You'll Learn
You'll learn how capacity scaling improves maximum flow algorithms by prioritizing augmenting paths with large capacities, dramatically speeding up performance on certain networks.
The Core Idea
Capacity scaling is a smart refinement of the Ford-Fulkerson method that addresses a key weakness: what if the algorithm repeatedly chooses augmenting paths with tiny capacities? You could end up making thousands of small improvements when a few large ones would suffice.
The solution: only consider paths whose bottleneck capacity is above a certain threshold, starting high and gradually lowering it.
How It Works
- Start with a scaling parameter Δ (initially the largest power of 2 ≤ maximum edge capacity)
- Find augmenting paths in the residual network, but only using edges with residual capacity ≥ Δ
- When no more such paths exist, halve Δ (Δ = Δ/2)
- Repeat until Δ < 1
Think of it like mining: first extract all the gold nuggets (high-capacity paths), then the smaller chunks, then finally the dust. You make rapid progress early by focusing on what matters most.
Why This Helps
Without scaling, algorithms like Edmonds-Karp might find many small augmenting paths. Capacity scaling ensures you handle large flows first, reducing the total number of augmentations needed. On networks with integer capacities up to U, this approach finds the maximum flow in O(E² log U) time—much better when U is reasonable.
Key Takeaway: Capacity scaling accelerates maximum flow algorithms by systematically finding high-capacity augmenting paths first, scaling down the threshold only when necessary, ensuring efficient progress toward the optimal flow.