Advanced Graph Algorithms, Flows & Matching

Given a flow f on network G, the residual network Gf has the same vertices and, for each edge (u,v) with capacity c and flow f, a forward residual edge (u,v) of capacity c−f and a backward residual edge (v,u) of capacity f. Augmenting along residual edges (including backward edges, which cancel flow) lets the algorithm undo earlier decisions.

An augmenting path is a source-to-sink path in the residual network with all residual capacities positive; pushing the bottleneck (minimum residual capacity) along it increases total flow. Ford-Fulkerson repeatedly finds augmenting paths until none remain; at that point the flow is maximum.

If augmenting paths are chosen arbitrarily, each augmentation may add as little as 1 unit, giving O(E·|f*|) time on integer capacities (bad when the max flow value is huge). With irrational capacities it may not terminate at all. Choosing paths carefully (BFS = Edmonds-Karp, or scaling) fixes this.

Edmonds-Karp is Ford-Fulkerson that always augments along a shortest (fewest-edges) augmenting path found by BFS. The shortest source-sink distance is non-decreasing across augmentations, and each edge becomes saturated O(V) times, giving O(V·E) augmentations and O(V·E²) total time, independent of capacities.

A BFS from the source assigns levels (distance) to vertices; the level graph keeps only edges (u,v) with level(v)=level(u)+1. A blocking flow is a flow in the level graph such that every source-sink level path has at least one saturated edge — no more augmentation is possible within the current level graph.

Repeat phases: (1) BFS from s to build the level graph and check s reaches t; (2) find a blocking flow in the level graph via DFS, using a current-arc (pointer) optimization to skip dead edges. Each phase strictly increases the shortest s-t distance, so there are at most V−1 phases.