Chapter 26: Maximum Flow

A directed graph can be interpreted as a flow network to answer questions about material flows — liquids through pipes, parts through assembly lines, current through electrical networks, or information through communication networks. The maximum-flow problem asks: what is the greatest rate at which material can be shipped from a source to a sink without violating capacity constraints?

This chapter presents two general approaches:

1. The Ford-Fulkerson method (augmenting paths)
2. The push-relabel method (local operations)

---

Flow Networks

Flow Networks and Flows

A flow network G = (V, E) is a directed graph where:

• Each edge (u, v) ∈ E has a nonnegative capacity c(u, v) ≥ 0
• If (u, v) ∈ E, then (v, u) ∉ E (no reverse edges; antiparallel edges handled separately)
• If (u, v) ∉ E, then c(u, v) = 0 by convention
• No self-loops are allowed
• Two distinguished vertices: source s and sink t
• Every vertex lies on some path from s to t, so the graph is connected and |E| ≥ |V| − 1

A flow in G is a function f : V × V → ℝ satisfying:

1. Capacity constraint: For all u, v ∈ V:

   • 0 ≤ f(u, v) ≤ c(u, v)

2. Flow conservation: For all u ∈ V − {s, t}:

   • Σ f(v, u) = Σ f(u, v) (flow in = flow out)

The value of a flow f is:

|f| = Σ f(s, v) − Σ f(v, s)

(total flow out of the source minus flow into the source)

The maximum-flow problem: given G with source s and sink t, find a flow of maximum value.

Modeling Problems with Antiparallel Edges

If a problem naturally has both edges (v₁, v₂) and (v₂, v₁) (antiparallel edges), transform the network:

• Choose one edge, say (v₁, v₂)
• Add a new vertex v'
• Replace (v₁, v₂) with (v₁, v') and (v', v₂), both with the original capacity

The resulting network has no antiparallel edges and is equivalent to the original.

Networks with Multiple Sources and Sinks

A problem with multiple sources {s₁, …, sₘ} and sinks {t₁, …, tₙ} reduces to ordinary max-flow:

• Add a supersource s with edges (s, sᵢ) of capacity ∞ for each source sᵢ
• Add a supersink t with edges (tⱼ, t) of capacity ∞ for each sink tⱼ

Any flow in the multi-source/sink network corresponds to a flow of identical value in the single-source/sink network, and vice versa.

---

The Ford-Fulkerson Method

The Ford-Fulkerson method iteratively increases the flow value by finding augmenting paths in the residual network. It is a "method" rather than an "algorithm" because it encompasses several implementations with differing running times.

FORD-FULKERSON-METHOD(G, s, t)
1  initialize flow f to 0
2  while there exists an augmenting path p in the residual network Gf
3      augment flow f along p
4  return f

Three key ideas: residual networks, augmenting paths, and cuts.

Residual Networks

Given flow network G and flow f, the residual network Gf represents how we can change the flow on edges of G.

The residual capacity cf(u, v) is defined as:

• c(u, v) − f(u, v) if (u, v) ∈ E (can send more flow forward)
• f(v, u) if (v, u) ∈ E (can cancel existing flow)
• 0 otherwise

The residual network Gf = (V, Ef) where:

• Ef = {(u, v) ∈ V × V : cf(u, v) > 0}
• |Ef| ≤ 2|E|

Reverse edges in the residual network allow an algorithm to "send back" flow it has already sent — equivalent to decreasing flow on an edge. This cancellation is crucial for correctness.

Augmentation of flow f by flow f' (where f' is a flow in Gf):

(f ↑ f')(u, v) = f(u, v) + f'(u, v) − f'(v, u) if (u, v) ∈ E

Lemma 26.1: f ↑ f' is a flow in G with value |f ↑ f'| = |f| + |f'|.

Augmenting Paths

An augmenting path p is a simple path from s to t in the residual network Gf.

The residual capacity of path p:

cf(p) = min{cf(u, v) : (u, v) is on p}

Lemma 26.2: The flow fp defined by sending cf(p) units along each edge of p is a valid flow in Gf with value |fp| = cf(p) > 0.

Corollary 26.3: Augmenting f by fp yields a flow f ↑ fp with value |f ↑ fp| = |f| + |fp| > |f|. Each augmentation strictly increases the flow value.

Cuts of Flow Networks

A cut (S, T) of flow network G is a partition of V into S and T = V − S such that s ∈ S and t ∈ T.

Net flow across cut (S, T):

f(S, T) = Σ(u∈S, v∈T) f(u, v) − Σ(u∈S, v∈T) f(v, u)

Capacity of cut (S, T):

c(S, T) = Σ(u∈S, v∈T) c(u, v)

Note the asymmetry: capacity counts only edges from S to T; net flow subtracts reverse flow.

A minimum cut is a cut whose capacity is minimum over all cuts.

Lemma 26.4: For any flow f and any cut (S, T): f(S, T) = |f|. The net flow across every cut equals the flow value.

Corollary 26.5: The value of any flow is bounded above by the capacity of any cut: |f| ≤ c(S, T).

Max-Flow Min-Cut Theorem

Theorem 26.6 (Max-Flow Min-Cut Theorem): The following are equivalent:

1. f is a maximum flow in G
2. The residual network Gf contains no augmenting paths
3. |f| = c(S, T) for some cut (S, T) of G

This means: the value of a maximum flow equals the capacity of a minimum cut.

Proof sketch:

• (1) ⇒ (2): If an augmenting path existed, we could increase the flow, contradicting maximality
• (2) ⇒ (3): Define S = {v : reachable from s in Gf}. Since t ∉ S, (S, T) is a cut. All forward edges are saturated, all backward edges carry zero flow, so |f| = c(S, T)
• (3) ⇒ (1): Since |f| ≤ c(S, T) for all cuts, equality implies f is maximum

The Basic Ford-Fulkerson Algorithm

FORD-FULKERSON(G, s, t)
1  for each edge (u, v) ∈ G.E
2      (u, v).f = 0
3  while there exists a path p from s to t in the residual network Gf
4      cf(p) = min{cf(u, v) : (u, v) is in p}
5      for each edge (u, v) in p
6          if (u, v) ∈ E
7              (u, v).f = (u, v).f + cf(p)
8          else (v, u).f = (v, u).f − cf(p)

• Lines 1–2: Initialize all flows to 0
• Lines 3–8: Repeatedly find augmenting paths and push flow along them
• Line 7: Increase flow on forward edges
• Line 8: Decrease flow on reverse edges (cancellation)

Analysis of Ford-Fulkerson

• With integer capacities and arbitrary path selection: O(E |f|)* where f* is the maximum flow
  • Each iteration takes O(E) time
  • Flow increases by at least 1 per iteration
  • Can be very slow if |f*| is large (e.g., 2,000,000 iterations on a simple 4-vertex graph)
• May not terminate with irrational capacities

The Edmonds-Karp Algorithm

The Edmonds-Karp algorithm uses BFS to find the shortest augmenting path (fewest edges).

Lemma 26.7: Shortest-path distances δf(s, v) in the residual network increase monotonically with each augmentation.

Theorem 26.8: The total number of augmentations is O(VE).

Proof idea:

• An edge (u, v) is critical on path p if cf(p) = cf(u, v)
• After augmentation, a critical edge disappears from the residual network
• Between two times an edge becomes critical, the distance of u from s increases by at least 2
• Each edge can become critical at most |V|/2 times
• Total critical edges (and thus augmentations): O(VE)

Running time: O(VE²) — each of O(VE) augmentations takes O(E) time.

---

Maximum Bipartite Matching

The Maximum-Bipartite-Matching Problem

Given an undirected graph G = (V, E):

• A matching M ⊆ E is a set of edges where each vertex has at most one incident edge from M
• A vertex is matched if some edge in M is incident on it; otherwise unmatched
• A maximum matching has maximum cardinality

For bipartite graphs: V = L ∪ R (disjoint), all edges go between L and R.

Application: matching machines (L) to tasks (R) — maximize the number of simultaneously working machines.

Finding a Maximum Bipartite Matching

Construct a corresponding flow network G' = (V', E'):

• V' = V ∪ {s, t}
• E' = {(s, u) : u ∈ L} ∪ {(u, v) : (u, v) ∈ E, directed L → R} ∪ {(v, t) : v ∈ R}
• All edges have unit capacity

Lemma 26.9: A matching M in G of size |M| corresponds to an integer-valued flow f in G' with |f| = |M|, and vice versa.

Theorem 26.10 (Integrality Theorem): If all capacities are integers, the Ford-Fulkerson method produces a maximum flow where all flow values f(u, v) are integers.

Corollary 26.11: The cardinality of a maximum matching equals the value of a maximum flow in G'.

Running time: O(VE)

• Maximum flow value is at most min(|L|, |R|) = O(V)
• Each augmentation takes O(E) time
• Total: O(V · E) = O(VE)

---

Push-Relabel Algorithms

Push-relabel algorithms work locally — one vertex at a time — rather than finding global augmenting paths. They achieve O(V²E) time, improving on Edmonds-Karp's O(VE²).

Preflows and Excess

A preflow f satisfies the capacity constraint but relaxes flow conservation:

Σ f(v, u) − Σ f(u, v) ≥ 0 for all u ∈ V − {s}

The excess flow at vertex u:

e(u) = Σ f(v, u) − Σ f(u, v)

A vertex u ∈ V − {s, t} is overflowing if e(u) > 0.

Height Functions

A height function h : V → ℕ satisfies:

• h(s) = |V|
• h(t) = 0
• h(u) ≤ h(v) + 1 for every residual edge (u, v) ∈ Ef

Lemma 26.12: If h(u) > h(v) + 1, then (u, v) is not a residual edge.

Lemma 26.17: There is no path from s to t in the residual network Gf (key to correctness).

Intuition

Think of vertices on platforms at different heights:

• Flow is pushed only downhill (from higher to lower vertices)
• Source is fixed at height |V|, sink at height 0
• Initially, saturate all edges leaving the source
• Excess collects at intermediate vertices
• Relabel a vertex (raise its height) when all outgoing residual edges go to same-height or higher vertices
• Eventually, excess that can't reach the sink flows back to the source

The Push Operation

PUSH(u, v)
// Applies when: u is overflowing, cf(u, v) > 0, and u.h = v.h + 1
// Action: Push Δf(u, v) = min(u.e, cf(u, v)) units from u to v
1  Δf(u, v) = min(u.e, cf(u, v))
2  if (u, v) ∈ E
3      (u, v).f = (u, v).f + Δf(u, v)
4  else (v, u).f = (v, u).f − Δf(u, v)
5  u.e = u.e − Δf(u, v)
6  v.e = v.e + Δf(u, v)

• A saturating push makes cf(u, v) = 0 afterward (edge disappears from residual network)
• A nonsaturating push makes u.e = 0 afterward (vertex is no longer overflowing) — Lemma 26.13

The Relabel Operation

RELABEL(u)
// Applies when: u is overflowing and u.h ≤ v.h for all (u, v) ∈ Ef
// Action: Increase the height of u
1  u.h = 1 + min{v.h : (u, v) ∈ Ef}

Sets u's height to one more than its lowest neighbor in the residual network, ensuring at least one admissible (downhill) edge exists afterward.

The Generic Push-Relabel Algorithm

INITIALIZE-PREFLOW(G, s)
1  for each vertex v ∈ G.V
2      v.h = 0
3      v.e = 0
4  for each edge (u, v) ∈ G.E
5      (u, v).f = 0
6  s.h = |G.V|
7  for each vertex v ∈ s.Adj
8      (s, v).f = c(s, v)
9      v.e = c(s, v)
10     s.e = s.e − c(s, v)

GENERIC-PUSH-RELABEL(G)
1  INITIALIZE-PREFLOW(G, s)
2  while there exists an applicable push or relabel operation
3      select an applicable push or relabel operation and perform it

Lemma 26.14: If u is overflowing, then either a push or relabel operation applies to it.

Correctness

Theorem 26.18: When GENERIC-PUSH-RELABEL terminates, the preflow f is a maximum flow.

Proof:

• At termination, no vertex in V − {s, t} has excess (otherwise an operation would apply)
• So the preflow is actually a valid flow
• The height function is maintained throughout (Lemma 26.16)
• No s-t path exists in the residual network (Lemma 26.17)
• By the max-flow min-cut theorem, f is a maximum flow

Analysis

Lemma 26.19: For any overflowing vertex x, there is a simple path from x to s in Gf.

Lemma 26.20: Vertex heights never exceed 2|V| − 1.

Corollary 26.21 (Relabel bound): At most 2|V| − 1 relabels per vertex, < 2|V|² total.

Lemma 26.22 (Saturating push bound): Fewer than 2|V||E| saturating pushes.

Lemma 26.23 (Nonsaturating push bound): Fewer than 4|V|²(|V| + |E|) nonsaturating pushes.

Proof uses potential function Φ = Σ(overflowing v) v.h:

• Each relabel increases Φ by < 2|V|
• Each saturating push increases Φ by < 2|V|
• Each nonsaturating push decreases Φ by ≥ 1
• Total increase bounded by 4|V|²(|V| + |E|)

Theorem 26.24: Total basic operations: O(V²E).

Corollary 26.25: The generic push-relabel algorithm can be implemented in O(V²E) time.

---

The Relabel-to-Front Algorithm

A specific push-relabel implementation that runs in O(V³) time — asymptotically at least as good as O(V²E), and better for dense networks.

Admissible Edges and Networks

An edge (u, v) is admissible if:

• cf(u, v) > 0 (residual capacity exists), AND
• h(u) = h(v) + 1 (height difference is exactly 1)

The admissible network Gf,h = (V, Ef,h) consists of all admissible edges.

Lemma 26.26: The admissible network is a DAG (directed acyclic graph).

Lemma 26.27: Pushing flow does not create new admissible edges (but may remove the pushed edge if saturating).

Lemma 26.28: After relabeling u, there is at least one admissible edge leaving u, but no admissible edges entering u.

Neighbor Lists

For each vertex u, maintain a neighbor list u.N containing all vertices v where (u, v) ∈ E or (v, u) ∈ E. A pointer u.current tracks the current position in the list.

Discharging an Overflowing Vertex

DISCHARGE(u)
1  while u.e > 0
2      v = u.current
3      if v == NIL
4          RELABEL(u)
5          u.current = u.N.head
6      elseif cf(u, v) > 0 and u.h == v.h + 1
7          PUSH(u, v)
8      else u.current = v.next-neighbor

Each iteration does exactly one of three things:

1. v is NIL (end of list): relabel u and reset pointer to head
2. (u, v) is admissible: push flow from u to v
3. (u, v) is inadmissible: advance pointer to next neighbor

The last action before DISCHARGE returns is always a push (since only a push reduces excess).

The Relabel-to-Front Algorithm

RELABEL-TO-FRONT(G, s, t)
1  INITIALIZE-PREFLOW(G, s)
2  L = G.V − {s, t}, in any order
3  for each vertex u ∈ G.V − {s, t}
4      u.current = u.N.head
5  u = L.head
6  while u ≠ NIL
7      old-height = u.h
8      DISCHARGE(u)
9      if u.h > old-height
10         move u to the front of list L
11     u = u.next

Key invariant (loop invariant for line 6):

• List L is a topological sort of the admissible network
• No vertex before u in L has excess flow

When a vertex is relabeled, it moves to the front of L (hence the name), ensuring the topological sort is maintained since relabeling creates admissible edges only leaving the relabeled vertex.

Termination: When the scan reaches the end of L, no vertex has excess, so the preflow is a maximum flow.

Analysis

Theorem 26.30: RELABEL-TO-FRONT runs in O(V³) time.

Proof breakdown:

• A phase = time between two consecutive relabels
• O(V²) phases total (from the relabel bound)
• Each phase has at most |V| calls to DISCHARGE
• Total DISCHARGE calls: O(V³)

Work within DISCHARGE:

• Relabels: O(VE) total time
• Pointer advances: O(V · degree(u)) per vertex over all relabels → O(VE) total by handshaking lemma
• Saturating pushes: O(VE) total
• Nonsaturating pushes: at most one per DISCHARGE call → O(V³) total

Total: O(V³ + VE) = O(V³)

---

Summary of Running Times

Key Theorems at a Glance

• Max-Flow Min-Cut Theorem: max flow value = min cut capacity
• Integrality Theorem: integer capacities ⇒ integer maximum flow exists
• Flow Decomposition: any flow can be decomposed into at most |E| augmenting paths and cycles
• Matching in bipartite graph ↔ integer flow in corresponding network