Maximum Flow

Motivation and Definitions

The problem of sending as much flow (e.g., oil, data) as possible from source $s$ to sink $t$ through a network with capacity constraints.

Definition 1. A flow network is a directed graph $G = (V, E)$ where each edge $e$ has a nonnegative capacity $c_e$ and two special nodes (source $s$, sink $t$).

Simplifying assumptions: No edges enter $s$ or leave $t$; every node has at least one incident edge; all capacities are integers.

Definition 2. An $s$-$t$ flow $f: E \to \mathbb{R}_+$ satisfies:

Capacity condition: $0 \leq f(e) \leq c_e$ for all $e$

Flow conservation: $f^{in}(v) = f^{out}(v)$ for all $v \in V \setminus \lbrace s,t\rbrace$

Definition 3. The value of a flow: $v(f) := \sum_{e \text{ out of } s} f(e)$

Problem (Maximum Flow). Find an $s$-$t$ flow of maximum value.

Residual Graph

A greedy approach (always augmenting along any path) is insufficient: once flow is sent, it cannot be redirected. We fix this by introducing the residual graph, which allows canceling flow.

Definition 4. The residual graph $G_f$ for flow $f$:

Node set: same as $G$

Forward edge: for $e = \langle u,v \rangle$ with $f(e) < c_e$, add $\langle u,v \rangle$ with capacity $c_e - f(e)$

Backward edge: for $e = \langle u,v \rangle$ with $f(e) > 0$, add $\langle v,u \rangle$ with capacity $f(e)$

An $s$-$t$ path in $G_f$ is called an augmenting path.

Augment Function

function Augment(f, P):
    b ← minimum residual capacity over all edges in P
    for each e = ⟨u,v⟩ ∈ P do
        if e is forward edge: f(e) ← f(e) + b
        else:
            e' := ⟨v,u⟩
            f(e') ← f(e') - b
    return f

Lemma 1. If $f$ is a valid $s$-$t$ flow and $P$ is a simple $s$-$t$ path in $G_f$, then Augment(f, P) returns a valid $s$-$t$ flow.

Proof sketch. For capacity: forward edges $f’(e) = f(e)+b \leq c_e$; backward edges $f’(e’) = f(e’)-b \geq 0$. For flow conservation: at each internal node $v$ of $P$, exactly one edge enters and one leaves, so the net change is zero. ∎

Ford-Fulkerson Algorithm

f(e) ← 0  for all e ∈ E
while there exists an s-t path in Gf do
    P ← simple s-t path in Gf
    f ← Augment(f, P)
return f

Termination and Complexity

Lemma 2. Throughout the algorithm, all edge flows and residual capacities are always integers.

Proof. By induction on iterations; the bottleneck $b$ is always an integer. ∎

Lemma 3. Each iteration strictly increases $v(f)$.

Proof. All residual capacities are positive, so $b > 0$. The first edge of $P$ is a forward edge leaving $s$ (not revisited), so $f^{out}(s)$ increases by $b > 0$. ∎

Define $C := \sum_{e \text{ out of } s} c_e$.

Lemma 4. The algorithm terminates in at most $C$ iterations.

Proof. $v(f) \leq C$ always. Each iteration increases $v(f)$ by at least 1 (integer, by Lemma 2). Starting from 0, at most $C$ iterations follow. ∎

Theorem 1. Ford-Fulkerson runs in $O(mC)$ time.

Note: This is not a polynomial-time algorithm. $C$ can be exponential in the number of input bits, making this a pseudo-polynomial algorithm. A strongly polynomial algorithm is bounded only by the number of input entries.

$s$-$t$ Cut

Definition 5. $(S, \bar{S})$ is an $s$-$t$ cut if $s \in S$, $t \in \bar{S}$, $S \cap \bar{S} = \emptyset$, $S \cup \bar{S} = V$.

Definition 6. Capacity of cut $(S, \bar{S})$: $c(S, \bar{S}) := \sum_{e \text{ out of } S} c_e$

Lemma 5. For any $s$-$t$ flow $f$ and $s$-$t$ cut $(S, \bar{S})$: $v(f) = f^{out}(S) - f^{in}(S)$.

Proof. Sum $[f^{out}(v) - f^{in}(v)]$ over all $v \in S$: internal edges cancel; flow conservation makes all $v \neq s$ contribute 0. ∎

Corollary 1. $v(f) \leq c(S, \bar{S})$ for any flow $f$ and cut $(S, \bar{S})$.

Max-Flow = Min-Cut

Lemma 6. If $G_f$ has no $s$-$t$ path, there exists a cut $(S^, \bar{S}^)$ with $v(f) = c(S^, \bar{S}^)$.

Proof. Let $S$ = vertices reachable from $s$ in $G_f$, $\bar{S} = V \setminus S$.

Each edge $e = \langle u,v \rangle$ leaving $S$ in $G$: since $v \notin S$, $\langle u,v \rangle \notin G_f$ → $f(e) = c_e$.
Each edge $e = \langle u,v \rangle$ entering $S$ in $G$: since $u \notin S$, backward edge $\langle v,u \rangle \notin G_f$ → $f(e) = 0$.

Therefore $v(f) = f^{out}(S) - f^{in}(S) = c(S, \bar{S})$. ∎

Corollary 2 (Ford-Fulkerson returns max flow). The algorithm terminates when $G_f$ has no $s$-$t$ path, at which point Lemma 6 gives an equal-value cut, making $f$ optimal.

Theorem 2 (Max-Flow Min-Cut). In every flow network, the value of the maximum $s$-$t$ flow equals the capacity of the minimum $s$-$t$ cut.

Theorem 3 (Integrality). If all capacities are integers, there exists a maximum flow in which every edge carries integer flow.

Proof. Ford-Fulkerson returns such a flow. ∎