Network Flows - Part 3

In Part 2, we defined flow networks, flows, and cuts, and proved weak duality: the value of any flow is at most the capacity of any cut. We ended with an open question — is our flow of value $5$ actually optimal, and can we find a matching cut? In this part, we'll develop the tools to answer both questions at once. The key idea is the residual graph, which tells us exactly where and how we can improve a flow.

Residual Graphs

Given a flow $f$ in a network, some arcs might still have room for more flow, while others are completely saturated. But there's a subtlety: even on a saturated arc, we can effectively "undo" some of the flow by sending flow backwards. The residual graph captures both possibilities.

Definition 6. Given a flow network $N = (D, s, t, c)$ with $D = (V, A)$ and a flow $f$, the residual capacity of an arc $(u,v) \in A$ is defined as:

• Forward residual capacity: $c_f(u,v) = c(u,v) - f(u,v)$, representing how much more flow can be pushed along $(u,v)$.
• Backward residual capacity: $c_f(v,u) = f(u,v)$, representing how much flow on $(u,v)$ can be "cancelled" by sending flow from $v$ back to $u$.

Definition 7. The residual graph $D_f = (V, A_f)$ is the directed graph on the same vertex set $V$, where $A_f$ contains every arc with positive residual capacity: $A_f = \{(u,v) : c_f(u,v) > 0\}.$

The forward arcs in the residual graph tell us where we can send more flow. The backward arcs tell us where we can reroute flow that's already been assigned. This ability to "undo" flow is what makes residual graphs so powerful — it means we don't have to get the flow right on the first try.

Let's build the residual graph for our running example. Recall the flow from Part 2: $f(s,a) = 3$, $f(s,b) = 2$, $f(a,b) = 2$, $f(a,t) = 1$, $f(b,t) = 4$, with value $|f| = 5$.

For each original arc, we compute the forward and backward residual capacities:

The residual graph has arcs (omitting those with zero residual capacity): $(s,a)$ with capacity $1$, $(a,s)$ with $3$, $(b,s)$ with $2$, $(a,b)$ with $1$, $(b,a)$ with $2$, $(t,a)$ with $1$, $(b,t)$ with $1$, and $(t,b)$ with $4$.

Augmenting Paths

Now the key question: does the residual graph contain a path from $s$ to $t$? If it does, we can push more flow along that path and increase the flow value. Such a path is called an augmenting path.

Definition 8. An augmenting path (with respect to a flow $f$) is a directed path from $s$ to $t$ in the residual graph $D_f$.

Let's look at our residual graph. Can we find a path from $s$ to $t$? Starting at $s$, we can go to $a$ (residual capacity $1$). From $a$, we can go to $b$ (residual capacity $1$). From $b$, we can go to $t$ (residual capacity $1$). The path $s \to a \to b \to t$ is an augmenting path.

How much flow can we push along this path? We're limited by the smallest residual capacity along the way — the bottleneck.

Definition 9. The bottleneck of an augmenting path $P$ is the minimum residual capacity along $P$: $\Delta(P) = \min_{(u,v) \in P} c_f(u,v).$

For our path $s \to a \to b \to t$, the bottleneck is $\min(1, 1, 1) = 1$. We can push one additional unit of flow.

To update the flow, we increase the flow by $\Delta(P)$ on each forward arc of the path and decrease it by $\Delta(P)$ on each backward arc. In our case, all arcs on the path are forward arcs of the original network, so we simply add $1$ to each:

$f'(s,a) = 4, \quad f'(a,b) = 3, \quad f'(b,t) = 5.$

The arcs $f(s,b) = 2$ and $f(a,t) = 1$ remain unchanged. The new flow has value $|f'| = f'(s,a) + f'(s,b) = 4 + 2 = 6$.

Let's verify that $f'$ is still a valid flow. At vertex $a$: incoming $f'(s,a) = 4$, outgoing $f'(a,b) + f'(a,t) = 3 + 1 = 4$ — conservation holds. At vertex $b$: incoming $f'(s,b) + f'(a,b) = 2 + 3 = 5$, outgoing $f'(b,t) = 5$ — conservation holds. All capacity constraints are satisfied too.

Can we push even more? Let's build the new residual graph for $f'$:

The residual arcs are $(a,s)$, $(b,s)$, $(b,a)$, $(t,a)$, and $(t,b)$ — all backward arcs. Crucially, vertex $s$ has no outgoing arcs in the residual graph, so there is no path from $s$ to $t$. We can't push any more flow.

The Max-Flow Min-Cut Theorem

The observation above — that a flow is maximum precisely when no augmenting path exists — is one direction of the most important theorem in network flow theory. The other direction connects this to cuts, establishing that the maximum flow value always equals the minimum cut capacity.

Theorem 1 (Max-Flow Min-Cut Theorem, Ford and Fulkerson, 1956). In a flow network $N = (D, s, t, c)$, the following three statements are equivalent:

(i) $f$ is a maximum flow.

(ii) There is no augmenting path with respect to $f$ (i.e., no $s$-$t$-path in the residual graph $D_f$).

(iii) There exists an $s$-$t$-cut $(S, T)$ with $|f| = c(S, T)$.

Moreover, $\max_f |f| = \min_{(S,T)} c(S,T)$.

Proof. We prove three implications.

(i) $\Rightarrow$ (ii): We prove the contrapositive. Suppose there exists an augmenting path $P$ from $s$ to $t$ in $D_f$ with bottleneck $\Delta(P) > 0$. Define a new flow $f'$ by modifying $f$ along $P$: for each arc $(u,v)$ on $P$, if $(u,v)$ is a forward arc of the original network, set $f'(u,v) = f(u,v) + \Delta(P)$; if $(u,v)$ corresponds to a backward arc (i.e., $(v,u)$ is in the original network), set $f'(v,u) = f(v,u) - \Delta(P)$. All other arcs keep their flow. One can verify that $f'$ satisfies the capacity constraints (by definition of the residual capacity) and flow conservation (since on the path, each intermediate vertex gains $\Delta(P)$ incoming and $\Delta(P)$ outgoing). The value increases: $|f'| = |f| + \Delta(P) > |f|$, so $f$ is not maximum.

(ii) $\Rightarrow$ (iii): Suppose there is no augmenting path. Let $S$ be the set of all vertices reachable from $s$ in the residual graph $D_f$, and let $T = V \setminus S$. Since $t$ is not reachable from $s$, we have $s \in S$ and $t \in T$, so $(S, T)$ is a valid $s$-$t$-cut.

Now consider any arc $(u,v)$ in the original network with $u \in S$ and $v \in T$. Since $v$ is not reachable from $s$ in $D_f$, the forward residual capacity must be zero: $c_f(u,v) = c(u,v) - f(u,v) = 0$, which means $f(u,v) = c(u,v)$. Similarly, for any arc $(u,v)$ with $u \in T$ and $v \in S$, the backward residual capacity from $u$ to $v$ would make $v$ reachable from $u$ — but $u \in T$ is not reachable from $s$, so this isn't useful. However, the forward residual capacity of the reverse direction tells us: since $v \in S$ is reachable but $u \in T$ is not, we need $c_f(v,u) = f(u,v) = 0$.

Using the flow-cut identity from Part 2: $|f| = \sum_{\substack{(u,v) \in A \\ u \in S, \, v \in T}} f(u,v) - \sum_{\substack{(u,v) \in A \\ u \in T, \, v \in S}} f(u,v) = \sum_{\substack{(u,v) \in A \\ u \in S, \, v \in T}} c(u,v) - 0 = c(S, T).$

(iii) $\Rightarrow$ (i): If $|f| = c(S, T)$ for some cut $(S, T)$, then by weak duality (Lemma 1 from Part 2), every flow $f'$ satisfies $|f'| \leq c(S, T) = |f|$. So $f$ is maximum.

The equivalence of (i), (ii), and (iii) immediately gives us the max-flow min-cut equality: $\max_f |f| = \min_{(S,T)} c(S, T)$.

Applying the Theorem

Let's use the theorem to wrap up our running example. After augmenting, we obtained a flow $f'$ with value $6$ and no augmenting path — condition (ii) is satisfied. By the theorem, $f'$ is a maximum flow.

The proof of (ii) $\Rightarrow$ (iii) also tells us how to find the minimum cut: take $S$ to be the vertices reachable from $s$ in the residual graph. In our case, $s$ has no outgoing arcs in $D_{f'}$, so $S = \{s\}$ and $T = \{a, b, t\}$. The cut capacity is $c(s,a) + c(s,b) = 4 + 2 = 6$, which matches $|f'| = 6$.

This confirms that the maximum flow is $6$ and the minimum cut is $(\{s\}, \{a,b,t\})$ with capacity $6$. The bottleneck in this network is the total capacity leaving the source — the arcs out of $s$ are the limiting factor.

Integrality

There is one more property worth mentioning. In many applications, we want integer flows — you can't ship half a truck or assign half a person to a task. Fortunately, when the capacities are integers, we're guaranteed that an integer maximum flow exists.

Theorem 2 (Integrality Theorem). If all capacities in a flow network are integers, then there exists a maximum flow that is integer-valued.

This follows from the augmenting path approach: if we start with the zero flow (which is integer) and always augment along paths in the residual graph, the bottleneck $\Delta(P)$ is always an integer (since it's the minimum of integer residual capacities). Each augmentation preserves integrality, and the process terminates because the flow value increases by at least $1$ each time and is bounded by the finite cut capacity¹.

Looking Ahead

We now have the central theorem of network flow theory and a clear strategy for finding maximum flows: repeatedly find augmenting paths and push flow along them. But several questions remain. How do we choose augmenting paths? Does the process always terminate? How fast is it? In the next part, we'll answer these questions by studying the Ford-Fulkerson method and the Edmonds-Karp algorithm, which turns the augmenting path idea into an efficient algorithm with guaranteed polynomial running time.