Maximum Flow

A flow network is a directed graph with source s, sink t, and non-negative edge capacities. A feasible flow respects capacity and conserves flow at every other vertex. The objective is to maximize net flow from s to t.

Residual network

The residual capacity describes how much additional flow an edge can carry and how much existing flow can be undone through a reverse residual edge. Ignoring reverse edges makes greedy augmentations permanently commit to choices and can miss an optimum.

Ford–Fulkerson method

Repeatedly find an s–t path in the residual graph, augment by its minimum residual capacity, and update forward and reverse residual edges. With integral capacities, each augmentation increases flow by at least one, so the method terminates. A bound depending on maximum flow is pseudo-polynomial, not strongly polynomial in the input bit length.

Edmonds–Karp and Dinic

Edmonds–Karp chooses a shortest residual path by BFS and runs in O(VE²) time. Dinic builds BFS level graphs and sends blocking flows; its general bound is O(V²E), with stronger bounds for important network classes.

Max-flow min-cut theorem

For any feasible flow and any s–t cut, flow value is at most cut capacity. When no augmenting path remains, vertices reachable from s in the residual network define a cut whose capacity equals the current flow. The flow is maximum and the cut minimum.

Reductions

Maximum flow models bipartite matching, edge-disjoint paths, resource allocation, and circulation variants. A reduction must preserve integrality, capacities, direction, and the meaning of a feasible solution.

Exercises

1. Show why reverse residual edges are necessary.
2. Reduce bipartite matching to unit-capacity flow.
3. Extract a minimum cut after the final residual search.