21 Flow Networks, Cuts, Max-Flow Min-Cut, Residual Networks, Ford-Fulkerson

Lecture from: 08.05.2025 | Video: Homelab

Many problems in computer science, operations research, and logistics can be modeled as moving something through a network: data, water, goods, traffic, etc. A central question in such settings is:

What is the maximum amount of flow that can be pushed from a source node to a sink node, respecting the capacity constraints of the network?

This is the maximum flow problem, and today we study it rigorously.

Flow Networks

Let $G = (V, E)$ be a directed graph representing a network. A flow network has the following properties:

Each edge $(u, v) \in E$ has a capacity $c (u, v) \geq 0$ .
There is a distinguished source vertex $s \in V$ .
There is a distinguished sink vertex $t \in V$ , with $s \neq = t$ .

Think of the network as a system of pipes. The source $s$ pumps fluid in, and the sink $t$ collects the outflow.

Definition and Constraints

A flow in the network is a function:

f : V \times V \to R

satisfying:

Capacity Constraint

\forall (u, v) \in E, 0 \leq f (u, v) \leq c (u, v)

Flow Conservation (except at source and sink):

\forall v \in V ∖ {s, t}, u \in V \sum f (u, v) = w \in V \sum f (v, w)

Skew Symmetry (convenience condition):

f (u, v) = - f (v, u)

This ensures that defining $f (u, v)$ for existing edges is enough - the reverse flow is implicitly handled.

Value of a Flow

The value of a flow $f$ , denoted $∣ f ∣$ , is (given there is no inflow at the source) the total flow leaving the source:

∣ f ∣ = v \in V \sum f (s, v)

By flow conservation, this is also equal to the flow entering the sink $t$ :

∣ f ∣ = u \in V \sum f (u, t)

Cuts in Flow Networks

A cut in the network is a partition of the vertex set $V$ into two disjoint subsets $S$ and $T$ such that:

s \in S, t \in T

The capacity of a cut $(S, T)$ is the total capacity of all edges from $S$ to $T$ :

c (S, T) = u \in S, v \in T \sum c (u, v)

Example:

How Cuts Bound the Value of a Flow

Before proving the Max-Flow Min-Cut Theorem, it’s important to understand the role of cuts in bounding flows.

Observation

Any $s$ - $t$ cut in a flow network places an upper bound on the value of any feasible flow.

Let’s see why this is true.

Setup: Flow and Cut

Let $f$ be any valid flow in the network, and let $(S, T)$ be any cut with:

$s \in S$
$t \in T$
$S \cup T = V$ , $S \cap T = \emptyset$

Define the net flow across the cut from $S$ to $T$ as:

f (S, T) = u \in S, v \in T \sum f (u, v) - u \in T, v \in S \sum f (u, v)

That is, total flow out of $S$ minus flow into $S$ from $T$ .

Key Lemma

∣ f ∣ = f (S, T)

This may seem surprising at first, but it’s true for any $s$ - $t$ cut. Here’s the intuition:

The total flow leaving the source $s$ must eventually cross from $S$ to $T$ , because the sink $t \in T$ lies beyond the cut. All flow must “escape” through the cut.

Let’s sketch a brief justification.

Sketch of Proof

By Flow Conservation: For every node $v \in V ∖ {s, t}$ , inflow equals outflow.
Sum net flow over all nodes in $S$ : This collapses (due to conservation) to:
$f (S, T) = v \in S \sum u \in V \sum f (v, u) = v \in S \sum net outflow (v)$
Only the source $s$ can have net outflow $> 0$ , and everything else balances. So:
$f (S, T) = ∣ f ∣$

Bounding Flow with Cut Capacity

Now, since $f (u, v) \leq c (u, v)$ for all edges (capacity constraint), and $f (u, v) \geq 0$ for $u \in S, v \in T$ , we have:

f (S, T) \leq u \in S, v \in T \sum c (u, v) = c (S, T)

Hence:

∣ f ∣ = f (S, T) \leq c (S, T)

The Max-Flow Min-Cut Theorem

The Max-Flow Min-Cut Theorem is one of the most elegant results in combinatorial optimization. It connects the maximum amount of flow that can be pushed through a network with the minimum bottleneck that separates source from sink.

Intuition

Flow through a network is constrained not by the largest paths, but by the narrowest bottlenecks.

Imagine a system of pipes from a source to a sink. The maximum water flow isn’t determined by the biggest pipes-it’s limited by the thinnest one that separates the source from the rest. That’s exactly what the Min-Cut is.

Theorem (Max-Flow Min-Cut)

In any flow network, the maximum value of a flow equals the minimum capacity of an $s$ - $t$ cut.

Formally:

f is a flow max val (f) = (S, T) min cap (S, T)

This holds for:

integer capacities without anti-parallel edges (proved with Ford-Fulkerson)
arbitrary real capacities (via more advanced arguments)

Proof (via Ford-Fulkerson Residual Network)

Assumption

We assume Ford-Fulkerson has been applied and terminated. That is, no more augmenting $s$ - $t$ paths exist in the residual graph $G_{f}$ .

Step 1: Build the Residual Graph

From flow $f$ , we define a residual network $G_{f} = (V, E_{f})$ with residual capacities $r_{f} (u, v)$ :

Forward edge $(u, v) \in E_{f}$ if $f (u, v) < c (u, v)$ , with $r_{f} (u, v) = c (u, v) - f (u, v)$
Backward edge $(v, u) \in E_{f}$ if $f (u, v) > 0$ , with $r_{f} (v, u) = f (u, v)$

Step 2: Construct a Cut

Let:

S := {v \in V ∣ reachable from s in G_{f}}, T := V ∖ S

This gives us an $s$ - $t$ cut $(S, T)$ . Importantly:

$s \in S$
$t \in / S$ (since $s ↛ t$ in $G_{f}$ )

Step 3: Analyze the Flow Across the Cut

Every edge $(u, v) \in E$ with $u \in S$ , $v \in T$ must be saturated:

f (u, v) = c (u, v)

(else $(u, v)$ would be in $G_{f}$ , and $v$ would be reachable, contradicting $v \in T$ )

Every edge $(v, u) \in E$ with $v \in T$ , $u \in S$ must be empty:

f (v, u) = 0

(otherwise a backward edge $(u, v)$ would exist in $G_{f}$ , making $v \in S$ , a contradiction)

Step 4: Use the Value Identity

From the earlier lemma:

val (f) = f (S, T) - f (T, S)

Given:

$f (S, T) = \sum_{(u, v), u \in S, v \in T} f (u, v) = cap (S, T)$
$f (T, S) = 0$