14.4 Maximum flow and minimum cut problems

Maximum flow and minimum cut problems

Maximum flow and minimum cut problems are central to network optimization. They answer two related questions: What's the most flow you can push through a network? and What's the cheapest way to disconnect the source from the sink? The remarkable connection between these two questions, formalized by the Max-Flow Min-Cut Theorem, makes them some of the most powerful tools in combinatorics and operations research.

These problems show up everywhere: routing data through the internet, distributing power across electrical grids, optimizing supply chains, and even segmenting images in computer vision.

Defining Maximum Flow and Minimum Cut

A flow network is a directed graph with two special nodes: a source $s$ (where flow originates) and a sink $t$ (where flow is collected). Each directed edge $(u, v)$ has a capacity $c(u, v) \geq 0$ that limits how much flow can pass through it.

A flow assigns a value $f(u, v)$ to each edge, subject to two constraints:

• Capacity constraint: $0 \leq f(u, v) \leq c(u, v)$ for every edge
• Flow conservation: At every node except $s$ and $t$, the total flow in equals the total flow out

The maximum flow problem asks: what is the largest total flow you can send from $s$ to $t$ while respecting all capacity constraints?

A cut $(S, T)$ partitions the vertices into two disjoint sets $S$ and $T$, where $s \in S$ and $t \in T$. The capacity of a cut is the sum of capacities of all edges going from $S$ to $T$:

$c(S, T) = \sum_{u \in S,\, v \in T} c(u, v)$

Note that edges going from $T$ back to $S$ do not count toward the cut capacity.

The minimum cut problem asks: which cut has the smallest total capacity? This represents the bottleneck of the network, the "narrowest point" that limits overall flow.

Ford-Fulkerson Algorithm for Maximum Flow

Algorithm Overview

The Ford-Fulkerson method is the foundational approach for computing maximum flow. It relies on two key ideas:

• Residual graph: After pushing some flow through the network, the residual graph tracks how much additional flow each edge can carry. If edge $(u, v)$ has capacity $c(u, v)$ and current flow $f(u, v)$, then its residual capacity is $c_f(u, v) = c(u, v) - f(u, v)$. The residual graph also includes a back edge $(v, u)$ with residual capacity $f(u, v)$, which represents the option to "undo" previously sent flow.
• Augmenting path: Any path from $s$ to $t$ in the residual graph where every edge has positive residual capacity. The flow along this path can be increased by the minimum residual capacity on the path (the bottleneck edge).

Steps

1. Initialize all edge flows to zero.
2. Construct the residual graph based on current flows.
3. Search for an augmenting path from $s$ to $t$ in the residual graph (using DFS, BFS, or another search method).
4. If an augmenting path exists, find its bottleneck capacity $\delta$ (the minimum residual capacity along the path).
5. Push $\delta$ units of flow along the path: increase flow on forward edges and decrease flow on back edges.
6. Update the residual graph and repeat from step 3.
7. When no augmenting path exists, the current flow is maximum.

A Quick Example

Consider a simple network with four nodes: $s, a, b, t$. Edges and capacities: $s \to a$ (cap 10), $s \to b$ (cap 5), $a \to b$ (cap 8), $a \to t$ (cap 7), $b \to t$ (cap 10).

• First augmenting path: $s \to a \to t$, bottleneck = 7. Push 7 units.
• Second augmenting path: $s \to b \to t$, bottleneck = 5. Push 5 units.
• Third augmenting path: $s \to a \to b \to t$, bottleneck = 3 (limited by remaining capacity on $s \to a$). Push 3 units.
• No more augmenting paths. Maximum flow = $7 + 5 + 3 = 15$.

Variants and Complexity

The basic Ford-Fulkerson method doesn't guarantee polynomial time if capacities are irrational, or even if they're large integers (it can take many iterations with small augmentations). Several variants fix this:

• Edmonds-Karp algorithm: Uses BFS to always find the shortest augmenting path. This guarantees $O(VE^2)$ time complexity.
• Dinic's algorithm: Builds a level graph (layers by BFS distance from $s$) and finds blocking flows that saturate at least one edge on every $s$-to-$t$ path. Runs in $O(V^2 E)$.
• Push-relabel algorithms: Instead of finding full augmenting paths, these maintain a preflow (where inflow can temporarily exceed outflow at internal nodes) and push excess flow toward $t$. Goldberg-Tarjan's version runs in $O(V^2 E)$ or $O(V^3)$ depending on implementation.
• Capacity scaling: Prioritizes augmenting paths with large bottleneck capacity, converging faster. Runs in $O(E^2 \log C)$ where $C$ is the maximum capacity.

Practical Considerations

• For sparse graphs, Dinic's algorithm tends to perform well. For dense graphs, push-relabel methods often win.
• Use integer capacities when possible to avoid floating-point precision issues.
• Preprocessing helps: remove edges with zero capacity, merge parallel edges, and eliminate nodes with no path to $s$ or $t$.
• For very large networks, parallel and distributed implementations exist, though they add significant complexity.

Max-Flow Min-Cut Theorem and Implications

Theorem Statement

This is one of the most important results in combinatorial optimization. It connects two seemingly different problems and shows they are dual to each other: solving one automatically solves the other.

Proof Sketch

The proof works in three parts:

1. Weak duality: For any flow $f$ and any cut $(S, T)$, the value of $f$ is at most $c(S, T)$. This follows because all flow from $s$ to $t$ must cross the cut, and it can't exceed the cut's capacity.

2. Termination of Ford-Fulkerson: When the algorithm terminates, no augmenting path exists in the residual graph.

3. Constructing the tight cut: Define $S$ as the set of vertices reachable from $s$ in the final residual graph, and $T = V \setminus S$. Since no augmenting path exists, $t \notin S$, so $(S, T)$ is a valid cut. Every edge from $S$ to $T$ in the original graph must be fully saturated (otherwise there'd be residual capacity and the endpoint would be reachable). Every edge from $T$ to $S$ must carry zero flow (otherwise the back edge would provide residual capacity). So the flow value equals $c(S, T)$, and combined with weak duality, both are optimal.

Why This Matters

• Finding the min cut: Run any max-flow algorithm, then identify vertices reachable from $s$ in the final residual graph. The edges crossing from reachable to unreachable vertices form the minimum cut.
• Bottleneck identification: The minimum cut reveals the most constrained part of the network. In a transportation system, these are the roads that limit overall throughput.
• Network reliability: The min cut tells you the fewest edges an adversary would need to destroy to disconnect $s$ from $t$.

Extensions

• Multicommodity flow: Multiple source-sink pairs share the same network. The max-flow min-cut theorem doesn't hold exactly here, but approximate versions (with a $O(\log k)$ gap for $k$ commodities) exist.
• Parametric max-flow: Studies how the maximum flow changes as edge capacities vary continuously.
• Vertex capacities: If nodes also have capacity limits, you can model this by splitting each node into two nodes connected by an edge whose capacity equals the node's capacity.

Real-World Applications

Network Optimization and Resource Allocation

• Bipartite matching: Matching employees to tasks, students to dorm rooms, or organs to recipients. Model as a flow network with source connected to one side, sink connected to the other, and unit-capacity edges. The max flow equals the size of the maximum matching (this is König's theorem in disguise).
• Supply chain optimization: Products flow from factories through warehouses to retail stores. Edge capacities represent shipping limits. Max flow determines the maximum throughput of the distribution network.
• Transportation and routing: Vehicles through road networks, data packets through internet infrastructure, electricity through power grids. Min cuts identify the critical links whose failure would most reduce system capacity.

Image Processing and Computer Vision

Image segmentation is one of the most successful applications. To separate foreground from background in an image:

1. Treat each pixel as a node in a graph.
2. Connect neighboring pixels with edges whose capacities reflect how similar the pixels are (similar pixels get high capacity, so the cut avoids separating them).
3. Connect each pixel to a virtual source (foreground) and sink (background) with capacities based on how likely that pixel belongs to each class.
4. Compute the minimum cut. Pixels on the source side become foreground; pixels on the sink side become background.

This approach also extends to stereo vision (3D reconstruction from two camera views), medical image analysis (segmenting tumors or organs), and video object tracking.

Social Network Analysis

• Community detection: Minimum cuts can identify natural divisions in social graphs where few connections bridge different groups.
• Information flow bottlenecks: The min cut between two nodes reveals the most constrained channels for information transfer.
• Influence maximization: Understanding flow structure helps identify which nodes, if activated, can spread information (or a product recommendation) most effectively through the network.