Course contentsShow
← Computer Science
Lesson 1040 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Capacity Scaling

Understand how scaling finds augmenting paths with large capacities first to improve performance.

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

  1. Start with a scaling parameter Δ (initially the largest power of 2 ≤ maximum edge capacity)
  2. Find augmenting paths in the residual network, but only using edges with residual capacity ≥ Δ
  3. When no more such paths exist, halve Δ (Δ = Δ/2)
  4. 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.