Flow Networks and the Maximum-Flow Problem

A flow network models the movement of a commodity (oil, water, data) through a network with capacity constraints. The problem is to maximise throughput from source to sink.

Definitions

A flow network is a directed graph $G = (V, E)$ with two distinguished vertices:

• Source $s \in V$: origin of flow, no incoming flow
• Sink $t \in V$: destination of flow, no outgoing flow

Each edge $(u, v) \in E$ has a non-negative capacity $c(u, v) \ge 0$. We assume no self-loops and (for convenience) no antiparallel edges: if $(u, v) \in E$ then $(v, u) \notin E$. Antiparallel edges can be removed by inserting a dummy vertex. Every vertex lies on some path $s \leadsto v \leadsto t$.

Flow

A flow $f: V \times V \to \mathbb{R}$ satisfies:

1. Capacity constraint: $0 \le f(u, v) \le c(u, v)$ for all $u, v \in V$
2. Flow conservation: for every vertex $u \in V \setminus \{s, t\}$:

$\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)$

Total flow in equals total flow out at every internal vertex. We define $f(u, v) = 0$ if $(u, v) \notin E$.

The value of flow $f$ is the net flow leaving the source:

$|f| = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s)$

The second sum is usually zero but is included for generality.

Antisymmetry Convention

For notational convenience, define $f(v, u) = -f(u, v)$. This lets us write net flow across a cut as a single sum. In practice, flow only exists in forward directions up to capacity; the antisymmetry notion simplifies the algebra of residual networks.

Residual Networks

Given flow $f$ on $G$, the residual network $G_f = (V, E_f)$ shows how much additional flow can be pushed on each edge, and where flow can be cancelled:

• If $(u, v) \in E$ and $f(u, v) < c(u, v)$, add $(u, v)$ to $E_f$ with residual capacity $c_f(u, v) = c(u, v) - f(u, v)$
• If $f(u, v) > 0$ (i.e. $(v, u) \in E$ with positive flow), add $(v, u)$ to $E_f$ with $c_f(v, u) = f(u, v)$

Residual edges in the reverse direction represent flow cancellation: we can “undo” flow previously sent along the forward edge.

Formally:

$c_f(u, v) = \begin{cases} c(u, v) - f(u, v) & \text{if } (u, v) \in E \\ f(v, u) & \text{if } (v, u) \in E \\ 0 & \text{otherwise} \end{cases}$

Augmentation

If $f'$ is a flow in $G_f$, then the augmented flow $f \uparrow f'$ is:

$(f \uparrow f')(u, v) = f(u, v) + f'(u, v) - f'(v, u)$

This yields a valid flow in $G$ with value $|f \uparrow f'| = |f| + |f'|$.

Problem Statement

Maximum-Flow Problem: given a flow network $G = (V, E)$ with capacities $c$, source $s$, and sink $t$, find a flow $f$ of maximum value $|f|$.

Applications

• Transport and logistics networks
• Bipartite matching (see Maximum Bipartite Matching via Flow)
• Circulation with demands
• Image segmentation (min-cut formulation)
• Edge-disjoint and vertex-disjoint paths
• Project selection / maximum closure
• Baseball elimination

Antiparallel Edge Elimination

If $(u, v)$ and $(v, u)$ both exist with capacities $a$ and $b$, insert a new vertex $x$ and replace $(v, u)$ with $(v, x)$ and $(x, u)$, both of capacity $b$. The resulting network has no antiparallel edges and preserves all feasible flows.

Example

Consider a simple 4-vertex network:

• $s \to a$ (capacity 10), $s \to b$ (capacity 5)
• $a \to b$ (capacity 3), $a \to t$ (capacity 8)
• $b \to t$ (capacity 7)

A feasible flow sends 8 via $s \to a \to t$ and 7 via $s \to b \to t$, but the $a \to b$ edge capacity of 3 constrains redistribution. The maximum flow value is 15 (send 10 on $s \to a$, split 8 to $t$ and 2 via $b$, plus 5 from $s \to b$, total $8 + 2 + 5 = 15$).

Summary

Concept	Definition
Flow network	$G = (V, E)$ with source $s$, sink $t$, capacities $c(u, v) \ge 0$
Capacity constraint	$0 \le f(u, v) \le c(u, v)$
Flow conservation	$\sum_v f(v, u) = \sum_v f(u, v)$ for $u \neq s, t$
Flow value $\lvert f \rvert$	Net flow out of $s$: $\sum_v f(s, v) - \sum_v f(v, s)$
Residual capacity	$c_f(u, v) = c(u, v) - f(u, v) + f(v, u)$
Augmentation	$f \uparrow f'$ adds residual flow $f'$ to $f$

Past Tripos: y2024p1q9, y2023p2q7.