47.04.03 · theoretical-cs / algorithms-analysis

Network Flow: Ford-Fulkerson, Augmenting Paths, and the Max-Flow Min-Cut Theorem

shipped3 tiersLean: none

Anchor (Master): CLRS 2022 Introduction to Algorithms 4e (MIT Press) §26.1-26.5; Tarjan 1983 Data Structures and Network Algorithms (SIAM) (preflow-push methods, minimum-cost flow)

Intuition Beginner

Imagine a network of pipes connecting a water source to a destination. Each pipe has a maximum capacity — it can carry only so much water per second. You want to push as much water as possible from source to destination without exceeding any pipe's limit.

This is the maximum flow problem. The answer is governed by a beautiful duality: the maximum amount you can push through the network equals the minimum capacity of any "bottleneck" cut. A cut is a partition of the network into two sides, with the source on one side and the destination on the other, and the cut's capacity is the total capacity of pipes crossing from the source side to the destination side.

The Ford-Fulkerson method finds the maximum flow by repeatedly searching for a path from source to destination that can carry more flow (an augmenting path), then pushing as much additional flow as that path allows. Each such push increases the total flow. When no augmenting path exists, the flow is maximum, and the method also identifies a minimum cut.

The max-flow min-cut theorem is one of the most widely applied results in combinatorial optimisation. It connects a maximisation problem (find the most flow) with a minimisation problem (find the smallest cut) and proves they always give the same value.

Visual Beginner

A 4-node flow network:

         10
    s ──────────→ a
    │             │
    │5            │8
    ↓             ↓
    b ──────────→ t
         7

Current flow: s→a: 8, a→t: 8, s→b: 3, b→t: 3
Residual: s→a: 2, a→s: 8, s→b: 2, b→s: 3, a→t: 0, t→a: 8, b→t: 4, t→b: 3

Cut	Source side	Sink side	Cut capacity
${s}, {a, b, t}$	${s}$	${a, b, t}$	$10 + 5 = 15$
${s, a}, {b, t}$	${s, a}$	${b, t}$	$8 + 5 = 13$
${s, b}, {a, t}$	${s, b}$	${a, t}$	$10 + 7 = 17$
${s, a, b}, {t}$	${s, a, b}$	${t}$	$8 + 7 = 15$

The minimum cut has capacity 13, which equals the maximum flow.

Worked example Beginner

Consider the 4-node network above with source $s$ , sink $t$ , and intermediate nodes $a$ , $b$ . Capacities: $c (s, a) = 10$ , $c (s, b) = 5$ , $c (a, t) = 8$ , $c (b, t) = 7$ .

Step 1. Find an augmenting path: $s \to a \to t$ . Residual capacity along this path is $min (10, 8) = 8$ . Push 8 units. Now $f (s, a) = 8$ , $f (a, t) = 8$ .

Step 2. Find another augmenting path: $s \to b \to t$ . Residual capacity is $min (5, 7) = 5$ . Push 5 units. Now $f (s, b) = 5$ , $f (b, t) = 5$ .

Step 3. Search for another augmenting path. From $s$ , edge $s \to a$ has residual 2 (capacity 10 minus flow 8), edge $s \to b$ has residual 0. From $a$ , edge $a \to t$ has residual 0. No augmenting path exists.

Wait — let us check if there is a path through $a \to b$ or $b \to a$ (if such edges exist). In this network there are no direct edges between $a$ and $b$ . So no augmenting path exists.

Step 4. Total flow = $8 + 5 = 13$ . The minimum cut is ${s, a}$ vs. ${b, t}$ with capacity $c (a, t) + c (s, b) = 8 + 5 = 13$ . The max-flow min-cut theorem is satisfied.

Check your understanding Beginner

Formal definition Intermediate+

Definition (flow network). A flow network is a tuple $G = (V, E, s, t, c)$ where $(V, E)$ is a directed graph, $s \in V$ is the source, $t \in V$ is the sink ( $s \neq = t$ ), and $c : E \to R_{\geq 0}$ is the capacity function. We assume $(v, u) \in / E$ whenever $(u, v) \in E$ (no anti-parallel edges; these can be handled by introducing a dummy vertex).

Definition (flow). A flow in $G$ is a function $f : V \times V \to R$ satisfying:

Capacity constraint: For all $u, v \in V$ : $f (u, v) \leq c (u, v)$ .
Skew symmetry: For all $u, v \in V$ : $f (u, v) = - f (v, u)$ .
Flow conservation: For all $u \in V ∖ {s, t}$ : $\sum_{v \in V} f (u, v) = 0$ .

The value of the flow is $∣ f ∣ = \sum_{v \in V} f (s, v)$ .

Definition (residual network). Given a flow $f$ in $G$ , the residual capacity of $(u, v)$ is $c_{f} (u, v) = c (u, v) - f (u, v)$ . The residual network $G_{f} = (V, E_{f}, s, t, c_{f})$ where $E_{f} = {(u, v) : c_{f} (u, v) > 0}$ .

Definition (cut). An s-t cut is a partition $(S, T)$ of $V$ with $s \in S$ and $t \in T$ . The capacity of the cut is $c (S, T) = \sum_{u \in S, v \in T} c (u, v)$ . The flow across the cut is $f (S, T) = \sum_{u \in S, v \in T} f (u, v)$ .

Counterexamples to common slips

"The maximum flow equals the capacity of every cut." No. It equals the capacity of the minimum cut. Other cuts may have larger capacity.
"Residual capacity is always the capacity minus the flow on the forward edge." It is. But the residual network also contains reverse edges with capacity equal to the current flow, allowing flow to be redirected.
"Ford-Fulkerson always terminates in polynomial time." Not with arbitrary augmenting path choices. Using DFS, the method can take exponentially many iterations on networks with irrational capacities. The Edmonds-Karp algorithm (BFS for shortest augmenting paths) guarantees $O (V E^{2})$ time.

Key theorem with proof Intermediate+

Theorem (max-flow min-cut). In any flow network, the value of the maximum flow equals the capacity of the minimum s-t cut.

Proof. We show three equivalent statements: (1) $f$ is a maximum flow, (2) there is no augmenting path in $G_{f}$ , (3) $∣ f ∣ = c (S, T)$ for some cut $(S, T)$ .

(1 $\Rightarrow$ 2): If an augmenting path existed, we could increase $∣ f ∣$ , contradicting maximality.

(2 $\Rightarrow$ 3): Let $S$ be the set of vertices reachable from $s$ in $G_{f}$ , and $T = V ∖ S$ . Since no augmenting path exists, $t \in T$ . For any $u \in S, v \in T$ : $(u, v) \in / E_{f}$ , so $c_{f} (u, v) = 0$ , meaning $f (u, v) = c (u, v)$ . Also for $v \in T, u \in S$ : $f (v, u) = - f (u, v)$ , and since $(v, u) \in / E_{f}$ , $c_{f} (v, u) = 0$ means $f (v, u) \leq 0$ , so $f (u, v) \geq 0$ , but more importantly $f (v, u) = 0$ . Therefore $∣ f ∣ = f (S, T) = \sum_{u \in S, v \in T} f (u, v) = \sum_{u \in S, v \in T} c (u, v) = c (S, T)$ .

(3 $\Rightarrow$ 1): For any flow $f^{'}$ and any cut $(S, T)$ : $∣ f^{'} ∣ \leq c (S, T)$ (each edge contributes at most its capacity). So $∣ f^{'} ∣ \leq c (S, T) = ∣ f ∣$ , proving $f$ is maximum. $□$

Bridge. The max-flow min-cut theorem is the foundational reason duality pervades combinatorial optimisation: the equality $∣ f^{*} ∣ = c (S^{*})$ connects a maximisation and a minimisation problem, and every application of network flow reduces to finding this correspondence. This builds toward bipartite matching in 47.04.04, where the max-flow formulation of matching yields Koenig's theorem and Hall's marriage theorem as corollaries of the min-cut, and it appears again in 47.02.03 where NP-completeness reductions often encode Boolean constraints as flow networks. The central insight is that the residual network is dual to the cut structure, and putting these together gives a polynomial-time algorithm (Edmonds-Karp) that simultaneously computes the maximum flow and the minimum cut.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Run the Edmonds-Karp algorithm (BFS for shortest augmenting path) on the network: $V = {s, a, b, t}$ , $E = {(s, a), (s, b), (a, b), (a, t), (b, t)}$ , capacities $c (s, a) = 10, c (s, b) = 8, c (a, b) = 3, c (a, t) = 5, c (b, t) = 10$ . Report the maximum flow and the minimum cut.

Answer

Iteration 1: BFS finds path $s \to a \to t$ (length 2). Residual: $min (10, 5) = 5$ . Push 5.

Iteration 2: BFS finds path $s \to b \to t$ (length 2). Residual: $min (8, 10) = 8$ . Push 8.

Iteration 3: BFS finds path $s \to a \to b \to t$ (length 3). Residual: $min (5, 3, 2) = 2$ . Push 2.

Iteration 4: BFS finds path $s \to a \to b \to t$ again. Residual: $min (3, 1, 0) = 0$ . No augmenting path (actually $c_{f} (b, t) = 10 - 8 - 2 = 0$ ). Wait, let us recheck. After pushing 2 on $s \to a \to b \to t$ : $f (s, a) = 7, f (a, t) = 5, f (s, b) = 8, f (a, b) = 2, f (b, t) = 10$ . Residual of $b \to t$ : $10 - 10 = 0$ . So no more augmenting paths.

Total flow: $5 + 8 + 2 = 15$ . Minimum cut: ${s, a}, {b, t}$ with capacity $c (a, b) + c (a, t) + c (s, b) = 3 + 5 + 8 = 16$ . Hmm, let me recheck. Cut ${s, a, b}, {t}$ : $c (a, t) + c (b, t) = 5 + 10 = 15$ . This equals the flow. So the minimum cut has capacity 15.

Exercise 6 (hard, symbolic).

Show that maximum bipartite matching reduces to max-flow by constructing a flow network from a bipartite graph $G = (L \cup R, E)$ and proving that the maximum matching size equals the maximum flow value.

Answer

Construct network $G^{'} = (V^{'}, E^{'}, s, t, c)$ where $V^{'} = {s, t} \cup L \cup R$ . Edges: $(s, u)$ for all $u \in L$ with capacity 1, $(u, v)$ for all $(u, v) \in E$ with capacity 1, and $(v, t)$ for all $v \in R$ with capacity 1. Any matching $M$ in $G$ gives a flow of value $∣ M ∣$ by routing 1 unit along each matched edge. Conversely, any integral flow of value $k$ gives a matching of size $k$ : the unit flows on edges from $L$ to $R$ form a matching (capacity-1 constraints on source and sink edges ensure each vertex is matched at most once). By integrality of the flow, the maximum matching size equals the maximum flow.

Lean formalization Intermediate+

Mathlib has Mathlib.Combinatorics.SimpleGraph for basic graph structures but no flow network definition, no flow function with capacity and conservation constraints, and no max-flow min-cut theorem. The Ford-Fulkerson algorithm and the Edmonds-Karp implementation are absent. A Codex.Algorithms.MaxFlow module defining flow networks with a proof of the max-flow min-cut theorem would be the foundational target; this unit ships without it.

Advanced results Master

Theorem 1 (Edmonds-Karp: $O (V E^{2})$ time). The Edmonds-Karp algorithm, which uses BFS to find shortest augmenting paths in the residual network, terminates in at most $O (V E)$ augmentations, for a total running time of $O (V E^{2})$ ^{[CLRS §26.2]}. The proof shows that the shortest-path distance from $s$ to any vertex in the residual network is non-decreasing, and each edge can be critical (the bottleneck of an augmenting path) at most $O (V /2)$ times.

Theorem 2 (integrality theorem). If all capacities in a flow network are integers, then the Ford-Fulkerson method produces a maximum flow with integer values on all edges. The maximum flow value is itself an integer ^{[CLRS §26.2]}. This is because each augmentation adds an integer amount (the minimum of integer residual capacities), so integrality is preserved throughout. The integrality theorem is the reason max-flow reduces to integer optimisation problems like bipartite matching.

Theorem 3 (push-relabel: $O (V^{2} E)$ time). The push-relabel algorithm of Goldberg and Tarjan (1988) maintains a "preflow" (which may violate conservation by allowing excess at vertices) and a "height" function $h : V \to N$ with $h (s) = ∣ V ∣$ , $h (t) = 0$ . Operations: push sends flow from a vertex with excess to a neighbour of lower height; relabel increases a vertex's height when it cannot push. The algorithm runs in $O (V^{2} E)$ time using the gap heuristic, improving on Edmonds-Karp for dense graphs ^{[Tarjan 1983]}.

Synthesis. The max-flow min-cut theorem is the foundational reason duality structures appear throughout combinatorial optimisation: the equality between maximum flow and minimum cut transforms maximisation into minimisation and vice versa, with each side providing insight into the other. The central insight is that the residual network is the dual object — it encodes the "room for improvement" in the current flow, and its structure reveals the minimum cut, and putting these together with the integrality theorem gives polynomial-time solutions to a vast family of combinatorial problems. This builds toward bipartite matching in 47.04.04 and the Hungarian algorithm, and appears again in the LP duality that underlies the ellipsoid method and interior-point methods of 44.02.01.

Full proof set Master

Proposition 1 (max-flow min-cut theorem). The value of the maximum flow equals the capacity of the minimum s-t cut.

Proof. See the Key theorem section above. $□$

Proposition 2 (weak duality). For any flow $f$ and any s-t cut $(S, T)$ : $∣ f ∣ \leq c (S, T)$ .

Proof. $∣ f ∣ = \sum_{v} f (s, v) = f (S, T) - f (T, S)$ by flow conservation on internal vertices of $S$ . Since $f (T, S) \geq 0$ and $f (u, v) \leq c (u, v)$ for all $(u, v)$ : $∣ f ∣ \leq f (S, T) \leq c (S, T)$ . $□$

Proposition 3 (integrality). If all capacities are integers, Ford-Fulkerson produces an integer maximum flow.

Proof. Initially $f = 0$ (integer). Each augmentation adds $c_{f} (p) = min_{(u, v) \in p} c_{f} (u, v)$ units of flow. The residual capacities $c_{f} (u, v) = c (u, v) - f (u, v)$ are differences of integers, hence integers. So $c_{f} (p)$ is a positive integer. The augmented flow remains integer. By induction, the final flow is integer. $□$

Connections Master

40.04.01 — Graph theory provides the foundational definitions of directed graphs, paths, and cuts that flow networks are built on.
47.04.01 — Amortized analysis applies to the Edmonds-Karp algorithm, where the total work across all augmenting path searches is bounded using distance-based potential arguments.
47.04.04 — Bipartite matching reduces to max-flow; the max-flow min-cut theorem specialises to Koenig's theorem and Hall's marriage theorem.

Historical & philosophical context Master

The max-flow min-cut theorem was first proved by Lester Ford and Delbert Fulkerson in 1956 in their paper "Maximal Flow Through a Network" ^{[CLRS §26.2]}. Their proof introduced the augmenting path method and established the fundamental duality between flow and cut. Peter Elias, Amiel Feinstein, and Claude Shannon independently proved an equivalent result in the context of information theory in 1956, showing that the maximum rate of reliable communication through a network of noisy channels is determined by a minimum cut.

The Edmonds-Karp algorithm was published by Jack Edmonds and Richard Karp in 1972, showing that BFS-based augmenting path selection gives polynomial-time performance. Andrew Goldberg and Robert Tarjan introduced the push-relabel method in 1988, achieving the best known running time for general flow networks and opening the door to efficient parallel implementations.

Bibliography Master

@book{clrs2022,
  author    = {Cormen, T. H. and Leiserson, C. E. and Rivest, R. L. and Stein, C.},
  title     = {Introduction to Algorithms},
  edition   = {4th},
  publisher = {MIT Press},
  year      = {2022},
}
@article{ford1956maximal,
  author  = {Ford, L. R. and Fulkerson, D. R.},
  title   = {Maximal Flow Through a Network},
  journal = {Canadian Journal of Mathematics},
  volume  = {8},
  pages   = {399--404},
  year    = {1956},
}
@article{edmonds1972theoretical,
  author  = {Edmonds, Jack and Karp, Richard M.},
  title   = {Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems},
  journal = {Journal of the ACM},
  volume  = {19},
  number  = {2},
  pages   = {248--264},
  year    = {1972},
}
@article{goldberg1988new,
  author  = {Goldberg, Andrew V. and Tarjan, Robert E.},
  title   = {A New Approach to the Maximum-Flow Problem},
  journal = {Journal of the ACM},
  volume  = {35},
  number  = {4},
  pages   = {921--940},
  year    = {1988},
}

Prerequisites

47.04.01
40.04.01

Tier anchors

beginner: CLRS 2022 Introduction to Algorithms 4e (MIT Press) §26.1-26.2 (flow networks as pipes, maximum flow, augmenting paths)
intermediate: CLRS 2022 Introduction to Algorithms 4e (MIT Press) §26.1-26.3 (Ford-Fulkerson method, residual networks, max-flow min-cut theorem, Edmonds-Karp algorithm)
master: CLRS 2022 Introduction to Algorithms 4e (MIT Press) §26.1-26.5; Tarjan 1983 Data Structures and Network Algorithms (SIAM) (preflow-push methods, minimum-cost flow)

References

Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C. — Introduction to Algorithms (4th ed.) · MIT Press (2022). Section 26.1 defines a flow network as a tuple $G = (V, E, s, t, c)$ where $s$ is the source, $t$ is the sink, and $c : E \to R_{\geq 0}$ is the capacity function; a flow is a function $f : E \to R_{\geq 0}$ satisfying capacity constraints $0 \leq f (u, v) \leq c (u, v)$ and flow conservation $\sum_{v} f (v, u) = \sum_{v} f (u, v)$ for all $u \in / {s, t}$ . Section 26.2 presents the Ford-Fulkerson method: compute the residual network $G_{f}$ , find an augmenting path $p$ in $G_{f}$ , augment flow along $p$ by the residual capacity $c_{f} (p)$ , and iterate until no augmenting path exists; the Edmonds-Karp specialisation uses BFS for shortest augmenting paths, giving $O (V E^{2})$ time. Section 26.3 proves the max-flow min-cut theorem: the value of the maximum flow equals the capacity of the minimum cut.
Tarjan, R. E. — Data Structures and Network Algorithms · SIAM (1983). Chapter 8 develops the preflow-push method for maximum flow in $O (V^{2} E)$ time and discusses the minimum-cost flow problem; the push-relabel framework generalises Ford-Fulkerson by allowing non-conserving "preflows" that are gradually converted to valid flows.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m