Applications of Maximum Flow

The maximum-flow framework extends far beyond literal flow problems. Many combinatorial optimisation problems reduce to flow networks. The key skill for Tripos is recognising when a problem “feels like max flow” and constructing the right network.

Edge-Disjoint Paths

Problem: find the maximum number of edge-disjoint paths from $s$ to $t$ in a directed graph.

Reduction: give every edge capacity 1. Run max flow. Each unit of flow corresponds to one path. Since capacities are 1, no edge can carry flow from two different paths simultaneously. The max flow value equals the maximum number of edge-disjoint paths. Running time: $O(|V| \cdot |E|^2)$ with Edmonds-Karp.

Menger’s Theorem then follows: the maximum number of edge-disjoint $s$-$t$ paths equals the minimum number of edges whose removal disconnects $s$ from $t$ (the minimum edge cut).

Vertex-Disjoint Paths

Problem: find maximum number of vertex-disjoint $s$-$t$ paths (paths sharing no vertices except $s$ and $t$).

Reduction: split each vertex $v \neq s, t$ into $v_{\text{in}}$ and $v_{\text{out}}$ with a capacity-1 edge $v_{\text{in}} \to v_{\text{out}}$. Replace each original edge $(u, v)$ with $(u_{\text{out}}, v_{\text{in}})$ of capacity $\infty$ (or a sufficiently large value). Run max flow. The capacity-1 internal edge ensures each vertex is used by at most one path.

Circulation with Demands

Problem: each vertex $v$ has a demand $d(v)$: positive means supply, negative means demand (net requirement to consume flow). Find a feasible flow satisfying all demands, or determine none exists.

Reduction: add supersource $s^*$ and supersink $t^*$. For each vertex with $d(v) > 0$ (supply), add edge $(s^*, v)$ with capacity $d(v)$. For each vertex with $d(v) < 0$ (demand), add edge $(v, t^*)$ with capacity $-d(v)$. Original edges keep their capacities. Run max flow from $s^*$ to $t^*$. Feasible circulation exists iff all edges from $s^*$ are saturated.

Project Selection / Maximum Closure

Problem: given a set of projects, each with profit $p_i$ (positive or negative), and dependencies (project $a$ requires project $b$), select a subset maximising total profit.

Reduction: bipartite-style network. Projects with $p_i > 0$ connect from $s$ with capacity $p_i$. Projects with $p_i < 0$ connect to $t$ with capacity $-p_i$. For each dependency $a \to b$ ($a$ requires $b$), add edge $(a, b)$ with capacity $\infty$. The minimum cut produces the optimal selection: projects on the $s$-side of the cut are selected. Max profit $= \sum_{p_i > 0} p_i - \text{min-cut capacity}$.

Image Segmentation

Problem: partition pixels into foreground and background, balancing pixel affinities with prior expectations.

Reduction: graph where each pixel is a vertex with edges to neighbours. Source represents foreground, sink represents background. Edge capacities encode how strongly a pixel “prefers” each label, and how much adjacent pixels should agree. The minimum cut gives the optimal segmentation.

Supersources and Supersinks

Multiple sources $s_1, \ldots, s_m$ and multiple sinks $t_1, \ldots, t_n$ reduce to a single source/sink pair by adding a supersource $s$ with infinite-capacity edges to each $s_i$, and a supersink $t$ with infinite-capacity edges from each $t_j$. This is a standard trick for any flow problem with multiple origins or destinations.

Recognising Flow Problems

Common signs a problem reduces to max flow:

• Items must be assigned to slots, with each item/slot used at most once (capacity 1)
• Constraints are local (edge capacities) and sequential (paths)
• The objective involves a “bottleneck” or “separation”
• The problem is about cutting or separating a graph into two parts

Summary

Application	Key Reduction Trick
Edge-disjoint paths	Capacity 1 on all edges
Vertex-disjoint paths	Split each vertex $v \to v_{\text{in}} \to v_{\text{out}}$ with capacity 1
Circulation	Supersource/sink + demands as edge capacities
Project selection	Source for profits, sink for costs, $\infty$-capacity dependencies
Image segmentation	Graph on pixels, min-cut = optimal labelling
Multiple sources/sinks	Supersource + supersink with $\infty$ edges

Past Tripos: y2024p2q7, y2022p1q9.