Max-Flow Min-Cut

Ford-Fulkerson augmenting paths and the cut that certifies the max flow.

The idea

A flow network is a directed graph with a source $s$, a sink $t$, and a nonnegative capacity on every edge. A flow assigns each edge an amount between zero and its capacity so that at every node other than $s$ and $t$, the amount arriving equals the amount leaving. Its value $|f|$ is the net amount leaving $s$. An $s$-$t$ cut $(S, T)$ partitions the nodes with $s \in S$ and $t \in T$, and its capacity $c(S, T)$ is the total capacity of the edges directed from $S$ to $T$.

Theorem (Max-flow min-cut theorem).

In any flow network, the maximum value of an $s$-$t$ flow equals the minimum capacity of an $s$-$t$ cut.

One inequality holds for every flow and every cut: all flow reaching $t$ starts at $s$, so it must cross the cut, and no more can cross than the cut's capacity allows, so $|f| \le c(S, T)$. A flow and a cut of equal value therefore certify each other, since neither can be improved.

The Ford-Fulkerson algorithm produces such a pair. It works in the residual network of the current flow $f$, where each edge offers its leftover capacity forward and the flow already placed on it backward — so a later path can undo an earlier decision. A path from $s$ to $t$ in the residual network is an augmenting path.

Algorithm.

Algorithm: Ford-Fulkerson Input: a flow network with source s and sink t Output: a maximum flow f 1. f(e) = 0 on every edge 2. form the residual network of f 3. if it has no augmenting path, return f 4. push flow along an augmenting path, as much as its tightest edge permits // raise f on forward edges, lower f on backward edges 5. go to step 2

With integer capacities each iteration raises $|f|$ by at least $1$, so the algorithm runs in $O(E \cdot |f^{}|)$ time, where $|f^{}|$ is the maximum flow value.

Ways to work on it

Not sure where to start? Take the ten-question placement test.