MIT 6.1220 — Lecture 9

Maximum Flow (Part I)

Problem. (Max Flow) Consider a directed graph $G = (V, E)$ with a source vertex $s$ and a sink vertex $t$ . Every (directed) edge has a capacity $c: E \to \mathbb{R}^{\geq 0}$ , extended to all of $V \times V$ by $c(u, v) = 0$ when $(u, v) \not \in E$ .

We'd like to assign a flow to every edge such that:

For any $e \in E$ , the flow across $e$ is at most the capacity of $e$ .
There is zero net flow into or out of any vertex other than $s$ or $t$ .

Formally, let $f: V \times V \to \mathbb{R}$ such that $f(u, v)$ is the (signed) flow from $u$ to $v$ , with $f(u, v) = -f(v, u)$ and $f(u, v) \leq c(u, v)$ for all $u, v \in V$ (so $f(u, v) = 0$ if neither $(u, v)$ nor $(v, u)$ is in $E$ ).

The net flow $|f|$ is defined by $\sum_{v \in V} f(s, v)$ . Find the maximum possible total flow.

Claim. Any flow assignment can be decomposed as the linear combination of paths from $s$ to $t$ and cycles.

Proof: Just induct. You never get “stuck” because of the “zero net flow” constraint, which is invariant. $\blacksquare$

There's an easy upper-bound on the max flow: the minimum cut.

Definition (Min Cut). Cut the directed graph via $V = S \sqcup T$ , with $s \in S$ and $t \in T$ . We define:

The total cut $c(S)$ is the sum of the (nonnegative) capacities $c(a, b)$ for all $a \in S$ and $b \in T$ .
The total flow $f(S)$ is the sum of the (not necessarily nonnegative) flows $f(a, b)$ for all $a \in S$ and $b \in T$ .

Evidently, $f(S) \leq c(S)$ .

Claim. Consider any flow assignment $f$ . Given any two cuts $S_1 \sqcup T_1$ and $S_2 \sqcup T_2$ , we have $f(S_1) = f(S_2)$ .

(By corollary, for any cut $S \sqcup T$ , we have $f(S)$ is the net flow of $f$ .)

Proof: Because the divergence is zero. (Formally, use the decomposition of flow into paths and cycles.) $\blacksquare$

Be careful, though—the above does not say that all cuts have the same cut. It only says that all cuts have the same flow—that is, the same measure with respect to edge weights with divergence $0$ everywhere.

Claim. The maximum possible flow of a graph equals the minimum possible cut.

Here's the key idea.

Definition (Residual Network). Given an assigned flow $f$ to a graph $G = (V, E)$ , the residual network consists of $G_f = (V, E_f)$ with edge weights $c_f(u, v) := c(u, v) - f(u, v)$ , and edges $E_f := \{(u, v) \in V \times V \mid c_f(u, v) > 0\}$ .

Importantly, some edges in $G_f$ will have greater weight than the corresponding edge in $G$ , because flow along an edge $u \to v$ increases $c_f(v, u)$ .

Think of this as reflecting our ability to “undo our mistakes”.

Definition (Augmenting Path). An augmenting path is a path $s \to \dots \to t$ in the residual network $G_f$ .

Claim. The max flow is zero if and only if there is a cut of zero.

Proof: If there's a zero cut, there's obviously zero flow. If there is zero possible flow, that means there is no path from $s$ to $t$ of positive capacity, so the cut defined by $S := \{v \in V \mid \text{there is a positive-capacity path from } s \text{ to } v\}$ works. $\blacksquare$

It turns out that the zero case is all we need! (Like proving JNF…)

Claim. The maximum possible flow is equal to the minimum possible cut.

Proof: Consider an optimal flow assignment $f$ . Then $G_f$ must have zero maximum possible flow, or else $f$ would not be optimal. This means $G_f$ has a cut $S \sqcup T$ of zero.

Claim. For any graph $G$ , any cut $S$ , and any flow $f$ , we have $c_f(S) = c(S) - f(S)$ .

Proof: Pretty obvious. Do the algebra if you want. $\square$

When there is a cut $S \sqcup T$ of value zero in $G_f$ , we have $f(S) = c(S)$ . Lower bound meets upper bound. $\blacksquare$

More generally, the following is true.

Claim. Given any network $G$ and any flow $f$ , the following statements are equivalent.

We have that $f$ is a max flow.
We have that $|f| = c(S)$ for some cut $S$ .
We have that $G_f$ has no augmenting paths.

Proof: Omitted to be DRY. (I am not writing a helper proof.) $\blacksquare$

And so the most naive algorithm actually just works.

Solution. (Ford-Fulkerson) Repeatedly find augmenting paths $P := s \to \dots \to t$ , then recompute the residual network each time. Repeat until no more augmenting paths exist. This is optimal.