12.7 Minimum Cut
Maximum flow asks how much can be sent from a source to a sink.
12.7 Minimum Cut
Problem
Maximum flow asks how much can be sent from a source to a sink. Minimum cut asks a complementary question: what is the smallest amount of capacity that must be removed to separate the source from the sink?
At first these sound like different problems. One measures throughput. The other measures vulnerability. In a transportation network, maximum flow tells you how many trucks can move from warehouses to stores. Minimum cut tells you which roads form the tightest bottleneck. In a communication network, maximum flow measures possible bandwidth. Minimum cut identifies the weakest separation between sender and receiver.
The useful fact is that these two values are always equal. Before proving that result, you need a precise model of cuts.
Solution
Partition the vertices of a flow network into two sets:
S-side
T-side
The source must belong to the first set, and the sink must belong to the second set.
A cut is usually written as:
(A, B)
where:
source ∈ A
sink ∈ B
A ∪ B = V
A ∩ B = ∅
The capacity of the cut is the total capacity of all directed edges going from A to B.
Edges going backward from B to A do not contribute to the cut capacity.
Example
Consider this network:
10
s --------> a
| |
5 | | 8
v v
b --------> t
10
Edges:
| Edge | Capacity |
|---|---|
| s -> a | 10 |
| s -> b | 5 |
| a -> t | 8 |
| b -> t | 10 |
One possible cut is:
A = {s}
B = {a, b, t}
The edges crossing from A to B are:
| Crossing edge | Capacity |
|---|---|
| s -> a | 10 |
| s -> b | 5 |
So the cut capacity is:
10 + 5 = 15
Another cut is:
A = {s, a, b}
B = {t}
The crossing edges are:
| Crossing edge | Capacity |
|---|---|
| a -> t | 8 |
| b -> t | 10 |
Cut capacity:
8 + 10 = 18
The first cut is smaller.
Computing Cut Capacity
For a cut (A, B), define:
capacity(A, B)
=
sum of c(u, v)
for all u ∈ A and v ∈ B
Only forward crossing edges count.
Suppose the graph also contains:
b -> a
with capacity 100.
For the cut:
A = {s, a}
B = {b, t}
the edge:
b -> a
does not count because it moves from B back to A.
This directionality is essential. A flow can only leave the source side through edges that go from A to B.
Why Every Cut Bounds Every Flow
A cut is a barrier between source and sink. Any flow from source to sink must cross from the source side into the sink side at least once.
Therefore the value of any feasible flow cannot exceed the capacity of any cut.
In symbols:
value(flow) ≤ capacity(cut)
This gives a simple upper bound.
If you exhibit a flow of value 15 and a cut of capacity 15, you have proven optimality immediately.
No larger flow can exist, because every source-to-sink transfer must cross that cut.
Example: Certifying Optimality
Use the previous graph:
| Edge | Capacity |
|---|---|
| s -> a | 10 |
| s -> b | 5 |
| a -> t | 8 |
| b -> t | 10 |
Construct this flow:
| Edge | Flow |
|---|---|
| s -> a | 10 |
| s -> b | 5 |
| a -> t | 8 |
| b -> t | 7 |
Flow value:
15
The cut:
A = {s}
B = {a, b, t}
has capacity:
15
Since:
flow value = cut capacity
the flow is maximum and the cut is minimum.
This is the most useful practical role of cuts: they provide certificates.
Finding a Cut from a Residual Graph
After a maximum-flow algorithm terminates, no augmenting path remains in the residual graph.
At that point, compute the set of vertices reachable from the source using only residual edges with positive capacity.
Call that set:
A
All other vertices form:
B = V - A
Because the sink is not reachable, it belongs to B.
The partition (A, B) is a minimum cut.
Example After Termination
Suppose the residual graph has positive-capacity reachability:
s reaches a
s cannot reach b
s cannot reach t
Then:
A = {s, a}
B = {b, t}
Now inspect the original graph and sum capacities of edges from A to B.
That sum is the minimum cut capacity.
Algorithm
Given a completed maximum-flow computation:
- Run DFS or BFS from the source in the residual graph.
- Mark every reachable vertex.
- Let marked vertices be
A. - Let unmarked vertices be
B. - Report all original edges from
AtoB. - Sum their capacities.
Pseudocode:
MinimumCut(G, residual, s):
A = vertices reachable from s in residual graph
B = V - A
cutEdges = []
for each original edge (u, v):
if u in A and v in B:
add (u, v) to cutEdges
return cutEdges
This algorithm is simple because the hard work has already been done by the max-flow computation.
Implementation Notes
Keep original capacities separate from residual capacities.
A common mistake is to compute cut capacity using the residual graph. The cut is defined on the original graph.
Residual reachability tells you which vertices belong to each side of the cut. Original capacities tell you the cut value.
In code, store each edge with enough information to identify whether it is an original edge or a reverse residual edge. When reporting cut edges, ignore artificial reverse edges.
Common Mistakes
Counting Backward Edges
Only edges from the source side to the sink side count.
Edges from the sink side back to the source side do not contribute to cut capacity.
Using Residual Capacities for Cut Value
Residual capacities are used to find the partition. Original capacities are used to compute the cut capacity.
Forgetting Direction
In undirected problems, each undirected connection must usually be modeled as two directed edges. The resulting cut may count one or both directions depending on the modeling goal.
Reporting a Cut Before Max Flow Finishes
Reachability in an intermediate residual graph does not necessarily produce a minimum cut. The residual graph must contain no path from source to sink.
Complexity
After max flow has been computed, extracting the minimum cut costs:
O(V + E)
for the reachability search plus one scan of the edge list.
The cut extraction step is rarely the bottleneck.
Discussion
Minimum cut is more than a companion problem to maximum flow. It is often the explanation for a maximum-flow answer.
A max-flow value tells you the throughput. A min-cut certificate tells you why the throughput cannot be larger.
This distinction matters in applied settings. If a logistics model says only 10,000 units can be shipped per day, the cut identifies the warehouse doors, rail links, truck lanes, or transfer points responsible for the limit. If a scheduler cannot assign all jobs, the cut identifies the capacity constraint that prevents feasibility.
Many reductions in this chapter rely on this diagnostic property. Project selection, image segmentation, closure problems, and certain scheduling models are often solved by building a graph, computing a min cut, and interpreting the source side and sink side as a decision.
Takeaway
A cut separates the source from the sink. Its capacity is the total capacity of original edges crossing from the source side to the sink side. Every feasible flow is bounded above by every cut. When a flow value equals a cut capacity, both are optimal.
After a maximum-flow algorithm terminates, the minimum cut can be recovered by a single reachability search in the residual graph. This gives maximum-flow algorithms not only an answer, but also a certificate explaining the bottleneck.