Unit 8: Network Flows, Max-Flow Min-Cut Theorem & Combinatorial Optimization

1. Step-by-Step Edmonds-Karp Trace

Initial flow: $f(e) = 0$ for all edges.

Augmentation 1:

• BFS searches for the shortest path in edge count from $s$ to $t$:

Path $p_1: s \to A \to B \to t$ (length 3 edges).

• Capacities along $p_1$:

$c_f(s, A) = 10, \; c_f(A, B) = 4, \; c_f(B, t) = 10$.

• Bottleneck: $\Delta_1 = \min(10, 4, 10) = 4$.
• Update flow:

$f(s, A) = 4, \; f(A, B) = 4, \; f(B, t) = 4$.

• Residual capacity updates:

$c_f(s, A) = 6, \; c_f(A, s) = 4$. $c_f(A, B) = 0$ (Saturated!), $c_f(B, A) = 4$. $c_f(B, t) = 6, \; c_f(t, B) = 4$.

• Flow value: $|f| = 4$.

Augmentation 2:

• BFS finds the next shortest path:

Path $p_2: s \to C \to D \to t$ (length 3 edges).

• Capacities along $p_2$:

$c_f(s, C) = 10, \; c_f(C, D) = 9, \; c_f(D, t) = 10$.

• Bottleneck: $\Delta_2 = \min(10, 9, 10) = 9$.
• Update flow:

$f(s, C) = 9, \; f(C, D) = 9, \; f(D, t) = 9$.

• Residual capacities:

$c_f(s, C) = 1, \; c_f(C, s) = 9$. $c_f(C, D) = 0$ (Saturated!), $c_f(D, C) = 9$. $c_f(D, t) = 1, \; c_f(t, D) = 9$.

• Flow value: $|f| = 4 + 9 = 13$.

Augmentation 3:

• BFS shortest path:

Path $p_3: s \to A \to D \to t$ (length 3 edges).

• Capacities along $p_3$:

$c_f(s, A) = 6, \; c_f(A, D) = 8, \; c_f(D, t) = 1$.

• Bottleneck: $\Delta_3 = \min(6, 8, 1) = 1$.
• Update flow:

$f(s, A) = 4 + 1 = 5$. $f(A, D) = 1$. $f(D, t) = 9 + 1 = 10$ (Saturated!).

• Residual capacities:

$c_f(s, A) = 5, \; c_f(A, s) = 5$. $c_f(A, D) = 7, \; c_f(D, A) = 1$. $c_f(D, t) = 0$ (Saturated!), $c_f(t, D) = 10$.

• Flow value: $|f| = 13 + 1 = 14$.

Augmentation 4:

• BFS shortest path:

Path $p_4: s \to A \to D \to B \to t$ (length 4 edges).

• Capacities along $p_4$:

$c_f(s, A) = 5, \; c_f(A, D) = 7, \; c_f(D, B) = 6, \; c_f(B, t) = 6$.

• Bottleneck: $\Delta_4 = \min(5, 7, 6, 6) = 5$.
• Update flow:

$f(s, A) = 5 + 5 = 10$ (Saturated!). $f(A, D) = 1 + 5 = 6$. $f(D, B) = 5$. $f(B, t) = 4 + 5 = 9$.

• Residual capacities:

$c_f(s, A) = 0$ (Saturated!), $c_f(A, s) = 10$. $c_f(A, D) = 2, \; c_f(D, A) = 6$. $c_f(D, B) = 1, \; c_f(B, D) = 5$. $c_f(B, t) = 1, \; c_f(t, B) = 9$.

• Flow value: $|f| = 14 + 5 = 19$.

Augmentation 5:

• Looking for path from $s$:

$c_f(s, A) = 0$. Only outgoing edge from $s$ with residual capacity $>0$ is $(s, C)$ with $c_f(s, C) = 1$.

• From $C$:

$c_f(C, D) = 0$. No other outgoing edges from $C$.

• BFS terminates: No path exists from $s$ to $t$ in $G_f$!

2. Maximum Flow Value

The maximum flow achieved is:

3. Reachability Set and Minimum Cut Verification

In the final residual network $G_f$, find all vertices reachable from $s$:

• Start at $s$.
• Can reach $C$ via edge $(s, C)$ because $c_f(s, C) = 1 > 0$.
• From $C$: no outgoing residual edges with capacity $> 0$.
• From $s$: edge to $A$ has $c_f(s, A) = 0$.

Thus, the set of reachable vertices from $s$ is:

The complement set is:

Calculate the cut capacity $c(S, T)$:

(Note: edge $(A, C)$ goes from $T$ to $S$, so it is NOT included).

Since $|f^*| = 19 = c(S, T)$, the Max-Flow Min-Cut theorem is verified with exact equality! $\blacksquare$

1. Proof of Flow Conservation Lemma Across Cuts

Let $(S, T)$ be any $(s, t)$-cut, so $s \in S$ and $t \in T = V \setminus S$. By definition of flow value, for the source node $s$:

For every intermediate node $u \in S \setminus \{s\}$ (since $t \notin S$):

Summing these expressions over all vertices $u \in S$:

Now split the summation over $v \in V$ into $v \in S$ and $v \in T$:

In the first two double sums, both indices $u$ and $v$ range over $S$. Renaming dummy variables reveals that $\sum_{u \in S}\sum_{v \in S} f(u, v)$ and $\sum_{u \in S}\sum_{v \in S} f(v, u)$ are identical sums of internal edge flows, so they cancel completely! What remains is:

Thus, the net flow across any cut $(S, T)$ strictly equals $|f|$. $\blacksquare$

2. Proof of Weak Duality

By part 1:

By the capacity constraint, flow is non-negative, so $f(v, u) \ge 0$, which implies $-\sum_{v \in T}\sum_{u \in S} f(v, u) \le 0$. Furthermore, $f(u, v) \le c(u, v)$ for all edges. Therefore:

Hence, the capacity of any cut is an upper bound on the value of any feasible flow:

3. Proof of Strong Duality (Max-Flow Min-Cut Theorem)

Let $f^$ be a feasible flow such that the residual network $G_{f^}$ contains no augmenting paths from $s$ to $t$. Define the set:

and let $T^ = V \setminus S^$.

1. $(S^*, T^*)$ is a valid $(s, t)$-cut:

• Clearly $s \in S^*$ (path of length 0).
• Since $G_{f^}$ contains no path from $s$ to $t$, $t \notin S^$, which means $t \in T^*$.

2. Analysis of edges crossing from $S^*$ to $T^*$:

Let $u \in S^$ and $v \in T^$. Suppose for contradiction that $(u, v) \in E$ and $f^*(u, v) < c(u, v)$. Then the residual capacity is:

This implies that $(u, v)$ is an edge in the residual graph $G_{f^*}$! Since $u \in S^$, there is a path from $s$ to $u$ in $G_{f^}$. Appending edge $(u, v)$ yields a path from $s$ to $v$ in $G_{f^}$, meaning $v \in S^$. This contradicts $v \in T^*$! Therefore, for every edge $(u, v) \in E$ with $u \in S^, v \in T^$, we must have:

3. Analysis of backward edges from $T^*$ to $S^*$:

Suppose for contradiction that $(v, u) \in E$ with $v \in T^, u \in S^$ and $f^*(v, u) > 0$. Then the backward residual capacity is:

This again implies $(u, v) \in E_{f^}$, making $v$ reachable from $s$ in $G_{f^}$ ($v \in S^*$), another contradiction! Therefore, for every edge $(v, u) \in E$ with $v \in T^, u \in S^$:

Now compute the net flow across $(S^, T^)$ using Lemma 8.1:

By Weak Duality, no flow can exceed $c(S^, T^)$, so $f^$ achieves the absolute maximum possible flow, and $(S^, T^*)$ achieves the absolute minimum possible cut capacity. Hence:

1. Construction of Canonical Flow Network $G'$

Given bipartite graph $G = (X \cup Y, E)$:

• Vertex set: $V' = X \cup Y \cup \{s, t\}$, where $s$ is a new source and $t$ is a new sink.
• Directed edge set and capacities:

1. For each $x \in X$, add edge $(s, x)$ with capacity $c(s, x) = 1$.
2. For each $y \in Y$, add edge $(y, t)$ with capacity $c(y, t) = 1$.
3. For each undirected edge $\{x, y\} \in E$ with $x \in X, y \in Y$, add directed edge $(x, y)$ with capacity $c(x, y) = \infty$ (or $c(x, y) = 1$).

2. Integrality and Matching Equivalence

By the Integrality Theorem for Network Flows: If all edge capacities are integers, the Ford-Fulkerson algorithm (with integer additions) terminates with a flow where $f(e) \in \mathbb{Z}$ for every edge $e$.

• For each edge $(s, x)$, capacity is 1, so $f(s, x) \in \{0, 1\}$.
• For each edge $(y, t)$, capacity is 1, so $f(y, t) \in \{0, 1\}$.
• By conservation of flow at $x \in X$: $\sum_{y \in Y} f(x, y) = f(s, x) \le 1$. Thus, at most one outgoing edge from $x$ carries flow 1.
• By conservation of flow at $y \in Y$: $\sum_{x \in X} f(x, y) = f(y, t) \le 1$. Thus, at most one incoming edge into $y$ carries flow 1.

Therefore, the set of edges:

is a valid matching in $G$ (no two edges share a vertex). The size of the matching is:

Conversely, any matching $M$ of size $k$ yields a valid integer flow of value $k$. Thus:

3. Proof of Hall's Marriage Theorem via Max-Flow Min-Cut

Necessity ($\implies$):

If a matching $M$ saturates all of $X$, then for any subset $A \subseteq X$, the edges of $M$ incident with $A$ match each element of $A$ to a distinct element in $Y$. All these targets belong to $N(A)$. Therefore, $|N(A)| \ge |A|$.

Sufficiency ($\impliedby$):

Assume Hall's condition holds: $\forall A \subseteq X, |N(A)| \ge |A|$. We must prove that the maximum flow satisfies $|f^*| = |X|$. Suppose for contradiction that $|f^*| < |X|$. By the Max-Flow Min-Cut Theorem, there exists an $(s, t)$-cut $(S, T)$ with capacity:

where $s \in S$ and $t \in T$.

Define the partition of $X$ and $Y$ by the cut:

Now examine the edges crossing from $S$ to $T$:

1. Edges from $s$ to $X_T$: Each has capacity 1. There are $|X_T|$ such edges.
2. Edges from $Y_S$ to $t$: Each has capacity 1. There are $|Y_S|$ such edges.
3. Edges from $X_S$ to $Y_T$: Each has capacity $\infty$.

Since $c(S, T) < |X| < \infty$, the cut capacity must be finite! Therefore, there can be no edges from $X_S$ to $Y_T$:

This implies that all neighbors of $X_S$ in $G$ must lie inside $Y_S$:

Now calculate the capacity of the cut:

Since $X$ is partitioned into $X_S$ and $X_T$, $|X_T| = |X| - |X_S|$. Substitute this into the inequality:

Subtracting $|X|$ from both sides:

Since $|N(X_S)| \le |Y_S|$, we obtain:

Letting $A = X_S \subseteq X$, we have constructed a subset $A$ such that:

This directly contradicts Hall's Condition! Therefore, the contradiction assumption was false. We must have $|f^*| = |X|$, guaranteeing a matching that saturates all of $X$. $\blacksquare$

4. Menger's Theorem for Edge-Disjoint Paths

Let $G = (V, E)$ be a directed graph with source $s$ and sink $t$. Assign every edge unit capacity $c(e) = 1$.

1. By the Integrality Theorem, the maximum flow $f^$ is an integer flow with $f^(e) \in \{0, 1\}$.
2. By flow decomposition, any $0-1$ flow can be decomposed into $|f^*|$ edge-disjoint directed paths from $s$ to $t$.
3. By the Max-Flow Min-Cut Theorem, $|f^| = c(S^, T^*)$.
4. Since every edge has capacity 1, $c(S^, T^)$ is precisely the number of edges crossing from $S^$ to $T^$, which forms a minimal edge cut disconnecting $s$ from $t$.

Hence, the maximum number of edge-disjoint paths from $s$ to $t$ equals the minimum number of edges whose removal disconnects $s$ and $t$. $\blacksquare$