Chapter 11. Network Flow

Augmenting paths in residual graphs, the max-flow / min-cut duality, and the lattice of mincuts.

This page: LLP forms. View classical forms »

Setting

A flow network is a directed graph $G = (V, E)$ with non-negative edge capacities $c(u, v)$, a designated source $s$, and a sink $t$. A flow $f$ assigns a non-negative number $f(u, v) \leq c(u, v)$ to every edge such that for each interior vertex, the inflow equals the outflow (conservation). The flow value is the net flow leaving the source. The maximum-flow problem asks for a flow of largest value.

A cut $(S, T)$ partitions the vertices with $s \in S$ and $t \in T$, and its capacity is $c(S, T) = \sum_{u \in S, v \in T} c(u, v)$. The Max-Flow Min-Cut Theorem says $\max_f |f| = \min_{(S, T)} c(S, T)$: the maximum flow value equals the minimum cut capacity. Constructive proofs hand back both objects from the same algorithm.

The FordFulkerson Algorithm

Start with the zero flow. Repeatedly find an augmenting $s \to t$ path in the residual graph $G_f$ (edges with non-zero residual capacity, including reverse edges that "undo" past flow), push the bottleneck residual capacity along that path, and update $f$. Terminate when no augmenting path remains. With integer capacities the algorithm is correct and terminates in at most $|f^*|$ iterations, each $O(|E|)$ via DFS or BFS, for a worst-case running time of $O(|E| \cdot |f^*|)$. For badly-shaped networks $|f^*|$ can be exponential in the input size.

The EdmondsKarp Algorithm

A small but pivotal refinement: always pick a shortest augmenting path (fewest edges), found via BFS in the residual graph. Distances from $s$ in $G_f$ never decrease, and after at most $O(|V| \cdot |E|)$ augmentations the algorithm halts. The total running time is $O(|V| \cdot |E|^2)$ — strongly polynomial, independent of capacity magnitudes. EdmondsKarp is the workhorse implementation: simple to implement, predictable to analyse, fast enough for most practical instances.

The Integrality Theorem and combinatorial consequences

If every capacity is an integer, then FordFulkerson (and EdmondsKarp) produces an integer-valued maximum flow. This single observation reduces several classical problems to a max-flow call on a unit-capacity graph:

• Bipartite matching. Build $L \to R$ flow with $s$ feeding every left vertex and every right vertex feeding $t$, all unit-capacity. The max flow is the maximum matching size — see Chapter 12 for the LLP-friendly direct algorithm.
• Edge-disjoint $s$-$t$ paths. Capacity-1 on every edge; the max flow equals the number of edge-disjoint paths, equal to the size of the minimum $s$-$t$ edge cut (Menger's theorem).
• Vertex-disjoint paths. Vertex-splitting trick (in/out copies with a unit edge between them) reduces this to the edge case.

The LLP perspective

The set of minimum $s$-$t$ cuts forms a finite distributive lattice under union/intersection (a consequence of cut-function submodularity). The membership predicate "$S$ is a minimum cut" is itself lattice-linear, so the LLP framework applies: searching for the least mincut $S$ that satisfies a side predicate $B$ becomes the standard LLP fixed-point problem.

Extending max-flow with such side constraints — finding the least mincut satisfying an arbitrary predicate $B$ — is NP-complete in general. The lattice-linear special case, and the LLP algorithm that solves it, is developed in the parallel edition of this book.