Network Flow

Imagine a network of pipes carrying water from a source to a sink, each pipe with a maximum capacity. How much water can you push through end to end? This is the maximum flow problem, and its reach extends far past plumbing: routing traffic, scheduling jobs, matching applicants to jobs, even segmenting images all reduce to it. Max-flow is one of algorithm design's great modeling tools; the art, as Erickson stresses, lies in recognizing a flow problem.¹

Flow networks

Think of routing a single commodity (water, electricity, traffic, money) from a source $s$ to a sink $t$ across a network whose edges have limited throughput.

A flow is a function $f:E\to \mathbb{R}$ on the edges. The single most useful piece of bookkeeping is the net flow out of a vertex $v$, written using the boundary symbol $\partial$:

A flow is feasible when it obeys two rules:

• Non-negativity & capacity. $0\le f(u,v)\le c(u,v)$ for every edge: no edge runs backward, and none carries more than its capacity.
• Conservation. $\partial f(v)=0$ for every vertex $v\notin \left\{s,t\right\}$: nothing is created or destroyed at an interior node. (When conservation holds at every vertex, $f$ is a circulation.)

The value of an $s$–$t$ flow is the net amount leaving the source, $\left|f\right|:=\partial f(s)$. A short computation shows this is the same as the net amount arriving at the sink: summing $\partial f(v)$ over all vertices counts each edge's flow once with a $+$ and once with a $-$, so ${\sum }_{v\in V}\partial f(v)=0$; conservation kills every interior term, leaving $\partial f(s)+\partial f(t)=0$, i.e. $\left|f\right|=\partial f(s)=-\partial f(t)$. The maximum-flow problem is to find a feasible flow of greatest value.

Below is a worked network; each edge is labeled $f/c$ (flow over capacity), realizing $\left|f\right|=12$ units pushed from $s$ to $t$:

Conservation is exactly the statement that each interior node balances. Take vertex $b$: its incident flows are the outgoing $f_{bd}=5$, $f_{ba}=0$, $f_{bg}=10$ and the incoming $f_{sb}=15$, so

Checking $\partial f(v)=0$ at every interior vertex this way is how you verify a flow is feasible.

Augmenting paths and the residual graph

How do we increase a flow? Find a path from $s$ to $t$ that still has spare room and push more along it. The bookkeeping device that makes this precise, and makes the algorithm correct, is the residual graph.

Concretely, each original edge $(u,v)$ splits into three cases on its residual capacity $c^f$:

• If $f_{uv}=0$ (empty), put $(u,v)\in E_f$ with $c_{uv}^f=c_{uv}$.
• If $0<f_{uv}<c_{uv}$ (partly used), put both: $(u,v)$ with $c_{uv}^f=c_{uv}-f_{uv}$, and $(v,u)$ with $c_{vu}^f=f_{uv}$.
• If $f_{uv}=c_{uv}$ (saturated), put only the reverse $(v,u)$ with $c_{vu}^f=f_{uv}$.

(We assume $G$ has no anti-parallel edges, at most one of $(u,v)$, $(v,u)$ is in $E$, so these reverse edges are unambiguous. Any graph can be preprocessed to satisfy this by splitting an edge through a dummy vertex.)

The backward edges are the subtle part that matters: pushing flow along $(v,u)$cancels existing flow on $(u,v)$, letting the algorithm undo earlier, suboptimal decisions. That is exactly why a greedy fill paths until stuck approach can get stuck below optimum, while augmenting paths cannot. Below, the feasible flow from above (top) and the residual graph $G_f$ it induces (below); each residual edge is labeled with its capacity $c_e^f$:

A single augmentation is easy to picture on a small network. Each edge below is labeled $f/c$; the highlighted residual path $s\to a\to b\to t$ has residual capacities $⟨1,2,3⟩$, so its bottleneck is $1$. Pushing one unit along it saturates $s\to a$ and lifts the flow value from $5$ to $6$, with every interior vertex still balanced:

The augmentation lemma

Before trusting the algorithm we must prove that augmenting actually produces a better feasible flow. Augmenting $f$ along a path $P$ by amount $k$ produces a new function $f^{\prime }$ defined edge-by-edge:

The proof is four short claims, each just unfolding the definitions:

• Non-negativity ($f_{uv}^{\prime }\ge 0$). The only danger is a decrease, $f_{uv}^{\prime }=f_{uv}-k$, which happens when the reverse $(v,u)$ lies on $P$. But then $(v,u)\in E_f$ forces $c_{vu}^f=f_{uv}$, and $k\le c_{vu}^f=f_{uv}$, so $f_{uv}^{\prime }=f_{uv}-k\ge 0$.
• Capacity ($f_{uv}^{\prime }\le c_{uv}$). The only danger is an increase, $f_{uv}^{\prime }=f_{uv}+k$, which happens when $(u,v)$ lies on $P$. Then $(u,v)\in E_f$ forces $c_{uv}^f=c_{uv}-f_{uv}$, and $k\le c_{uv}^f$, so $f_{uv}^{\prime }=f_{uv}+k\le f_{uv}+(c_{uv}-f_{uv})=c_{uv}$.
• Conservation ($\partial f^{\prime }(v)=0$ for $v\notin \left\{s,t\right\}$). If $v\notin P$, none of its incident terms change. If $v$ is an interior vertex of $P$, the path enters $v$ once and leaves once; that pair of edges shifts the in- and out-flow by the same $k$ (with matching signs whether the path step is a forward or reverse edge), so $\partial f^{\prime }(v)=\partial f(v)=0$.
• Value ($\left|f^{\prime }\right|=\left|f\right|+k$). $P$ uses exactly one edge out of $s$ and none into $s$. That single edge gains $k$ (forward) or loses $-k$ across a reverse step, so $\partial f^{\prime }(s)=\partial f(s)+k$, i.e. $\left|f^{\prime }\right|=\left|f\right|+k$.

So every augmentation strictly increases the value while keeping $f$ legal. The converse, which the min-cut proof will need, also holds: if $f$ is not maximum, $G_f$ must contain an augmenting path. Putting the two together gives the equivalence at the center of the theory

Ford-Fulkerson and Edmonds-Karp

The $\text{Ford-Fulkerson}$ method is then irresistibly simple: while an augmenting path exists, push flow along it.²

Correctness is immediate from the augmentation lemma: each iteration produces a feasible flow of strictly larger value, and the method halts exactly when no augmenting path remains, which (by the equivalence above, proved in full below) is precisely the condition for a maximum flow.

Running time rests on an invariant: if every capacity is an integer, $c:E\to \mathbb{N}$, then all residual capacities $c_e^f$ and flow values $f_{uv}$ stay integers throughout. Each augmentation then raises $\left|f\right|$ by at least $1$, so there are at most $\left|f^{\ast }\right|$ iterations, each costing $O(m)$ to find a path and push along it (here $m=\left|E\right|$, $n=\left|V\right|$):

If additionally every capacity lies in $[1,C]$, then $\left|f^{\ast }\right|\le {\sum }_e{c}_e\le Cm$, giving $T(m,n,C)=O(m^{2}C)$. This is pseudo-polynomial: fine for small capacities, but it can genuinely crawl when they are huge. The classic bad case has a middle edge of capacity $1$ between two paths of capacity $1000$; a naïve solver alternately pushes one unit forward and one unit back, taking $\Omega (C)$ augmentations. (On irrational capacities the method may not even terminate.)

The fix, due to $\text{Edmonds-Karp}$, is to always pick the shortest augmenting path (fewest edges): find it with BFS in the residual graph. The key lemma is that each edge $e$ disappears from $G_f$ at most $\frac{n}{2}$ times; since each iteration causes at least one disappearance, the number of iterations is $O(m)\cdot \frac{n}{2}=O(mn)$. With $O(m)$ per BFS this gives a strongly polynomial $O(m^{2}n)$ bound, independent of capacities. (Orlin's 2012 algorithm improves this to $O(mn)$; you may cite it as a black-box max-flow subroutine.)

The max-flow min-cut theorem

When does Ford-Fulkerson stop, and why is the result optimal? The answer is one of the most elegant theorems in algorithms, linking flow to cuts.³

The dual view is a minimum-cut problem: an adversary wants to cut a cheap set of edges so that no $s$–$t$ flow can get through. The two problems turn out to be the same problem.

The proof has two directions.

Easy direction (weak duality): every feasible flow $f$ and every $s$–$t$ cut $(S,T)$ satisfy $\left|f\right|\le c(S,T)$. We compute $\left|f\right|$ by summing $\partial f$ over all of $S$, where conservation makes the interior terms vanish, leaving only $\partial f(s)$:

So $\max \left|f\right|\le \min c(S,T)$; flow is bounded by the narrowest cut.

Hard direction: there exist a flow $f^{\ast }$ and an $s$–$t$ cut $(S^{\ast },T^{\ast })$ with $\left|f^{\ast }\right|=c(S^{\ast },T^{\ast })$. Take $f^{\ast }$ to be a maximum flow. If $G_{f^{\ast }}$ had an augmenting path, the augmentation lemma would yield a larger flow, a contradiction. Therefore $t$ is not reachable from $s$ in $G_{f^{\ast }}$. Define the reachable set and its complement:

Then $s\in S^{\ast }$ and $t\in T^{\ast }$, so $(S^{\ast },T^{\ast })$ is a genuine $s$–$t$ cut. Now the two boundary observations:

• Forward edges are saturated. Every $(u,v)\in E$ with $u\in S^{\ast }$, $v\in T^{\ast }$ has $f_{uv}^{\ast }=c_{uv}$; otherwise it would contribute a forward residual edge, making $v$ reachable from $s$, so $v\in S^{\ast }$, a contradiction.
• Backward edges are empty. Every $(v,u)\in E$ with $v\in T^{\ast }$, $u\in S^{\ast }$ has $f_{vu}^{\ast }=0$; otherwise it would contribute a reverse residual edge $(u,v)\in G_{f^{\ast }}$, again making $v$ reachable.

These are exactly the two inequalities that were slack in the easy direction. With forward edges saturated ($f=c$) and backward edges unused ($f=0$), both $\le$ steps become equalities, so $\left|f^{\ast }\right|=c(S^{\ast },T^{\ast })$. Combined with weak duality, $f^{\ast }$ is a maximum flow and $(S^{\ast },T^{\ast })$ is a minimum cut. $■$

Because the hard direction shows the converse of the augmentation lemma, we get the promised three-way equivalence — all three statements are the same fact:

This is also why $\text{Ford-Fulkerson}$ is correct: it halts exactly when $G_f$ has no $s$–$t$ path, which is precisely when $f$ is maximum.

Application: bipartite matching

The payoff of the flow abstraction is that other problems melt into it.⁴ A useful rule of thumb: whenever a graph problem looks for paths or cycles under some per-edge or per-vertex budget constraint, reach for max-flow as a subroutine, and many non-graph problems (task assignment, base-station connection, workshop scheduling) yield to it too once you find the right network.

Consider bipartite matching: a set $L$ of applicants, a set $R$ of jobs, and an edge for each applicant qualified for a job (edge ${\ell }_i\to r_j$ iff $A[i][j]=\text{true}$). A matching pairs applicants to jobs with no one used twice; we want a maximum matching.

Build a flow network: add a source $s$ with a unit-capacity edge to every applicant, add a sink $t$ with a unit-capacity edge from every job, and orient each qualification edge from $L$ to $R$ with capacity $1$.

The reduction works because of an exact correspondence in both directions: if $k$ tasks can be assigned, those $k$ disjoint $s\to \ell \to r\to t$ routes form a flow of value $k$ (easy); conversely, if the max-flow value is $k$, then $k$ tasks can be assigned (less obvious, since it needs integrality).

Here every capacity is $1$, so the maximum flow is $0$/$1$ on every edge. Its path-flow decomposition is a set of vertex-disjoint $s\to \ell \to r\to t$ routes; reading off the middle $\ell \to r$ edge of each gives a matching, and the value of the max flow equals the size of the maximum matching. So one run of $\text{Edmonds-Karp}$ solves bipartite matching.

For the network above, the integral max flow saturates three vertex-disjoint routes, shown in blue: ${\ell }_1\to r_1$, ${\ell }_2\to r_2$, ${\ell }_3\to r_3$. The flow value is $3$, so the maximum matching has size $3$ — every applicant is placed:

This is the template for countless reductions (assignment, base-station connection, workshop scheduling, vertex-disjoint paths), all of which become build a network, compute max flow, read off an integral solution.

Takeaways

• A flow network routes flow from $s$ to $t$ under capacity and conservation ($\partial f(v)=0$) constraints; the value $\left|f\right|=\partial f(s)=-\partial f(t)$ is what we maximize.
• The residual graph $G_f$ adds reverse edges (capacity $f_{uv}$) that let us undo flow; the augmentation lemma proves pushing $k$ along any $s$–$t$ path of $G_f$ yields a feasible flow of value $\left|f\right|+k$.
• $\text{Ford-Fulkerson}$ augments until $G_f$ has no $s$–$t$ path; with integer capacities it runs in $O(m\left|f^{\ast }\right|)=O(m^{2}C)$ (pseudo-polynomial), and $\text{Edmonds-Karp}$'s BFS choice makes it $O(m^{2}n)$, capacity-independent.
• The max-flow min-cut theorem (max flow $=$ min cut) gives a three-way equivalence: $f$ is maximum $\leftrightarrow$ $G_f$ has no augmenting path $\leftrightarrow$$\left|f\right|=c(S,T)$ for some cut. The hard direction builds the cut from the set reachable from $s$ in $G_{f^{\ast }}$.
• By the integrality theorem, an all-integer network has an integral max flow that decomposes into path flows; bipartite matching is the canonical unit-capacity instance, the gateway to flow's vast catalog of applications.