Chapter 24: Maximum Flow: Flow Networks and the Ford-Fulkerson Method

The residual network G_f captures remaining capacity by tracking how much additional flow can be pushed along each edge, including reverse edges that allow previously committed flow to be redirected, and an augmenting path is any simple s-to-t path through this residual network along which flow can be increased by the path's minimum residual capacity. The max-flow min-cut theorem ties these concepts together elegantly: a flow is maximum if and only if no augmenting path exists in the residual network, and the value of the maximum flow always equals the capacity of the minimum cut — the partition of vertices separating s and t with the smallest total edge capacity crossing from the source side to the sink side. The Ford-Fulkerson method repeatedly finds and augments along any available path, running in O(E × |f*|) time for integer capacities but potentially failing to terminate with irrational ones, while the Edmonds-Karp refinement uses BFS to always select the shortest augmenting path, guaranteeing that bottleneck distances are non-decreasing and bounding the total number of augmentations at O(VE) for an overall runtime of O(VE²). The chapter also addresses structural extensions such as antiparallel edges — resolved by inserting a dummy vertex — and multiple sources or sinks, unified through a supersource and supersink with infinite-capacity edges. Finally, maximum bipartite matching is elegantly reduced to a flow problem by directing unit-capacity edges from a supersource through the left partition, across the bipartite edges, through the right partition, and into a supersink, with the integrality theorem guaranteeing an integer-valued max flow that corresponds directly to a maximum matching, solvable in O(VE) time via Edmonds-Karp.