An aqueduct carries water from a spring to a city through a network of pipes, each with a maximum capacity. How much water per second can reach the city, at most? And if you wanted to reduce that amount by cutting some pipes, which would be the cheapest to cut? These are two seemingly different questions, but they have the same numerical answer. It is one of the most beautiful results in combinatorial optimisation: the max-flow min-cut theorem.
The model: a flow network
A flow network is a directed graph with:
- a source s, where the flow starts;
- a sink t, where the flow arrives;
- a capacity c(u, v) ≥ 0 on every edge.
A flow assigns to each edge a quantity f(u, v) that respects two rules:
- capacity constraint: 0 ≤ f(u, v) ≤ c(u, v);
- conservation: at every vertex other than s and t, what comes in equals what goes out.
The value of the flow is the total quantity leaving s, which equals the quantity entering t. The maximum flow problem asks for the flow with the highest value.
The residual graph
The most ingenious idea is the residual graph. For each edge (u, v) with flow f and capacity c we consider:
- a forward edge with residual capacity c − f, that is, how much more can be pushed;
- a backward edge (v, u) with capacity f, that is, how much flow can be «undone».
Backward edges are essential. They let the algorithm correct an earlier choice: if a first path made poor use of a pipe, a later path can divert that flow elsewhere.
Ford-Fulkerson: augmenting paths
The general scheme is simple:
- start from zero flow;
- look in the residual graph for a path from s to t, called an augmenting path;
- find the minimum residual capacity along the path (the «bottleneck») and push that amount along the whole path;
- repeat until no augmenting paths remain.
When the algorithm stops, the flow is maximum. With integer capacities, each iteration increases the flow by at least 1, so the algorithm terminates and the maximum flow it finds is itself integral. This integrality property is fundamental in applications: it guarantees solutions made of whole units, such as people or vehicles.
Edmonds-Karp: choosing the path wisely
Ford-Fulkerson does not specify which augmenting path to choose, and an unlucky choice can require a very large number of iterations. Edmonds-Karp fixes the rule: always choose the augmenting path with the fewest edges, found with a breadth-first search.
With this rule the number of iterations is bounded regardless of the capacity values, and the total cost is proportional to n · m². For very large graphs there are faster algorithms, such as Dinic's or push-relabel methods, but Edmonds-Karp remains an excellent starting point: it is short, clear and reliable.
The minimum cut
An s–t cut splits the vertices into two groups, S containing s and T containing t. Its capacity is the sum of the capacities of the edges going from S to T. Any flow must cross the cut, so no flow can exceed the capacity of any cut.
The theorem states that the value of the maximum flow is equal to the capacity of the minimum cut. Moreover, at the end of Ford-Fulkerson the cut comes for free: S is the set of vertices still reachable from s in the residual graph. The edges from S to T are all saturated and form the minimum cut.
An example
Edges with capacities: s→a 10, s→b 5, a→b 15, a→t 5, b→t 10.
- Path s→a→t: bottleneck 5. Total flow 5.
- Path s→b→t: bottleneck 5. Total flow 10.
- Path s→a→b→t: residuals 5, 15, 5. Bottleneck 5. Total flow 15.
At this point both edges leaving s are saturated: s→a carries 10 out of 10, s→b carries 5 out of 5. There are no more augmenting paths: the maximum flow is 15, and the minimum cut is {s} against the rest, with capacity 10 + 5 = 15.
Where it is used
- Logistics and transport: how many goods per day can travel from a port to a distribution centre over a network with capacity limits.
- Computer networks: the maximum bandwidth between two points, and the links that form the real bottleneck. The minimum cut shows where to invest to increase capacity.
- Reliability: with capacity 1 on every edge, the maximum flow is the number of independent paths between two nodes, and the minimum cut is the number of links that must be broken to isolate them.
- Computer vision: segmenting images into foreground and background is formulated as a minimum cut on a graph of pixels.
- Matchings: assigning workers to shifts or students to projects reduces to a maximum flow on a bipartite graph.
In short
- A flow network has a source, a sink and capacities; the flow respects capacity and conservation.
- Ford-Fulkerson pushes flow along augmenting paths in the residual graph.
- Edmonds-Karp chooses the shortest paths with a BFS, at a cost of n · m².
- The maximum flow equals the capacity of the minimum cut, which is read off the final residual graph.
- With integer capacities the maximum flow is integral, a decisive property for assignments and logistics.
