Maximum flow (concept + Ford-Fulkerson)

Flow networks

A flow network is a directed graph where each edge $(u,v)$ has a nonnegative capacity $c(u,v)\ge 0$, with a designated source $s$ and sink $t$. A flow $f$ assigns a value to each edge subject to two rules:

- Capacity constraint: $0\le f(u,v)\le c(u,v)$ — you cannot send more than an edge can carry. - Flow conservation: at every vertex except $s$ and $t$, flow in equals flow out — nothing accumulates or appears.

The value $|f|=\sum_v f(s,v)-\sum_v f(v,s)$ is the net flow leaving the source. The maximum-flow problem asks for the flow of greatest value.

Residual networks and augmenting paths

The key device is the residual network $G_f$, which records *how the flow can still change*. For each edge it provides two residual capacities:

- Forward residual $c_f(u,v)=c(u,v)-f(u,v)$ — unused capacity you can still push. - Backward residual $c_f(v,u)=f(u,v)$ — the ability to cancel existing flow and reroute it.

An edge appears in $G_f$ exactly when its residual capacity is positive. An augmenting path $p$ is any simple $s\rightsquigarrow t$ path in $G_f$; its residual capacity is the bottleneck $c_f(p)=\min\{c_f(u,v):(u,v)\in p\}$. *Augmenting* along $p$ pushes $c_f(p)$ units — raising forward edges and lowering the cancelled ones — increasing $|f|$ by $c_f(p)>0$. The backward edges are what let a greedy method *undo* a bad earlier routing choice.

The max-flow min-cut theorem (Theorem 24.6)

A cut $(S,T)$ partitions the vertices with $s\in S$, $t\in T$; its capacity $c(S,T)$ is the total capacity of edges crossing $S\to T$. The theorem states three equivalent conditions:

1. $f$ is a maximum flow.
2. $G_f$ contains no augmenting path.
3. $|f|=c(S,T)$ for some cut $(S,T)$.

So max flow = min cut. The $(2)\Rightarrow(3)$ proof is constructive: when no augmenting path exists, take $S=\{$vertices reachable from $s$ in $G_f\}$. Then every $S\to T$ edge is *saturated* ($c_f=0\Rightarrow f=c$) and every $T\to S$ edge carries *zero* flow, so the net flow across the cut equals its capacity, $|f|=c(S,T)$ — proving maximality and exhibiting a minimum cut at once.

Ford-Fulkerson and Edmonds-Karp

Ford-Fulkerson is the method: start with $f=0$, and while an augmenting path exists in $G_f$, augment along it. With integer capacities each augmentation adds at least $1$, so it terminates — but choosing the path carelessly costs $O(E\,|f^*|)$, which is *not* polynomial in the input size (a $1{,}000{,}000$-capacity graph can need $2{,}000{,}000$ augmentations).

Edmonds-Karp fixes this by always taking the shortest (fewest-edge) augmenting path via BFS. Then BFS distances from $s$ in $G_f$ increase monotonically, so each edge becomes a critical (bottleneck) edge at most $|V|/2$ times — yielding $O(VE)$ augmentations and a total of $O(VE^2)$, polynomial regardless of capacity values. By the integrality theorem, integer capacities yield an integer maximum flow — which is why bipartite matching reduces to max flow: give every edge capacity $1$ and each vertex is matched at most once.

Worked example

On the CLRS Fig 24.1 network (6 vertices $s,v_1,v_2,v_3,v_4,t = 0\dots5$) Edmonds-Karp finds a maximum flow of value 23.