ADVANCED ALGORITHMS - NETWORK FLOW:Max-Flow Min-Cut Theorem

Max-Flow Min-Cut Theorem

What is a Cut?

An s-t cut is a partition (S, T) of vertices with s ∈ S and t ∈ T.

The capacity of a cut = sum of capacities of edges from S to T (forward edges only):

cap(S, T) = Σ c(u, v) for (u, v) with u ∈ S, v ∈ T

Key observation: For any flow f and any cut (S, T):

|f| ≤ cap(S, T)

This is because all flow from s to t must cross the cut.

Max-Flow Min-Cut Theorem

Theorem (Ford-Fulkerson, 1956):

The value of maximum flow = capacity of minimum cut.

Proof (three equivalent conditions — one implies the next, cyclically):

1. f is a maximum flow
2. There is no augmenting path from s to t in residual graph Gf
3. There exists an s-t cut (S, T) with cap(S, T) = |f|

The critical direction is 2 → 3: Let S = {vertices reachable from s in Gf}. Since t ∉ S (no augmenting path), (S, T = V − S) is a valid cut. For every edge (u, v) crossing S→T: f(u,v) = c(u,v) (fully saturated, otherwise v would be reachable). So |f| = cap(S, T).

Finding the Min-Cut

from collections import deque

def find_min_cut(capacity, source, sink):
    """
    Find min cut after running max-flow.
    Returns: (min_cut_value, cut_edges)
    """
    n = len(capacity)
    _, residual = ford_fulkerson_bfs(capacity, source, sink)
    
    # BFS on residual graph to find S (reachable from source)
    reachable = [False] * n
    queue = deque([source])
    reachable[source] = True
    
    while queue:
        u = queue.popleft()
        for v in range(n):
            if not reachable[v] and residual[u][v] > 0:
                reachable[v] = True
                queue.append(v)
    
    # Min-cut edges: from reachable to non-reachable with original capacity > 0
    cut_edges = []
    min_cut_value = 0
    
    for u in range(n):
        if reachable[u]:
            for v in range(n):
                if not reachable[v] and capacity[u][v] > 0:
                    cut_edges.append((u, v, capacity[u][v]))
                    min_cut_value += capacity[u][v]
    
    return min_cut_value, cut_edges


# Verify: max flow = min cut
cap = [[0,10,10,0],[0,0,1,10],[0,0,0,10],[0,0,0,0]]
max_flow, _ = ford_fulkerson_bfs(cap, 0, 3)
min_cut_val, cut = find_min_cut(cap, 0, 3)
assert max_flow == min_cut_val  # Always equal!
print(f"Max flow = Min cut = {max_flow}")  # 20
print(f"Cut edges: {cut}")

Applications of Min-Cut

Image Segmentation (Boykov-Kolmogorov)

Pixels are nodes. Edge weights encode similarity between neighboring pixels and affinity to foreground/background seeds. Min-cut separates the image into foreground/background while minimizing total "boundary cost".

Network Reliability

Minimum edge cut of a communication network = minimum number of links whose failure disconnects the network. This tells you the most vulnerable bottleneck.

Project Selection

• Profit nodes: Projects with positive profit
• Cost nodes: Resources needed
• Dependency edges: Project needs resource
• Min-cut gives the maximum-profit selection respecting dependencies

Gomory-Hu Tree: All-Pairs Min-Cuts in n−1 Max-Flow Calls

Computing all n(n−1)/2 pairwise min-cuts naively takes O(n²) max-flow calls. The Gomory-Hu tree stores all pairwise min-cut values in a single tree with n−1 edges, computed with just n−1 max-flow calls.

Practice Problems

1. Find the minimum cut and its edges in a given network
2. Prove that in a planar graph, shortest s-t path in the dual = min cut in the primal
3. Formulate "assign n tasks to m machines with capacity constraints" as a flow problem
4. Given a network, find all edges that lie on some minimum cut