Network flows: max-flow min-cut and Menger’s theorem

How much oil can a pipeline network deliver from a field to a port, how many trains per day can a rail network carry between two cities, how much data can flow from a server to a client? Each question asks for a maximum flow through a network whose links have limited capacity. The theory of network flows, created by Lester Ford and Delbert Fulkerson in the 1950s, answers it with an algorithm and a duality theorem: the largest flow equals the smallest cut. The same theorem, applied to suitable networks, proves König's theorem of lesson 10 and Menger's theorem on disjoint paths, making it one of the great unifying results of combinatorics.

Networks and flows

A network is a directed graph with two distinguished vertices, a source \(s\) and a sink \(t\), and a capacity \(c(u, v) \ge 0\) on each arc. A flow assigns to each arc a number \(f(u, v)\) with \(0 \le f(u, v) \le c(u, v)\), the capacity constraint, such that at every vertex other than \(s\) and \(t\) the total flow in equals the total flow out, the conservation law. The value of the flow, \(|f|\), is the net flow out of \(s\), which by conservation equals the net flow into \(t\).

An \(s\)–\(t\) cut is a partition of the vertices into a set \(S\) containing \(s\) and its complement \(\bar{S}\) containing \(t\). Its capacity \(c(S, \bar{S})\) is the total capacity of arcs from \(S\) to \(\bar{S}\); arcs from \(\bar{S}\) back to \(S\) do not count.

Lemma (weak duality). For every flow \(f\) and every cut \((S, \bar{S})\), \[|f| = \sum_{u \in S, v \in \bar{S}}f(u, v) - \sum_{u \in \bar{S}, v \in S}f(u, v) \le c(S, \bar{S}).\]

Proof. Sum the conservation equations, out-flow minus in-flow, over all vertices of \(S\). Only \(s\) contributes a nonzero amount, namely \(|f|\). On the other hand, every arc with both ends in \(S\) appears once with each sign and cancels, leaving the flow on arcs from \(S\) to \(\bar{S}\) minus the flow on arcs from \(\bar{S}\) to \(S\). The first sum is at most \(c(S, \bar{S})\) and the second is at least 0.

So every cut gives an upper bound on every flow. If we ever find a flow and a cut with equal value, both are optimal: the cut certifies that the flow cannot be improved.

Residual networks and augmenting paths

Given a flow \(f\), the residual capacity of an arc \(uv\) is \(c(u, v) - f(u, v)\), the room left, and the residual network also contains a reverse arc \(vu\) with residual capacity \(f(u, v)\), representing the option of canceling flow already sent. An augmenting path is a directed path from \(s\) to \(t\) in the residual network using only arcs of positive residual capacity. If its smallest residual capacity is \(b\), pushing \(b\) units along it, increasing flow on forward arcs and decreasing it on reverse ones, gives a valid flow of value \(|f| + b\).

Theorem (max-flow min-cut; Ford and Fulkerson, 1956). In every network, the maximum value of an \(s\)–\(t\) flow equals the minimum capacity of an \(s\)–\(t\) cut. Moreover, a flow is maximum if and only if its residual network has no augmenting path.

Proof. If an augmenting path exists, the flow is not maximum. Suppose there is none, and let \(S\) be the set of vertices reachable from \(s\) in the residual network; then \(t \notin S\). Every arc \(uv\) from \(S\) to \(\bar{S}\) is saturated, \(f(u, v) = c(u, v)\), since otherwise \(v\) would be reachable. Every arc \(vu\) from \(\bar{S}\) to \(S\) carries no flow, since otherwise the reverse residual arc \(uv\) would make \(v\) reachable. By the formula in the weak duality lemma, \(|f| = c(S, \bar{S})\). So this flow attains the cut bound and is maximum, and this cut is minimum. A maximum flow exists because flows form a closed bounded set and the value is continuous, which completes the proof of equality.

In the figure the flow has value \(9 + 8 = 17\). The vertices reachable from \(s\) in the residual network are \(s\), \(a\), \(b\) and \(d\); the arcs leaving this set, \(ac\), \(dc\) and \(dt\), have capacities \(5 + 3 + 9 = 17\). No better flow is possible, because everything must cross those three arcs.

Integrality. If all capacities are integers, the Ford–Fulkerson method, starting from the zero flow, keeps every flow value an integer, since each bottleneck \(b\) is an integer. It increases the value by at least 1 each time, so it terminates, and there is a maximum flow that is integral on every arc. This integrality theorem is what turns flows into a tool for combinatorics, where we want whole edges, not fractions.

Choosing augmenting paths well

With badly chosen paths the method can be slow: in a network with capacities of a million on four arcs and 1 on a cross arc, alternating augmenting paths through the cross arc takes two million steps. With irrational capacities Ford and Fulkerson gave an example where the method never terminates and converges to a value below the maximum. Jack Edmonds and Richard Karp (1972) and Yefim Dinitz (1970) independently showed that always choosing a shortest augmenting path, found by breadth-first search, guarantees at most \(VE/2\) augmentations, for a total running time of \(O(VE^2)\). Decades of improvements followed, and in 2022 Li Chen, Rasmus Kyng, Yang Liu, Richard Peng, Maximilian Probst Gutenberg and Sushant Sachdeva announced an algorithm running in almost linear time, \(E^{1 + o(1)}\).

The problem has a Cold War history. In 1955 T. E. Harris and F. S. Ross wrote a classified report for the US Air Force modeling the Soviet and Eastern European rail network with 44 regions and 105 links, and computing its minimum cut, the cheapest set of links to interdict. Their work prompted Ford and Fulkerson's research; the report was declassified in 1999. A. N. Tolstoi had already studied transportation flows on Soviet railways in 1930.

Matchings from flows

Given a bipartite graph with sides \(X\) and \(Y\), build a network: a source \(s\) with an arc of capacity 1 to each \(x \in X\), an arc of capacity 1 from each \(y \in Y\) to a sink \(t\), and an arc from \(x\) to \(y\) for each edge, with capacity 1 (or infinity). By integrality, a maximum flow is integral, and the arcs from \(X\) to \(Y\) carrying flow form a matching of the same size. So maximum matching equals maximum flow.

König from max-flow min-cut. Give the middle arcs infinite capacity. A finite cut \((S, \bar{S})\) cannot have an arc \(xy\) with \(x \in S\), \(y \in \bar{S}\). So its capacity counts the vertices of \(X\) not in \(S\) and the vertices of \(Y\) in \(S\), and these together touch every edge: an edge \(xy\) with \(x \in S\) has \(y \in S\). Hence every finite cut gives a vertex cover of the same size, and conversely every vertex cover gives such a cut. So maximum matching equals minimum vertex cover.

Menger's theorem

Paths between two vertices are edge-disjoint if they share no edge, and internally disjoint if they share no vertex other than their ends. If removing \(k\) edges separates \(u\) from \(v\), there can be at most \(k\) edge-disjoint \(u\)–\(v\) paths, since each must use a removed edge. Karl Menger proved in 1927 that this bound is always attained.

Theorem (Menger). Let \(u\) and \(v\) be vertices of a graph. The maximum number of edge-disjoint \(u\)–\(v\) paths equals the minimum number of edges whose removal separates \(u\) from \(v\). If \(u\) and \(v\) are not adjacent, the maximum number of internally disjoint \(u\)–\(v\) paths equals the minimum number of vertices, other than \(u\) and \(v\), whose removal separates them.

Proof. For the edge version, replace each edge by two opposite arcs of capacity 1 and take \(s = u\), \(t = v\). An integral maximum flow of value \(k\) decomposes into \(k\) arc-disjoint paths, after canceling any pair of opposite arcs both carrying flow; a minimum cut of capacity \(k\) is a set of \(k\) edges separating \(u\) from \(v\). Max-flow min-cut gives equality. For the vertex version, split each vertex \(w \ne u, v\) into \(w_{\text{in}}\) and \(w_{\text{out}}\) joined by an arc of capacity 1, and send every arc entering \(w\) to \(w_{\text{in}}\) and every arc leaving \(w\) from \(w_{\text{out}}\), with infinite capacity. Disjoint paths in the original graph become arc-disjoint paths through the unit arcs, and a finite cut must consist of unit arcs, that is, vertices.

Corollary (Whitney, 1932). A graph with at least \(k + 1\) vertices is \(k\)-connected if and only if every two vertices are joined by \(k\) internally disjoint paths, and \(k\)-edge-connected if and only if every two vertices are joined by \(k\) edge-disjoint paths. This is the global form of Menger's theorem, and it explains why connectivity measures robustness: \(k\)-connected networks keep working after any \(k - 1\) failures, because every pair still has a surviving route.

More applications

Many problems that do not look like flows reduce to minimum cuts. In project selection, projects have profits and some require tools with costs; the most profitable choice is found by a minimum cut in a network with arcs from \(s\) to projects (profits), from tools to \(t\) (costs), and infinite arcs from each project to the tools it needs. In image segmentation, each pixel is joined to its neighbors with capacities reflecting similarity, and a minimum cut separates foreground from background. In sports elimination, a flow network decides whether a team can still finish first given the remaining schedule, a method popularized by Schwartz in 1966. Flows with costs, or with lower bounds and demands, extend the theory to transportation and scheduling problems solved daily by logistics companies.

from collections import deque
from itertools import combinations

def max_flow(cap, s, t):
    flow = {e: 0 for e in cap}
    nodes = sorted({u for u, v in cap} | {v for u, v in cap}, key=str)
    res = lambda u, v: cap.get((u, v), 0) - flow.get((u, v), 0) + flow.get((v, u), 0)
    value, rounds = 0, 0
    while True:
        parent = {s: None}; q = deque([s])
        while q and t not in parent:
            u = q.popleft()
            for v in nodes:
                if v not in parent and res(u, v) > 0:
                    parent[v] = u; q.append(v)
        if t not in parent:
            return value, flow, set(parent), rounds
        path, v = [], t
        while parent[v] is not None:
            path.append((parent[v], v)); v = parent[v]
        b = min(res(u, v) for u, v in path)
        for u, v in path:
            back = min(b, flow.get((v, u), 0))
            if back:
                flow[(v, u)] -= back
            if b - back:
                flow[(u, v)] = flow.get((u, v), 0) + b - back
        value += b; rounds += 1

cap = {("s", "a"): 10, ("s", "b"): 8, ("a", "b"): 2, ("a", "c"): 5, ("b", "d"): 10,
       ("a", "d"): 4, ("d", "c"): 3, ("c", "t"): 10, ("d", "t"): 9}
value, flow, S, rounds = max_flow(cap, "s", "t")
cut = [(u, v) for (u, v) in cap if u in S and v not in S]
print("max flow:", value, "after", rounds, "augmentations")
print("min cut S =", sorted(S), " arcs", cut, " capacity", sum(cap[e] for e in cut))
print("flow on arcs:", {f"{u}{v}": f for (u, v), f in sorted(flow.items()) if f})

def brute_min_cut(cap, s, t):
    others = sorted(({u for u, v in cap} | {v for u, v in cap}) - {s, t})
    best = None
    for r in range(len(others) + 1):
        for extra in combinations(others, r):
            side = {s, *extra}
            c = sum(w for (u, v), w in cap.items() if u in side and v not in side)
            best = c if best is None else min(best, c)
    return best
print("brute force minimum over all", 2 ** 4, "cuts:", brute_min_cut(cap, "s", "t"))

can_do = {"a": [1, 2], "b": [2], "c": [2, 3], "d": [2, 3], "e": [3, 4, 5]}
net = {("s", w): 1 for w in can_do}
net.update({(w, j): 1 for w, js in can_do.items() for j in js})
net.update({(j, "t"): 1 for j in {j for js in can_do.values() for j in js}})
v, f, _, _ = max_flow(net, "s", "t")
print("matching via flow:", v, sorted((w, j) for (w, j), x in f.items() if x and w in can_do and j != "t"))

def disjoint_paths(edges, u, v):
    cap = {}
    for a, b in edges:
        cap[(a, b)] = 1; cap[(b, a)] = 1
    return max_flow(cap, u, v)[0]

def min_edge_cut(edges, u, v):
    for k in range(len(edges) + 1):
        for removed in combinations(edges, k):
            rest = [e for e in edges if e not in removed]
            reach, stack = {u}, [u]
            while stack:
                x = stack.pop()
                for a, b in rest:
                    for p, q in ((a, b), (b, a)):
                        if p == x and q not in reach:
                            reach.add(q); stack.append(q)
            if v not in reach:
                return k

cube = [(a, b) for a in range(8) for b in range(8) if a < b and bin(a ^ b).count("1") == 1]
print("cube Q3: edge-disjoint paths 0 to 7:", disjoint_paths(cube, 0, 7), " min edge cut:", min_edge_cut(cube, 0, 7))
bowtie = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2), (0, 5), (5, 4)]
print("bowtie with extra route: edge-disjoint paths 0 to 3:", disjoint_paths(bowtie, 0, 3), " min edge cut:", min_edge_cut(bowtie, 0, 3))

def vertex_disjoint(edges, u, v):
    cap = {}
    nodes = {x for e in edges for x in e}
    for w in nodes - {u, v}:
        cap[(("in", w), ("out", w))] = 1
    node_in = lambda x: x if x in (u, v) else ("in", x)
    node_out = lambda x: x if x in (u, v) else ("out", x)
    for a, b in edges:
        cap[(node_out(a), node_in(b))] = 10 ** 6
        cap[(node_out(b), node_in(a))] = 10 ** 6
    return max_flow(cap, u, v)[0]
petersen = [(i, (i + 1) % 5) for i in range(5)] + [(5 + i, 5 + (i + 2) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
print("Petersen: internally disjoint paths between nonadjacent 0 and 2:", vertex_disjoint(petersen, 0, 2))

max flow: 17 after 4 augmentations
min cut S = ['a', 'b', 'd', 's']  arcs [('a', 'c'), ('d', 'c'), ('d', 't')]  capacity 17
flow on arcs: {'ac': 5, 'ad': 4, 'bd': 8, 'ct': 8, 'dc': 3, 'dt': 9, 'sa': 9, 'sb': 8}
brute force minimum over all 16 cuts: 17
matching via flow: 4 [('a', 1), ('b', 2), ('c', 3), ('e', 4)]
cube Q3: edge-disjoint paths 0 to 7: 3  min edge cut: 3
bowtie with extra route: edge-disjoint paths 0 to 3: 2  min edge cut: 2
Petersen: internally disjoint paths between nonadjacent 0 and 2: 3

Breadth-first augmentation finds the flow of value 17 in the figure and the cut that certifies it, and checking all 16 cuts by brute force confirms that 17 is the minimum. The worker problem of lesson 10 becomes a unit-capacity network whose maximum flow is the maximum matching. In the cube, three edge-disjoint paths join opposite corners and three edges must be removed to separate them, and the Petersen graph, which is 3-connected, has three internally disjoint paths between nonadjacent vertices, as Menger's theorem predicts.