Network Flow

Introduction

Many optimization problems reduce to routing as much "stuff" as possible through a network subject to capacity limits, such as traffic through roads, data through pipes, and goods through supply chains. Network flow formalizes this and gives efficient algorithms with broad applications (e.g. bipartite matching).

The central problem: given a directed graph with edge capacities, a source and sink node, find the maximum amount of flow that can be routed from source to sink without violating any capacity or conservation constraints.

Definitions

Flow Network. A flow network is a directed graph $G = (V, E)$ where each edge $e \in E$ has capacity $c_e \ge 0$, a source node $s \in V$ and sink node $t \in V$. We assume no edge enters $s$ and no edge leaves $t$.

Flow. A flow is a function $f: E \rightarrow \mathbb{R}_{\ge 0}$ satisfiying the following two conditions:

• Capacity constraint. For every edge $e \in E$: $f(e) \le c_e$.
• Conservation constraint. For every node $v \in V \setminus \{s, t\}$:

$$\begin{align*} \sum_{e \text{ into } v} f(e) = \sum_{e \text{ out of } v} f(e) \end{align*}$$

That is, the flow in equals flow out at every internal node.

Value of a flow. The value of a flow is the total flow leaving the source:

$$\begin{align*} \text{value}(f)= \sum_{e \text{ out of } s} f(e) \end{align*}$$

Maximum flow problem. Given a flow network $(G, c, s, t)$, find a flow $f$ maximizing $|f|$.

Residual graph. Given a flow $f$, the residual graph $G_f = (V, E_f)$ captures remaining capacity. For each edge $(u, v) \in E$.

• Add a forward edge $(u, v)$ with residual capacity $c_e - f_e$ if $e = (v, w)$ and $f_e < c_e$.
• Add a backwards edge $(v, u)$ with residual capacity $f_e$ if if $e = (v, w)$ and $f_e > 0$.

These backward edges allow us to "cancel" or undo any previously routed flow.

Augmenting path. An augmenting path is any path from $s$ to $t$ in the residual graph $G_f$. We say the bottleneck capacity of path $P$ is:

$$\begin{align*} \text{bottleneck}(P) = \min( \min_{\text{forward } e \in P} (c_e - f_e), \min_{\text{backward } e \in P} f_e). \end{align*}$$

In other words, it is the maximum flow we can add/subtract onto any foward/backward edge along $P$ without violating any capacity constraints (without exceed $c_e$ or going below 0).

Ford-Fulkerson

Ford-Fulkerson repeatedly finds an augmenting path in the residual graph $G_f$ and pushes flow along it equal to its bottleneck capacity, until no augmenting path remains. After finding an augmenting path $P$ with flow $f$ and bottleneck $b$, we use the following augment operation.

• For each forward edge $e \in P$: set $f(e) \leftarrow f(e) + b$.
• For each backward edge $e \in P$ (reversing an original edge $e' \in E$): set $f(e') \leftarrow f(e') - b$.

Algorithm

Ford-Fulkerson(G, s, t, c):
    f(e) = 0 for all edges
    build residual graph G_f
    while there is an s-t path P in G_f:
        b = bottleneck(P)
        f = augment(f, P, b)
        update G_f
    return flow f

Lemma: Augmenting preserves capacity and conservation constraints.

Let $f$ be a valid flow, $P$ be a simple $s-t$ path in $G_f$ and $b = \text{bottleneck}(P) > 0$. Let $f'$ be the flow after augmenting $f$ with path $P$.

Recall that the augment performs the following operation to forward/backward edges:

• Forward edge $(u, v)$ with $e = (u, v) \in E$ with $f_e < c_e$; we set $f'(e) = f(e) + b$.
• Backward edge $(u, v)$ with $e = (v, e) \in E$ with $f_e > 0$; we set $f'(e) = f(e) - b$.

For our bottleneck $b > 0$,

• $b \le c_e - f_e$ for every forward edge $e$.
• $b \le f_e$ for every backward edge $e$.

We show the capacity constraint, i.e. $0 \le f'(e) \le c_e$ for every $e \in E$.

Case 1: $e \notin P$. This means that the edge $e$ was not augmented, so $f'(e) = f(e)$. Because $f$ is a valid flow, we have $0 \le f(e) = f'(e) \le c_e$ as required.

Case 2: $e \in P$, $e$ is used as a forward edge. Then, $f'(e) = f(e) + b$. We have:

$$\begin{align*} f'(e) &= f(e) + b \ge 0 + 0 > 0 \\ f'(e) &= f(e) + b \le f(e) + (c_e - f(e)) = c_e \end{align*}$$

where the upperbound uses $b \le c_e - f(e)$.

Case 3: $e \in P$, $e$ is used as a backward edge. Then, $f'(e) = f(e) - b$.

$$\begin{align*} f'(e) &= f(e) - b \ge f(e) - f(e) = 0 \\ f'(e) &= f(e) - b \le f(e) \le c_e \end{align*}$$

The lower bound uses $b \le f(e)$, and the upper bound uses $b > 0$.

In all cases $0 \le f'(e) \le c_e$, so $f'$ satisfies the capacity constraint.

Next, we show that the conservation constraint is satisfied.

We fix an internal node $v \in V \setminus \{s, t\}$. Since $f$ satisfies conservation at $v$, it is enough to show the augmentation changes the total inflow and outflow at $v$ by the same amount. We denote these changes as $\delta_{in}(v)$ and $\delta_{out}(v)$.

If $v \notin P$, no incident edge to $v$ is modified, so $\delta_{in}(v) = \delta_{out}(v) = 0$ and conservation is preserved.

Otherwise, $v$ is an interval vertex of our path $P$, so there is exactly one incoming edge $(u, v)$ and one outgoing edge $(v, w)$ in $G_f$. Each contributes $\pm b$ to the flow on its underlying original edge.

Consider the case where $(u, v)$ is a forward edge and $(v, w)$ is a backward edge.

• Since $(u, v)$ is a forward edge, we contribute $+ b$ to $\delta_{in}(v)$.
• Since $(v, w)$ is a backward edge (original edge is $(w, v)$), we contribute $- b$ to $\delta_{in}(v)$.

In total, we contribute $b + (- b) = 0$ to $\delta_{in}(v)$ and leave $\delta_{out}(v)$ unchanged. In this case, $\delta_{in}(v) = \delta_{out}(v)$, so conservation is preserved. As an exercise, extend this reasoning to the rest of the cases:

• $(u, v)$ is a forward edge and $(v, w)$ is a forward edge.
• $(u, v)$ is a backward edge and $(v, w)$ is a forward edge.
• $(u, v)$ is a backward edge and $(v, w)$ is a backward edge.

Thus, in every case $\delta_{in}(v) = \delta_{out}(v)$. Since $\sum_{e \text{ into } v} f(e) = \sum_{e \text{ out of } v} f(e)$ held for $f$, adding equal changes to both sides preserves the equality for $f'$. As $v$ was an arbitrary internal node, $f'$ satisfies conservation everywhere.

Together, these establish that $f'$ is a valid flow.

Termination. If all $c_e \in \mathbb{Z}$, then every residual capacity stays integral, so each bottleneck is a positive integer and value increase by at least 1 per iteration. Since value$(f) \le C := \sum_{e \text{out of } s} c_e$, the loop runs at most $C$ times.

Runtime Analysis. Suppose for flow network graph $G = (V, E)$, let $m = |E|$. We can find augmenting paths in $O(m)$ time and augments in $O(n)$ time (each path has at most $n$ nodes). This gives $O(mC)$ time overall, since the loop can run at most $C$ times. This is only pseudo-polynomial: the runtime depends on the capacities, not just on $n$ and $m$.

Since the algorithm doesn't specify which augmenting path to pick at each step, a poor choice of paths can be extremely slow. Consider a network where an internal edge has capacity 1 but every other edge has a much larger capacity $C$. If Ford-Fulkerson happens to alternate between two augmenting paths that both route through this narrow edge, forward through it in one path and backward (canceling flow) in the next, each round trip only increases the total flow by 1, even though a smarter choice of paths would saturate the network in just two augmentations.

Every edge has capacity 1000 except a‑b, whose capacity is 1. An unlucky sequence of augmenting paths that keeps crossing a‑b (forward, then backward to cancel it) makes Ford-Fulkerson take 2000 iterations, even though the max flow of 2000 could be reached in just 2.

Visualization Demo

Ford-Fulkerson Visualizer

Start with zero flow

Every edge begins at 0 flow.

Total flow0

flow active path residual back edge

Properties

Applications

Bipartite Matching

Max-flow Reduction

Min-cut Reduction

Practice

Problem 1.