Max Flow-Min Cut & Ford-Fulkerson

The Max Flow-Min Cut theorem states that the maximum flow equals the minimum cut capacity. The Ford-Fulkerson algorithm computes max flow using augmenting paths in the residual graph. We also cover the Integrality Lemma and three standard flow modifications. This is the last topic covered on the midterm.

Learning Objectives

Define cuts and the min cut of a network

State and prove the Max Flow-Min Cut theorem

Implement Ford-Fulkerson using augmenting paths in the residual graph

Trace Ford-Fulkerson on example networks

State the Integrality Lemma and apply flow modifications

Key Concepts

Cuts & Min Cut

A cut in a flow network is a partition of vertices into sets $S$ and $T = V \setminus S$ with $s \in S$ and $t \in T$ . The capacity of the cut is the sum of capacities of edges from $S$ to $T$ .

The min cut is the cut with minimum capacity.

-
For any flow $f$ and cut $(S,T)$ : $|f| \leq c(S,T)$
-
The max flow equals the min cut capacity
-
A min cut can be found from the max flow: $S$ = vertices reachable from $s$ in the residual graph

Ford-Fulkerson Algorithm

The Ford-Fulkerson method repeatedly finds augmenting paths in the residual graph and pushes flow along them.

The residual graph $G_f$ has:

-Forward edges with residual capacity $c(e) - f(e)$ (if $f(e) < c(e)$ )
-Backward edges with capacity $f(e)$ (if $f(e) > 0$ )

-
Find $s$ - $t$ path in residual graph, push minimum residual capacity along it
-
Repeat until no $s$ - $t$ path exists in residual graph
-
With BFS for path finding (Edmonds-Karp): $O(nm^2)$ time
-
With integer capacities: terminates in $O(|f^*| \cdot m)$ time
-
After termination: vertices reachable from $s$ in residual graph form the min cut

Integrality Lemma & Flow Modifications

The Integrality Lemma guarantees that if all capacities are integers, there exists a maximum flow with integer values on all edges. This is crucial for applications like matching.

Three standard modifications extend the basic flow model:

-Multiple sources/sinks: Add a super source $S$ and super sink $T$ with infinite-capacity edges
-Vertex capacities: Split each vertex $v$ into $v_{in}$ and $v_{out}$ connected by an edge of capacity $c(v)$
-Undirected edges: Replace each undirected edge $uv$ with two directed edges $\overrightarrow{uv}$ and $\overrightarrow{vu}$ , both with capacity $c(uv)$

-
Integer capacities → integer max flow (critical for matching via flow)
-
Multiple sources $s_1, \ldots, s_k$ and sinks $t_1, \ldots, t_l$ : add super source $S$ with edges $(S, s_i)$ of capacity $\infty$ , and super sink $T$ with edges $(t_j, T)$ of capacity $\infty$
-
Vertex capacity $c(v)$ : split $v$ into $v_{in}$ (all incoming edges) and $v_{out}$ (all outgoing edges), add edge $(v_{in}, v_{out})$ with capacity $c(v)$
-
Undirected network: replace edge $uv$ with two directed edges $\overrightarrow{uv}$ and $\overrightarrow{vu}$ , both with capacity $c(uv)$

W9: Edge Coloring, König & Max Flow W11: Vertex & Edge Connectivity