Minimum S-T Cut

Minimum S-T Cut is the classic payoff of max-flow theory. It asks: what is the cheapest set of edges to sever so the source can no longer reach the sink? The surprising answer is that you already compute it for free when you compute the maximum flow.

The slow way first

The brute-force definition tempts you to try every way to split the vertices into a source side (containing s) and a sink side (containing t), sum the crossing edges, and take the minimum. With n vertices there are 2^(n-2) ways to split the middle — exponential. Hopeless for anything but toy graphs.

The question to ask: is there a quantity I already know how to compute that equals the answer? There is. The max-flow min-cut theorem says the value of the maximum flow from s to t exactly equals the capacity of the minimum cut.

The idea: max flow, then BFS the leftovers

Run any max-flow algorithm first. It leaves behind a residual graph: each edge remembers how much spare capacity it still has. Now BFS (or DFS) from s, but only follow residual edges that still have spare capacity. The vertices you can reach form the source side; everything you cannot reach is the sink side. The minimum cut is every original edge that goes from a reachable vertex to an unreachable one.

The key insight: a saturated edge has zero residual capacity, so BFS cannot cross it. That is precisely why the frontier of the BFS lands on the bottleneck edges — the ones that limit the flow.

Walk through it

Step through the animation. First the max flow settles to 4. Then BFS starts at S (green) and grows along residual edges, reaching A but getting blocked by the saturated frontier. B, C, and T stay dim on the sink side. Finally the edges crossing from the reachable set into the unreachable set light up red — that is the cut, and its capacities sum to 4.

Pseudocode

run max flow from s to t; this fills the residual graph
reach = { s }                         # vertices reachable in the residual graph
BFS from s, but only across residual edges with spare capacity > 0
    add every newly reached vertex to reach
cut = empty list
for each ORIGINAL edge (u, v):
    if u is in reach and v is not in reach:
        add (u, v) to cut             # this edge crosses the frontier
return cut                            # total capacity of cut == max flow

The Python solution

def min_cut(graph, s, t):
    # 1) run max flow; residual stores leftover capacity
    flow = max_flow(graph, s, t)
    # 2) BFS the residual graph from the source
    reach = set([s])
    queue = [s]
    while queue:
        u = queue.pop()
        for v in residual[u]:
            if residual[u][v] > 0 and v not in reach:
                reach.add(v); queue.append(v)
    # 3) edges from reachable -> unreachable are the cut
    cut = []
    for u in reach:
        for v in graph[u]:
            if v not in reach:
                cut.append((u, v))
    return cut, flow

• max_flow does the heavy lifting and leaves the residual graph behind for us to inspect.
• reach is the source side: every vertex BFS can still get to using leftover capacity.
• The BFS only traverses edges where residual[u][v] > 0 — a saturated edge has zero spare and blocks the search.
• Lines 13-16 are the cut itself: scan every original edge and keep the ones that leave reach and land outside it.
• The total capacity of those crossing edges equals flow — the theorem guarantees it.

Complexity

The cut-extraction step is just one linear BFS plus an edge scan, so the cost is dominated by the max-flow computation itself (for example O(VE^2) with Edmonds-Karp). Finding the cut on top of the flow is essentially free.

When this pattern shows up

Practice