Max-Flow Min-Cut

Picture a network of pipes from a source to a sink, each pipe with a maximum capacity. How much total flow can you push through? That is the max-flow question. A separate-sounding question: what is the cheapest way to cut a set of pipes so that no flow can get through at all? That is min-cut. The surprising theorem — and the reason this pairing gets its own name — is that these two numbers are always exactly equal.

The idea: push flow along paths, undo mistakes with reverse edges

The Ford-Fulkerson method repeatedly finds any path from source to sink with spare capacity (an "augmenting path"), pushes as much flow as that path's bottleneck edge allows, and repeats until no augmenting path remains. The trick that makes this correct rather than greedy-and-wrong: every time you push flow along an edge $u \to v$, you also open up a reverse edge $v \to u$ with capacity equal to the flow just pushed. A later augmenting path is allowed to use that reverse edge to "cancel" an earlier bad decision. Without reverse edges the algorithm can get stuck on a suboptimal answer; with them, it's proven to find the true maximum.

Edmonds-Karp is Ford-Fulkerson with one specific rule: always pick the augmenting path with the fewest edges (found via BFS). That single choice bounds the algorithm to $O(VE^2)$ — a concrete, guaranteed running time, versus plain Ford-Fulkerson which can be slow on pathological capacities.

When no more augmenting paths exist, the set of nodes still reachable from the source (call it $S$) and everything else ($T$) defines a cut, and the max-flow-min-cut theorem says the total flow achieved equals the total capacity of edges crossing from $S$ to $T$ — that boundary is simultaneously the bottleneck and the answer.

Worked example

Capacities: S-A 5, S-B 3, A-C 2, B-D 3, C-T 10, D-T 10. First augmenting path S-A-C-T, bottleneck $\min(5,2,10)=2$; push 2. Second path S-B-D-T, bottleneck $\min(3,3,10)=3$; push 3. Total flow so far $=5$. Any further path from S must reuse A-C (now saturated at 0 remaining) or B-D (also saturated), so no augmenting path exists — max flow is 5, matching the cut {A-C, B-D} with capacity $2+3=5$.

from collections import deque

def bfs_augment(cap, s, t, n):
    parent = [-1] * n
    parent[s] = s
    q = deque([s])
    while q:
        u = q.popleft()
        for v in range(n):
            if parent[v] == -1 and cap[u][v] > 0:
                parent[v] = u
                q.append(v)
    return parent if parent[t] != -1 else None

def edmonds_karp(cap, s, t, n):      # O(V E^2)
    flow = 0
    while (parent := bfs_augment(cap, s, t, n)):
        v, bottleneck = t, float("inf")
        while v != s:
            u = parent[v]
            bottleneck = min(bottleneck, cap[u][v])
            v = u
        v = t
        while v != s:
            u = parent[v]
            cap[u][v] -= bottleneck
            cap[v][u] += bottleneck   # reverse edge
            v = u
        flow += bottleneck
    return flow

Where it shows up

Interview framing: bipartite matching (assign traders to desks, orders to counterparties) reduces to max flow with unit capacities; "maximum number of matches" questions are almost always this in disguise. On a desk, capacity-constrained order routing across venues (each venue has a max fill size) and stress-testing a payment or clearing network for its weakest link both map directly onto max-flow-min-cut.