The idea

  • Scaling reduces the general-capacity case toward the unit-capacity case, feeding in capacities one bit at a time 16:09, 16:53.
  • Treat each capacity as a log₂ U-bit binary integer 16:53.
  • Work with shadow capacities c'(e), starting at 0, that grow toward the true c(e) bit by bit; e.g. an edge of capacity 6 (0110) is seen as capacity 0, then 1, then 3, then 6 19:17, 19:51, 20:19, 20:46.

Pseudocode

f ← 0;  c'(e) ← 0 for all e
for k = log₂U − 1 down to 0:
    for each edge e:  c'(e) ← 2·c'(e);  f(e) ← 2·f(e)     # shift left
    for each edge e:  c'(e) ← c'(e) + (k-th bit of c(e))  # shift the bit in
    augment f until it is a max flow for c'

17:33, 18:26, 21:22, 21:36, 22:05

Correctness — the loop invariant

  • Invariant: at the start of every iteration, f is a max flow for the current c' capacities 22:05, 23:17.
  • Base case: trivially true when all capacities are 0 23:17.
  • Doubling preserves maximality: max flow = min cut, and a max flow saturates some s–t cut with zero residual capacity. Doubling doubles both that cut's capacity and the flow across it, so it stays saturated 23:17, 24:17.
  • Shifting in a bit keeps f feasible but possibly non-maximum; augmenting paths restore maximality 24:44.

Running time

  • Iterations: exactly log U 25:30.
  • Caution: after doubling, unsaturated edges are not unit-capacity, so this is not literally the unit-capacity case — the lecturer retracts that phrasing 25:58, 26:33.
  • The real argument is that the residual max flow per iteration is small 26:56:
    1. Before shifting in the new bit, some cut C is saturated by f and has residual capacity 0 27:18, 28:06.
    2. C has at most m edges, and the shift adds at most 1 capacity per edge 27:35, 28:53.
    3. So C's residual capacity is at most m, hence the min cut — and therefore the residual max flow — is at most m 27:35, 29:33.
  • Per iteration Ford–Fulkerson costs O(m · f*) = O(m²), giving O(m² log U) overall — weakly polynomial 28:06, 29:33.

Why scaling matters beyond this bound

  • Scaling is a wrapper: the inner "augment to max flow" step can be any max-flow routine, so it composes with blocking flows and other algorithms 29:33, 30:23.
flowchart LR
    A["c' = 0, f = 0"] --> B["double c' and f<br/>(max flow preserved)"]
    B --> C["shift in next bit of c<br/>(feasible, not maximal)"]
    C --> D["augment to max flow<br/>residual flow ≤ m"]
    D -->|"log U times"| B
    D --> E["max flow for true c"]