Max Flow / Min Cut

Imagine a network of water pipes connecting a reservoir (source) to a city (sink). Each pipe has a maximum flow rate — its capacity. The question: how much water can flow through the network per second?

That's the max flow problem. The answer turns out to equal the minimum "cut" capacity — the cheapest set of pipes you'd need to sever to completely stop all water. This relationship is one of the most beautiful theorems in combinatorics.

What's a Flow Network?

Formally: a directed graph where each edge (u→v) has a capacity c(u,v) ≥ 0. We pick a source s and a sink t. A valid flow assigns a value f(u,v) to each edge satisfying:

Capacity constraint: f(u,v) ≤ c(u,v) — can't exceed the pipe limit.
Conservation: at every vertex except s and t, total flow in = total flow out — water doesn't pile up or disappear.

The value of the flow is the net amount leaving s (which always equals the net amount arriving at t).

Augmenting Paths

The Ford-Fulkerson method finds max flow by repeatedly finding an augmenting path — a route from s to t in the residual graph where every edge has leftover capacity (found via BFS or DFS). Send flow along this path (limited by the tightest pipe), then repeat.

Stop when no augmenting path exists. At that point, you've found max flow.

The Residual Graph — and the Crucial Backward Edge

For each pipe (u→v) with capacity c carrying flow f, the residual graph has:

A forward edge (u→v) with remaining capacity c−f.
A backward edge (v→u) with capacity f — modeling the ability to "undo" some previously sent flow.

Backward edges are the clever part. Without them, a greedy augmenting strategy could get stuck on a suboptimal routing. Backward edges let the algorithm reroute flow that was sent the wrong way.

Max-Flow Min-Cut Theorem

A cut partitions all vertices into two groups: S (containing the source) and T (containing the sink). Its capacity is the total capacity of edges crossing from S into T (reverse-direction edges don't count).

The theorem: maximum flow value = minimum cut capacity. The min cut is exactly the bottleneck constraining all flow. When Ford-Fulkerson finishes, the vertices still reachable from s in the residual graph form S — and the corresponding cut is the minimum cut.

Ford-Fulkerson with BFS (Edmonds-Karp)

from collections import deque

def max_flow(graph, source, sink):
    """graph[u][v] = capacity (0 if no edge). Returns max flow."""
    n = len(graph)
    total = 0

    while True:
        # BFS to find shortest augmenting path
        parent = [-1] * n
        parent[source] = source
        q = deque([source])
        while q and parent[sink] == -1:
            u = q.popleft()
            for v in range(n):
                if parent[v] == -1 and graph[u][v] > 0:
                    parent[v] = u
                    q.append(v)

        if parent[sink] == -1:
            break  # No augmenting path

        # Find bottleneck
        flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            flow = min(flow, graph[u][v])
            v = u

        # Update residual capacities
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= flow
            graph[v][u] += flow  # backward edge
            v = u

        total += flow

    return total

# 4-node network: 0=source, 3=sink
#   0->1 cap 3, 0->2 cap 2, 1->3 cap 2, 2->3 cap 3, 1->2 cap 1
g = [[0,3,2,0],[0,0,1,2],[0,0,0,3],[0,0,0,0]]
print(max_flow(g, 0, 3))  # 4

Output

Complexity

🌊 Ford-Fulkerson (DFS paths)With irrational capacities this can run forever; with integers it terminates but can be slow

Depends on max flow value\(O(E · |f|)\)

🔍 Edmonds-Karp (BFS paths)BFS finds shortest paths; augmenting path lengths only grow, bounding total work

Polynomial — always terminates fast\(O(VE^2)\)

✂️ Finding min cutBFS on the final residual graph: vertices reachable from s form the S-side of the min cut

Linear after max flow\(O(V+E)\)

🔄 Residual graph updateForward and backward capacities each updated in one assignment