1. Max-flow recap and complexity terminology

Where the lecture picks up

Goal of the day: faster max-flow algorithms — scaling, blocking flows, and how link-cut trees speed blocking flows up 0:27.
Setup carried over from last lecture: a capacitated directed graph G = (V, E), every edge e with capacity c_e 1:17.
Capacities are integers in [1, U]; the task is to find an s–t flow of maximum value 1:59.
Integrality is assumed throughout — fractional capacities can be handled by clearing denominators; with fractions log U stops making sense as a bound unless you normalize somehow 33:14, 33:42, 34:02.
Model: word RAM with words of at least log n bits, so arithmetic/comparison on capacities costs O(1) 14:47.

A flow is a vector on the edges 1:59.
Capacity constraints: never push more flow than an edge's capacity 2:43.
Conservation: flow out of s equals flow into t; every other vertex has flow in = flow out 2:43.
Value of a flow = amount leaving s 2:43.
Residual graph G_f: residual capacity = original capacity minus the flow already on the edge, i.e. how much more can still be sent 3:08. Flow pushed the opposite way counts as negative flow, so a reverse edge gets residual capacity (e.g. 0 − (−1) = 1) 47:31, 48:04.

Algorithm: repeatedly find an augmenting path in the current residual graph, augment, rebuild the residual graph, stop when no augmenting path exists — this is correct 3:08, 4:02.
Each augmenting path pushes at least one unit of flow; finding one path is linear in m via DFS or BFS 4:50, 5:29.
Running time: O(m · f*), f* = value of the max flow 5:29.
Why that is bad: f* can be as large as n · U, and writing a capacity takes only log U bits — so the runtime is exponential in the input's representation 5:59.
Ford–Fulkerson leaves the path-selection rule open (DFS, BFS, max-bottleneck, ...), and the choice changes the bound 31:11, 32:12.
- Augment along the path with largest minimum capacity → much better than vanilla FF (a problem-set exercise) 31:11, 32:12.
- Augment along BFS shortest paths → O(m²n), i.e. Edmonds–Karp 32:12.

Term	Running time depends on	Example
Weakly polynomial	`poly(m, log U)` — polynomial in the representation `6:33`	scaling algorithms `7:58`
Strongly polynomial	`poly(m)` only; step count independent of capacity magnitudes (arithmetic on capacities still assumed `O(1)`) `7:23`	blocking flows `7:58`
Pseudo-polynomial	`poly(m, U)` — worst of the three `7:23`, `7:58`	Ford–Fulkerson `7:58`; exact knapsack DP, whose state count is linear in total weight `8:18`, `8:51`

The lecture will deliver one strongly polynomial and one weakly polynomial algorithm 7:58.