Same advance/retreat/augment procedure, now charged carefully with arbitrary capacities 1:21:06.
Counting each operation
| Operation | Count | Cost each | Total |
|---|---|---|---|
| Augment | ≤ m — every augment saturates at least one edge, which is then deleted 1:21:53, 1:22:31 | O(n) — the built path has length ≤ n and flow is added edge by edge 1:22:31, 1:22:48 | O(mn) 1:22:48 |
| Retreat | ≤ m — each retreat deletes an edge 1:23:13 | O(1) 1:23:13 | O(m) 1:23:13 |
| Advance | ≤ mn — you cannot advance n times without either reaching t (augment) or hitting a dead end (retreat), and each of those deletes an edge; at most m deletions 1:23:51, 1:24:16, 1:24:43 | O(1) | O(mn) 1:24:43 |
- Note the vocabulary: "augment" inside this subroutine means adding the path's bottleneck capacity to the blocking flow being built — not modifying the residual graph
1:21:53.
Resulting bound
O(mn)per blocking flow in general capacitated graphs1:24:43.- × at most
niterations ⇒O(mn²)max flow1:24:43,1:25:32. - Compare with Edmonds–Karp's
O(m²n)— blocking flows trade anmfor ann32:12,32:44.
Where the waste is, and the fix (next lecture)
- The single-blocking-flow procedure is wasteful: it re-explores paths from scratch after each augment
1:25:32,1:26:04. - Link-cut trees (Sleator–Tarjan, 1983) cut the cost from
O(mn)toO(m log n)per blocking flow1:26:04,1:26:22,1:26:48. - ⇒
O(mn log n)max flow, the bound that stood from 1983 until Orlin'sO(mn)in 201350:40,9:21. - Details deferred to the next lecture
1:26:22,1:26:48.