Network Flows and Max-Flow Min-Cut

Network flow theory models the transportation of commodities through a network. The max-flow min-cut theorem, a cornerstone of combinatorial optimization, establishes a deep duality between flows and cuts.

Flow Networks

Definition7.1Network and Flow

A flow network is a directed graph $G = (V, E)$ with a source $s$ , sink $t$ , and capacity function $c: E \to \mathbb{R}_{\geq 0}$ . A flow is a function $f: E \to \mathbb{R}_{\geq 0}$ satisfying: (1) capacity constraint: $0 \leq f(e) \leq c(e)$ for all $e$ ; (2) conservation: $\sum_{(u,v)\in E} f(u,v) = \sum_{(v,w)\in E} f(v,w)$ for all $v \neq s, t$ . The value of $f$ is $|f| = \sum_{(s,v)\in E} f(s,v) - \sum_{(v,s)\in E} f(v,s)$ .

Definition7.2Cut and Capacity

An $s$ - $t$ cut is a partition $(S, T)$ of $V$ with $s \in S, t \in T$ . The capacity of the cut is $c(S, T) = \sum_{\substack{(u,v)\in E \\ u\in S, v\in T}} c(u,v)$ . For any flow $f$ and cut $(S,T)$ : $|f| = \sum_{\substack{u\in S,v\in T}} f(u,v) - \sum_{\substack{u\in T,v\in S}} f(u,v) \leq c(S,T)$ . This shows max flow $\leq$ min cut.

Algorithms

ExampleFord-Fulkerson Method

The Ford-Fulkerson method iteratively finds augmenting paths in the residual graph $G_f$ (where edge $(u,v)$ has residual capacity $c_f(u,v) = c(u,v) - f(u,v)$ and back-edge $c_f(v,u) = f(u,v)$ ). Each augmenting path increases $|f|$ by the bottleneck capacity. With integer capacities $C = \max c(e)$ : terminates in $O(|f^*|)$ augmentations, total $O(|f^*| \cdot m)$ . Edmonds-Karp (BFS augmentations): $O(nm^2)$ . Dinic's algorithm (blocking flows on layered graphs): $O(n^2 m)$ .

RemarkPush-Relabel Algorithm

The Goldberg-Tarjan push-relabel algorithm maintains a preflow (excess allowed at vertices) and uses "push" (send flow along admissible edges) and "relabel" (increase height labels) operations. Running time: $O(n^2\sqrt{m})$ with FIFO selection, or $O(n^3)$ with highest-label. For dense graphs, push-relabel is often the fastest in practice. The highest-label variant achieves $O(n^2\sqrt{m})$ worst-case.