12: Network Flows

Flow Networks

A flow network is a directed graph $G = (V, E)$ with two distinguished vertices — a source $s$ and a sink $t$ — together with a capacity function $c : E \to \mathbb{R}_{\geq 0}$ assigning a nonneg capacity to each edge. A flow is a function $f : E \to \mathbb{R}_{\geq 0}$ satisfying two constraints:

1. Capacity constraint: for every edge $(u, v) \in E$, we require $0 \leq f(u,v) \leq c(u,v)$.
2. Flow conservation: for every vertex $v \in V \setminus \{s, t\}$, the total flow entering $v$ equals the total flow leaving $v$:

$\sum_{u:(u,v) \in E} f(u,v) = \sum_{w:(v,w) \in E} f(v,w)$

The value of a flow is the net flow leaving the source: $|f| = \sum_{v:(s,v) \in E} f(s,v) - \sum_{u:(u,s) \in E} f(u,s)$. The maximum flow problem asks for a flow of maximum value.

Residual Graphs and Augmenting Paths

Given a flow $f$ on $G$, the residual graph $G_f = (V, E_f)$ encodes remaining capacity. For each edge $(u,v) \in E$:

• If $f(u,v) < c(u,v)$, include a forward edge $(u,v)$ with residual capacity $c_f(u,v) = c(u,v) - f(u,v)$.
• If $f(u,v) > 0$, include a backward edge $(v,u)$ with residual capacity $c_f(v,u) = f(u,v)$.

An augmenting path is any $s \to t$ path in the residual graph $G_f$. The bottleneck capacity of such a path $P$ is $\min_{(u,v) \in P} c_f(u,v)$. We can increase the flow value by this bottleneck amount by pushing flow along $P$, incrementing forward edges and decrementing backward edges accordingly.

The Ford-Fulkerson Method

The Ford-Fulkerson method is an iterative approach to computing maximum flows:

1. Initialize $f(u,v) = 0$ for all edges.
2. While there exists an augmenting path $P$ in $G_f$:
   • Compute the bottleneck capacity $\delta = \min_{(u,v) \in P} c_f(u,v)$.
   • Update the flow: for each edge $(u,v) \in P$, increase $f(u,v)$ by $\delta$ (forward) or decrease $f(v,u)$ by $\delta$ (backward).
3. Return $f$.

With integer capacities, each iteration increases $|f|$ by at least 1, so the method terminates in at most $|f^*|$ iterations, where $f^*$ is a maximum flow. Each iteration requires $O(E)$ time to find an augmenting path, yielding $O(E \cdot |f^*|)$ total time. This can be arbitrarily bad: a network with capacity $C$ on critical edges yields $O(EC)$ time, which is pseudo-polynomial.

The Max-Flow Min-Cut Theorem

An $s$-$t$ cut is a partition $(S, T)$ of $V$ with $s \in S$ and $t \in T$. Its capacity is $c(S, T) = \sum_{u \in S, v \in T} c(u,v)$. For any flow $f$ and any cut $(S, T)$, the value of $f$ equals the net flow across the cut, and therefore $|f| \leq c(S, T)$.

Theorem (Max-Flow Min-Cut). The following three conditions are equivalent:

1. $f$ is a maximum flow in $G$.
2. The residual graph $G_f$ contains no augmenting path.
3. $|f| = c(S, T)$ for some $s$-$t$ cut $(S, T)$.

This theorem, due to Ford and Fulkerson (1956), establishes a strong duality between flows and cuts. The proof is constructive: when no augmenting path exists, the set $S$ of vertices reachable from $s$ in $G_f$ defines a minimum cut.

Edmonds-Karp Algorithm

The Edmonds-Karp algorithm is Ford-Fulkerson with the specific rule of always choosing the shortest augmenting path (fewest edges), found via BFS on $G_f$.

Theorem. Edmonds-Karp runs in $O(VE^2)$ time.

The key insight is that after each augmentation, at least one edge becomes saturated (its residual capacity drops to zero), and the distance from $s$ to any vertex in $G_f$ is monotonically nondecreasing. Since each edge can be critical at most $O(V)$ times and there are $O(E)$ edges, the total number of augmentations is $O(VE)$. Each BFS takes $O(E)$ time, giving $O(VE^2)$.

More advanced algorithms achieve better bounds. Dinic’s algorithm runs in $O(V^2 E)$ using the concept of blocking flows in layered graphs. For unit-capacity networks, this improves to $O(E\sqrt{V})$. The push-relabel algorithm of Goldberg and Tarjan achieves $O(V^2 E)$ as well, with practical implementations often outperforming augmenting-path methods.

Applications

Bipartite Matching

Given a bipartite graph $G = (L \cup R, E)$, a matching is a subset $M \subseteq E$ where no vertex appears more than once. To find a maximum matching, construct a flow network: add source $s$ with edges to all vertices in $L$, add sink $t$ with edges from all vertices in $R$, direct all original edges from $L$ to $R$, and set all capacities to 1. An integral maximum flow corresponds to a maximum matching. By the integrality theorem, the max-flow in a network with integer capacities is integer-valued, so this reduction is exact.

By K”onig’s theorem, the size of the maximum matching in a bipartite graph equals the size of the minimum vertex cover, a combinatorial analogue of max-flow min-cut duality.

Edge-Disjoint Paths

The maximum number of edge-disjoint $s$-$t$ paths in a directed graph equals the maximum $s$-$t$ flow when all capacities are 1 (Menger’s theorem). This follows directly from the integrality theorem: each unit of flow traces a distinct $s$-$t$ path, and no edge carries more than one unit.

Minimum Cut in Undirected Graphs

For undirected graphs, replace each edge $\{u,v\}$ with two directed edges $(u,v)$ and $(v,u)$, each with the original capacity. The minimum $s$-$t$ cut in this directed network gives the minimum $s$-$t$ cut in the original undirected graph. The global minimum cut (over all $s,t$ pairs) can be found by fixing $s$ and trying all $|V|-1$ choices of $t$.

Connection to Machine Learning

Graph cuts for image segmentation. In binary image segmentation, each pixel $i$ is assigned a label $x_i \in \{0,1\}$ (foreground or background). The energy function combines unary terms (how likely each pixel belongs to each class, derived from a learned model) and pairwise terms (a penalty for neighboring pixels with different labels):

$E(x) = \sum_i D_i(x_i) + \lambda \sum_{(i,j) \in \mathcal{N}} V_{ij}(x_i, x_j)$

When the pairwise terms are submodular (the penalty for disagreeing neighbors exceeds that for agreeing ones), this energy can be exactly minimized via a minimum $s$-$t$ cut. Construct a flow network with pixels as nodes, source representing foreground and sink representing background. Edge capacities encode the energy terms. The minimum cut partitions pixels into foreground and background, minimizing $E(x)$ in polynomial time.

This technique, popularized by Boykov, Veksler, and Zabih (2001), is widely used in computer vision. Extensions handle multi-label problems via alpha-expansion moves, where each move solves a binary graph cut subproblem.

Next: 13: Linear Programming