Maximum Flow

The maximum flow problem asks how much material can be pushed from a source to a sink through a network where each edge has a capacity. It is one of the most versatile models in combinatorial optimization, and by the max-flow min-cut theorem its value equals the capacity of the smallest cut separating source from sink.

How it works

The Ford-Fulkerson method repeatedly finds an augmenting path from source to sink in the residual graph, a bookkeeping structure that records remaining capacity and allows undoing flow. Pushing flow along augmenting paths until none remain yields a maximum flow. The Edmonds-Karp refinement always augments along a shortest path found by BFS, guaranteeing O(V E squared) time; Dinic's algorithm improves this further with level graphs and blocking flows.

Applications

Max flow models pipeline and traffic throughput, bipartite matching for job assignment, airline crew scheduling, image segmentation in computer vision, baseball elimination, and project selection. It is the standard advanced graph topic in competitive programming and senior interviews.