Max-Flow Min-Cut Theorem, in depth: weak and strong duality, the LP view, minimum cut structure, certificates and modelling with cuts

Networks, flows and cuts

A network is a directed graph with a capacity c(u, v) ≥ 0 on each arc, a source s and a sink t. A flow assigns f(u, v) to each arc with two rules: 0 ≤ f(u, v) ≤ c(u, v) (capacity), and at every vertex other than s and t, flow in equals flow out (conservation). The value |f| is the net flow out of s; conservation forces the same amount into t.

An s-t cut is a partition of the vertices into two sides: S, which holds s, and T, which holds t. Its capacity c(S, T) is the sum of capacities of arcs going from S to T. Arcs from T back to S do not count, a common source of wrong hand calculations.

Theorem. The maximum value of a flow equals the minimum capacity of an s-t cut.

Weak duality: every flow is bounded by every cut

Half of the theorem is easy and holds for every flow and every cut: |f| ≤ c(S, T). The proof is two steps.

Step 1: every cut carries the full flow. For any cut, the flow from S to T minus the flow from T to S equals |f|. Add up, over all vertices in S, flow out minus flow in. For s that is |f|; for every other vertex of S it is 0 by conservation. Arcs with both ends inside S appear once as out and once as in, so they cancel, leaving exactly the arcs that cross the cut.

Step 2: bound it. Flow from S to T is at most the capacity of those arcs, and flow from T to S is at least 0. So |f| = f(S→T) − f(T→S) ≤ c(S, T).

This weak duality is what makes certificates work: a flow and a cut of equal value are both optimal, whatever algorithm produced them.

Strong duality: the bound is always tight

The hard half is that equality is always reachable. The standard proof shows three statements are equivalent for a flow f: (1) f is a maximum flow; (2) the residual graph has no s-t path; (3) |f| = c(S, T) for some cut. (1) implies (2) because a residual path would let you push more flow. (3) implies (1) by weak duality. For (2) implies (3), take S as the vertices reachable from s in the residual graph. Every arc from S to T is saturated and every arc from T to S empty, so the two terms in Step 1 become c(S, T) and 0.

One subtlety: the proof assumes a maximum flow exists. With irrational capacities, Ford-Fulkerson with an unlucky path choice may never stop, and can converge below the maximum. The theorem still holds, since a maximum flow exists by compactness or by the LP view below, and Edmonds-Karp terminates for any real capacities.

Worked example: two minimum cuts

Take six vertices and eight arcs: s→a (3), s→b (10), a→t (10), a→c (1), b→c (4), b→d (5), c→t (4) and d→t (2). The maximum flow is 9: 3 units along s→a→t, 4 along s→b→c→t and 2 along s→b→d→t.

Now check it as a certificate rather than trusting it. The cut S = {s, b, d} has arcs s→a (3), b→c (4) and d→t (2) leaving it, so its capacity is 9, equal to the flow; both are optimal. But it is not the only minimum cut. S = {s, b, c, d} has arcs s→a (3), c→t (4) and d→t (2) leaving it, also 9. Here a→c crosses from T to S and is ignored. Enumerating all 16 cuts in the test script confirms these are the only two of capacity 9; the next smallest is 12.

Arcs s→a and d→t are in both cuts, so they are true bottlenecks. Arcs b→c and c→t are interchangeable: raising only one of them leaves the other cut at 9, so that upgrade alone gains nothing.

The linear programming view and integrality

Write max flow as a linear program: maximise the net flow out of s, subject to 0 ≤ f(e) ≤ c(e) and conservation. Its LP dual has a variable d(e) ≥ 0 per arc and a potential p(v) per vertex, with p(s) = 1, p(t) = 0 and d(u, v) ≥ p(u) − p(v), and minimises the sum of c(e)·d(e). A cut is the 0-1 case: p = 1 on S, 0 on T, d = 1 on arcs from S to T.

LP strong duality says the two optima are equal. The step that turns this into the max-flow min-cut theorem is that the dual has an optimal solution that is a cut. The constraint matrix is a vertex-arc incidence matrix, which is totally unimodular, so with integer data every vertex of either polytope is integral. This also gives the integrality theorem: if all capacities are integers, there is a maximum flow that is integral on every arc. Matchings and disjoint paths depend on that.

Consequences: Menger, Konig and Hall

Set every capacity to 1 and the theorem becomes a statement about paths. An integral flow of value k decomposes into k arc-disjoint s-t paths, and a cut of capacity k is a set of k arcs whose removal disconnects t from s. That is Menger's theorem: the maximum number of arc-disjoint s-t paths equals the minimum number of arcs whose removal separates s from t. For vertex-disjoint paths, split each vertex v into v_in→v_out with capacity 1.

In the test network s→a, s→b, s→c, a→d, b→d, b→e, c→e, d→t, e→t, the flow is 2: there are three arcs out of s, but every path must use d→t or e→t, and the minimal cut is exactly those two arcs.

Applied to a bipartite graph with unit arcs from s and to t, the same theorem gives König's theorem and Hall's condition; those derivations, with the matching algorithms, are in Bipartite Matching, in depth.

The structure of all minimum cuts

Minimum cuts are generally not unique, and they have a clean structure. If S1 and S2 are both minimum cuts, so are their union and intersection. So there is a smallest one, S_min, and a largest one, S_max, and every minimum cut S satisfies S_min ⊆ S ⊆ S_max. Given any maximum flow, both are easy to find. S_min is the set reachable from s in the residual graph. S_max is everything except the vertices that can reach t in the residual graph.

Two practical tests follow. The minimum cut is unique exactly when S_min = S_max. An arc (u, v) lies in every minimum cut exactly when u ∈ S_min and v ∉ S_max. Those arcs are the bottlenecks you must upgrade to raise the flow. The numbers on this page come from the code below, which a test script also checked against brute-force cut enumeration on 2,000 random networks.

from collections import deque, defaultdict

def max_flow(cap, s, t):
    # Edmonds-Karp on {u: {v: capacity}}. Returns (value, flow, residual).
    res = defaultdict(lambda: defaultdict(int))
    for u in cap:
        for v, c in cap[u].items():
            res[u][v] += c
            res[v][u] += 0                       # reverse arc exists
    value = 0
    while True:
        parent, q = {s: None}, deque([s])
        while q and t not in parent:
            u = q.popleft()
            for v, r in res[u].items():
                if r > 0 and v not in parent:
                    parent[v] = u
                    q.append(v)
        if t not in parent:
            break
        path, v = [], t
        while parent[v] is not None:
            path.append((parent[v], v))
            v = parent[v]
        push = min(res[u][v] for u, v in path)
        for u, v in path:
            res[u][v] -= push
            res[v][u] += push
        value += push
    # antiparallel arcs are netted, which leaves a valid flow of the same value
    flow = {u: {v: c - res[u][v] for v, c in cap[u].items() if c > res[u][v]} for u in cap}
    return value, flow, res

def reach(res, start):
    seen, stack = {start}, [start]
    while stack:
        u = stack.pop()
        for v, r in res[u].items():
            if r > 0 and v not in seen:
                seen.add(v)
                stack.append(v)
    return seen

def can_reach(res, target):                       # reach() on reversed arcs
    rev = defaultdict(dict)
    for u in list(res):
        for v, r in res[u].items():
            rev[v][u] = r
    return reach(rev, target)

def min_cut_structure(cap, s, t):
    value, flow, res = max_flow(cap, s, t)
    nodes = set(cap) | {v for u in cap for v in cap[u]}
    s_min = reach(res, s)
    s_max = nodes - can_reach(res, t)
    every = sorted((u, v) for u in cap for v in cap[u] if u in s_min and v not in s_max)
    return value, flow, s_min, s_max, every

Certificates: checking any answer in linear time

Weak duality makes verification cheaper than solving. Whatever produced a flow, say a hand-tuned Dinic implementation, you can check it in linear time: capacities respected, conservation holds, and the flow value equals the capacity of a supplied cut. If all three pass, the answer is optimal. If the solver is right, S_min from its residual graph is a valid cut to pass in.

def check_certificate(cap, flow, S, s, t):
    assert s in S and t not in S
    net = defaultdict(int)
    for u in flow:
        for v, f in flow[u].items():
            assert 0 <= f <= cap.get(u, {}).get(v, 0), f"capacity violated on {u}->{v}"
            net[u] -= f
            net[v] += f
    assert all(x in (s, t) or b == 0 for x, b in net.items()), "conservation violated"
    cut = sum(c for u in cap if u in S for v, c in cap[u].items() if v not in S)
    assert net[t] == cut, f"flow {net[t]} != cut {cut}: not optimal"
    return net[t]

It catches the bugs that matter: a reverse arc updated the wrong way, a cut read from a stale residual graph, or overflow in a capacity used as infinity.

Modelling with cuts: project selection

Many decision problems are naturally cut problems. Project selection is the classic one: each project earns a profit, each tool costs money, and a project can run only if all its tools are bought. Build a network with an arc from s to each project with capacity equal to its profit, an arc from each tool to t with capacity equal to its cost, and an infinite arc from each project to each tool it needs. A finite cut cannot separate a chosen project from its tools, so the source side of the minimum cut is the best plan, worth total profit minus the cut.

def best_projects(profit, cost, needs):
    cap, INF = defaultdict(dict), sum(profit.values()) + 1
    for p, gain in profit.items():
        cap["SRC"][p] = gain
        for tool in needs[p]:
            cap[p][tool] = INF
    for tool, c in cost.items():
        cap[tool]["SNK"] = c
    cap["SNK"] = {}
    cut, flow, res = max_flow(cap, "SRC", "SNK")
    S = reach(res, "SRC")
    return sum(profit.values()) - cut, sorted(x for x in S if x in profit), sorted(x for x in S if x in cost)

profit = {"search": 10, "recs": 7, "alerts": 3}
cost = {"gpu": 12, "kafka": 4, "featstore": 5}
needs = {"search": ["gpu", "featstore"], "recs": ["featstore", "kafka"], "alerts": ["kafka"]}
print(best_projects(profit, cost, needs))   # (1, ['alerts', 'recs'], ['featstore', 'kafka'])

The minimum cut is 19: the profit of search (10) is given up, and featstore (5) and kafka (4) are bought. Net profit is 20 − 19 = 1, which brute force over all eight project subsets confirms. Note what the cut captured: alerts loses money alone, but it shares kafka with recs, so together they are worth doing. The same construction, maximum weight closure, also schedules dependent tasks and selects features with prerequisites.

Failure modes

• Counting arcs from T to S in the cut. Only arcs from S to T count. Check with the certificate function.
• Vertex capacities and several sources or sinks. Split vertices into in and out halves, and add a super source and sink with arcs of infinite capacity.
• Infinity. Use a finite value larger than the sum of all finite capacities, and watch for overflow in fixed-width integers.
• Global minimum cut. The smallest cut separating any two vertices is a different problem. Use Stoer-Wagner, or Karger's randomised contraction, rather than one s-t cut.
• Assuming the cut is unique. If the answer feeds a decision, compute S_min and S_max and report the arcs in every minimum cut.

What to do next

1. Prove weak duality on paper for the worked example: pick three cuts and check each one is at least 9.
2. Run the code on the example, then raise b→c to 5 and predict the new maximum flow before running it again.
3. Add the certificate check to the tests of every flow solver you use, including library ones.
4. Model one real dependency problem in your work as project selection and compare the cut answer with your current plan.
5. Use Menger on your own network topology: compute arc-disjoint paths between two critical sites and list the arcs in every minimum cut.