Network Flows - Part 5

So far in this series, we've built up the theory of network flows — definitions, the Max-Flow Min-Cut Theorem, and efficient algorithms. Now comes the payoff. Maximum flow is not just a problem in its own right; it's a tool for solving a surprising variety of other problems. In this part, we'll see three applications that look very different on the surface but all reduce to finding a maximum flow in a cleverly constructed network.

Bipartite Matching

Our first application connects directly to the Introduction to Graph Theory series. In Part 8 of that series, we studied matchings in bipartite graphs — pairing up vertices from two groups so that no vertex is used twice. It turns out that finding a maximum matching in a bipartite graph is equivalent to finding a maximum flow in a specific network.

Given a bipartite graph $G = (A \cup B, E)$, we construct a flow network $N$ as follows:

1. Create a source $s$ and a sink $t$.
2. For each vertex $a \in A$, add an arc $(s, a)$ with capacity $1$.
3. For each edge $(a, b) \in E$ with $a \in A$ and $b \in B$, add an arc $(a, b)$ with capacity $1$.
4. For each vertex $b \in B$, add an arc $(b, t)$ with capacity $1$.

Every arc has capacity $1$, so by the Integrality Theorem (Theorem 2 from Part 3), there exists a maximum flow that is integer-valued — meaning each arc carries either $0$ or $1$ unit of flow.

Theorem 4. The value of a maximum flow in $N$ equals the size of a maximum matching in $G$.

Proof. We show a bijection between integer flows and matchings.

Given an integer flow $f$ in $N$, consider the set $M = \{(a,b) : a \in A, b \in B, f(a,b) = 1\}$. We claim $M$ is a matching. For any $a \in A$, at most $1$ unit of flow enters $a$ (since $c(s,a) = 1$), so at most one arc from $a$ to $B$ carries flow — meaning $a$ appears in at most one edge of $M$. Similarly, for any $b \in B$, at most $1$ unit leaves through $(b,t)$, so $b$ appears in at most one edge. Thus $M$ is a valid matching of size $|f|$.

Conversely, given a matching $M$ in $G$, define a flow by setting $f(s,a) = f(a,b) = f(b,t) = 1$ for each edge $(a,b) \in M$ and $0$ everywhere else. This is a valid flow of value $|M|$: capacity constraints are satisfied (all capacities are $1$), and flow conservation holds at every intermediate vertex.

Since larger flows correspond to larger matchings and vice versa, maximizing one is equivalent to maximizing the other.

Let's try a small example. Consider the bipartite graph with $A = \{a_1, a_2, a_3\}$, $B = \{b_1, b_2\}$, and edges $\{(a_1, b_1), (a_1, b_2), (a_2, b_1), (a_3, b_2)\}$. The flow network adds $s$ connected to all of $A$ and $t$ connected from all of $B$, all with capacity $1$. Running Edmonds-Karp on this network finds a maximum flow of value $2$, corresponding to the matching $\{(a_1, b_1), (a_3, b_2)\}$ (or equivalently $\{(a_2, b_1), (a_1, b_2)\}$). Since $|B| = 2$, we cannot match all three vertices in $A$ — and indeed Hall's condition fails for $S = A$: $|N(A)| = 2 < 3 = |A|$.

This reduction also gives us a new proof of König's theorem (Theorem 12 from the graph theory series). The minimum cut in $N$ corresponds to a minimum vertex cover in $G$, so König's equality $\nu(G) = \tau(G)$ follows directly from the Max-Flow Min-Cut Theorem¹.

Edge-Disjoint Paths

Our second application answers a natural question about connectivity: how many "independent" routes exist between two vertices? More precisely, given a directed graph $D = (V, A)$ and two vertices $s$ and $t$, how many paths from $s$ to $t$ can we find that share no arcs?

Definition 11. Two $s$-$t$-paths are edge-disjoint (or arc-disjoint in digraphs) if they share no arc.

The connection to flows is immediate: treat the digraph as a flow network with capacity $1$ on every arc. An integer flow of value $k$ decomposes into $k$ unit-flow paths from $s$ to $t$, and since each arc has capacity $1$, these paths are arc-disjoint.

Theorem 5 (Menger, 1927). In a directed graph, the maximum number of arc-disjoint $s$-$t$-paths equals the minimum number of arcs whose removal disconnects $t$ from $s$.

Proof. This is a direct consequence of the Max-Flow Min-Cut Theorem applied to the network with unit capacities. The maximum flow value equals the maximum number of arc-disjoint paths (by integrality and flow decomposition). The minimum cut capacity equals the minimum number of arcs that must be removed to separate $s$ from $t$ (since each arc has capacity $1$, the cut capacity is just the number of arcs crossing the cut). By max-flow min-cut, these two quantities are equal.

Menger's theorem predates the Max-Flow Min-Cut Theorem by nearly three decades — Menger proved it in 1927, while Ford and Fulkerson's theorem came in 1956. In a sense, Menger's theorem was a precursor that hinted at the deeper duality between flows and cuts.

There is also a vertex-disjoint version: two paths are vertex-disjoint if they share no internal vertex (they may share $s$ and $t$).

Theorem 6 (Menger, vertex version). The maximum number of internally vertex-disjoint $s$-$t$-paths equals the minimum number of vertices (other than $s$ and $t$) whose removal disconnects $t$ from $s$.

This can also be proved via max-flow, using a standard trick: replace each vertex $v$ (other than $s$ and $t$) with two copies $v_{in}$ and $v_{out}$ connected by an arc $(v_{in}, v_{out})$ of capacity $1$. All arcs originally entering $v$ now enter $v_{in}$, and all arcs originally leaving $v$ now leave from $v_{out}$. The capacity-$1$ arc between the copies ensures that at most one path passes through $v$, effectively enforcing vertex-disjointness.

Project Selection

Our third application comes from optimization and has a very different flavor. Imagine a company evaluating a set of potential projects. Each project has a profit (which may be positive or negative — some projects are investments that cost money). Some projects depend on others: if you undertake project $i$, you must also undertake project $j$. The goal is to select a subset of projects that maximizes total profit while respecting all dependencies.

Formally, we have a set of projects $P = \{1, 2, \ldots, n\}$ with profits $p_i \in \mathbb{R}$, and a set of dependencies — pairs $(i, j)$ meaning "if project $i$ is selected, then project $j$ must also be selected." We want to find a subset $S \subseteq P$ such that $S$ is closed (if $i \in S$ and $(i,j)$ is a dependency, then $j \in S$) and $\sum_{i \in S} p_i$ is maximized.

This is the project selection problem (also called the closure problem), and it can be solved by a maximum flow computation.

We construct the following flow network:

1. Create a source $s$ and a sink $t$.
2. For each project $i$ with $p_i > 0$, add an arc $(s, i)$ with capacity $p_i$.
3. For each project $i$ with $p_i < 0$, add an arc $(i, t)$ with capacity $|p_i|$.
4. For each dependency $(i, j)$, add an arc $(i, j)$ with capacity $\infty$.

The infinite capacities on dependency arcs ensure that they are never part of a minimum cut — cutting them would give infinite capacity. A finite minimum cut $(S, T)$ with $s \in S$ and $t \in T$ corresponds to a closed set: the selected projects are $S \setminus \{s\}$.

Theorem 7. The maximum profit of a closed set equals $\sum_{i: p_i > 0} p_i - |f^*|$, where $|f^*|$ is the maximum flow value (equivalently, the minimum cut capacity).

The intuition is as follows. Start by tentatively selecting all profitable projects — this gives profit $\sum_{i: p_i > 0} p_i$. The minimum cut tells us the "cost" of making the selection feasible: we either give up some profitable projects (cutting their arcs from $s$) or include some unprofitable ones (cutting their arcs to $t$). The minimum cut minimizes this total cost, and what remains is the optimal profit.

Consider a small example with four projects: $p_1 = 5$, $p_2 = -3$, $p_3 = 4$, $p_4 = -1$, and dependencies $(1, 2)$ and $(3, 4)$. Project $1$ yields profit $5$ but requires project $2$ (which costs $3$), and project $3$ yields $4$ but requires project $4$ (which costs $1$).

The flow network has arcs $(s,1)$ with capacity $5$, $(s,3)$ with capacity $4$, $(2,t)$ with capacity $3$, $(4,t)$ with capacity $1$, $(1,2)$ with capacity $\infty$, and $(3,4)$ with capacity $\infty$. The minimum cut turns out to have capacity $4$: we cut $(2,t)$ and $(4,t)$, meaning we include all four projects. The maximum profit is $(5 + 4) - 4 = 5$, which matches $p_1 + p_2 + p_3 + p_4 = 5 - 3 + 4 - 1 = 5$. Selecting all projects is optimal because the profitable ones outweigh the costs of their dependencies².

The Power of Reductions

The three applications in this part illustrate a general principle: many combinatorial optimization problems can be reduced to maximum flow. The art lies in designing the right network — choosing the vertices, arcs, and capacities so that the max-flow min-cut structure captures the problem's constraints and objectives.

This is one of the reasons network flow theory occupies such a central place in optimization: not because flow problems themselves are so common, but because so many other problems can be expressed as flow problems and solved with the same efficient algorithms.

Looking Ahead

We've seen that maximum flow is a versatile tool, but it optimizes only one thing: the total amount of flow. What if we also care about cost — for example, different routes have different shipping costs, and we want to maximize flow at minimum expense? In the next part, we'll introduce the minimum-cost flow problem, which adds a cost dimension to our networks and opens up an even richer set of applications.