Mathematics
Network Flow Problems and the Max-Flow Min-Cut Theorem
Quick fact
The max-flow min-cut theorem was proven independently by Ford and Fulkerson in 1956 and by Elias, Feinstein, and Shannon in the same year, and it led to a fundamental algorithm that runs in polynomial time for many networks.
Why this is interesting
Imagine water flowing through a network of pipes, each with a limited capacity. You'd think the answer depends on every pipe, but a surprising theorem tells you that the bottleneck is actually one single cut of the pipes. What is that cut?
Read the full explanation
Understanding Network Flow Problems and the Max-Flow Min-Cut Theorem
Think of a network as a system of pipes connecting a source (where water enters) to a sink (where water leaves). Each pipe (edge) has a maximum capacity—how much water can pass through per second. The goal is to push as much water as possible from source to sink without exceeding any pipe's capacity. Intuitively, some pipes will be fully used, while others have spare capacity. The max-flow problem asks: what's the maximum total flow? The max-flow min-cut theorem provides the answer: it's equal to the smallest possible total capacity of a 'cut'—a set of edges whose removal breaks the connection between source and sink. Visualize a network of roads: the flow is the number of cars per hour, capacity is the number of lanes, and a cut is a line you can draw that separates source and sink, with the road crossings being the cut edges. The theorem says the biggest traffic jam you can have is determined by the narrowest set of roads you can block to stop all traffic.
A deeper explanation
The max-flow min-cut theorem states: In any directed graph with a source node s, a sink node t, and non-negative edge capacities, the maximum value of a feasible flow equals the minimum capacity of an s-t cut. A flow assigns a value to each edge, not exceeding its capacity, and conserves flow at every node except s and t (what goes in equals what goes out). A cut is a partition of vertices into two sets, one containing s and the other containing t; its capacity is the sum of capacities of edges going from the s-side to the t-side. The proof has two parts: First, any flow value is bounded by any cut capacity, because flow must cross from the s-side to the t-side, and the total crossing flow cannot exceed the sum of capacities on those edges. Therefore, the max flow ≤ min cut capacity. Second, to show equality, one can use the Ford-Fulkerson algorithm that builds an increasing flow by finding augmenting paths in the residual graph (which shows remaining capacity). When no augmenting path exists, the set of nodes reachable from s defines a cut whose capacity exactly equals the current flow, proving that flow is maximal and that the cut's capacity equals the flow. Thus the theorem provides both a certificate of optimality and a method to find the max flow. This result is a special case of the strong duality theorem in linear programming, where max flow and min cut are primal and dual programs.