Network Flow and Matchings

The question

A plant pumps water from a source $s$ to a reservoir $t$ through four pumping stations and nine one-way pipes. Each pipe has a capacity in units per hour:

s→a 4, s→b 9, s→c 6, a→b 6, a→c 5, a→t 2, b→d 8, c→b 3, d→t 9

The plant manager asks two questions. How much can reach $t$ per hour? And, because she will have to defend the number to the board: what proof would convince a sceptic that no routing does better?

A routing is easy to check; a claim that nothing better exists is harder. This module answers both at once: the algorithm that finds the best routing also hands you a certificate, a set of pipes whose capacities add up to the answer.

This module assumes you can run a depth-first search on a directed graph. Matching (the last part) assumes nothing more.

Pushing without undoing

The obvious approach: find a path from $s$ to $t$ whose pipes all have room, push as much as the pipe with the least room allows, and repeat until no such path is left.

Say it picks s a b d t first. The pipe $s\to a$ has only 4, so it pushes 4. Then s b d t: $b\to d$ has 4 of its 8 left, so it pushes 4 more. Now $s\to a$ and $b\to d$ are full, and every path from $s$ to $t$ runs through one of them. The approach stops at 8.

8 is not the answer. The 4 units on $a\to b$ are the waste: $a$ has its own pipe to $t$, with room 2, and $b\to d$ is the only way on from $b$. If 2 of those units went $a\to t$ instead, $b\to d$ would have room for 2 more units straight from $s$. But an approach that only adds flow can't move units it has already sent, so the first path's mistake is permanent.

Proving optimality by brute force is no better. As we'll see, every set of stations containing $s$ but not $t$ gives an upper bound: $2^4=16$ sets here, $2^{V-2}$ for $V$ vertices.

The model: flows and cuts

A flow assigns an amount $f(u,v)$ to every edge. It must obey two rules:

• capacity: $0\le f(u,v)\le c(u,v)$ on every edge;
• conservation: at every vertex other than $s$ and $t$, what flows in equals what flows out.

The value $|f|$ is the net amount leaving $s$. An $s$-$t$ cut is a set $S$ of vertices with $s\in S$ and $t\notin S$. Its capacity $c(S)$ is the total capacity of the edges leaving $S$. Edges that enter $S$ don't count.

from itertools import combinations

HOOK = {("s", "a"): 4, ("s", "b"): 9, ("s", "c"): 6,
        ("a", "b"): 6, ("a", "c"): 5, ("a", "t"): 2,
        ("b", "d"): 8, ("c", "b"): 3, ("d", "t"): 9}
assert {v for e in HOOK for v in e} - {"s", "t"} == set("abcd")
assert len(HOOK) == 9   # four pumping stations, nine pipes

def cut_capacity(cap, S):
    """Capacity of the edges leaving S; entering edges don't count."""
    return sum(c for (u, v), c in cap.items()
               if u in S and v not in S)

def value_of(cap, flow, s="s", t="t"):
    """The flow's value, after checking capacity and conservation."""
    net = {}
    for (u, v), c in cap.items():
        f = flow.get((u, v), 0)
        assert 0 <= f <= c, f"{u}->{v} carries {f} of {c}"
        net[u] = net.get(u, 0) - f
        net[v] = net.get(v, 0) + f
    for v, d in net.items():
        assert v in (s, t) or d == 0, f"not conserved at {v}"
    return -net[s]

sides = [{"s", *more} for r in range(5)
         for more in combinations("abcd", r)]
cuts = sorted((cut_capacity(HOOK, S), "".join(sorted(S)))
              for S in sides)
assert len(cuts) == 16 and cuts[0] == (10, "abcs") and cuts[1][0] > 10
assert cut_capacity(HOOK, {"s"}) == 19
assert cut_capacity(HOOK, set("sabcd")) == 11

STUCK = {("s", "a"): 4, ("a", "b"): 4, ("s", "b"): 4,
         ("b", "d"): 8, ("d", "t"): 8}
assert value_of(HOOK, STUCK) == 8

The smallest of the 16 cuts is $S=\{s,a,b,c\}$, with capacity 10. The obvious cuts are worse: $\{s\}$ has $4+9+6=19$, and everything but $t$ has $2+9=11$.

Lemma (weak duality). For every flow $f$ and every cut $S$, $|f|=f(\text{out of }S)-f(\text{into }S)\le c(S)$.

Proof. Add up "out minus in" over the vertices of $S$. For $s$ it is $|f|$, and for every other vertex of $S$ it is 0 by conservation, so the total is $|f|$. In that sum, an edge with both ends in $S$ appears once with $+$ and once with $-$ and cancels. What remains is the flow on edges leaving $S$ minus the flow on edges entering $S$. The first is at most $c(S)$ by the capacity rule, and the second is at least 0. $◻$

So every cut is an upper bound on every flow. If we ever hold a flow and a cut with $|f|=c(S)$, both are optimal, and the cut is the certificate the manager wants.

assert cut_capacity(HOOK, {"s", "b"}) == 18
entering = HOOK[("a", "b")] + HOOK[("c", "b")]
assert cut_capacity(HOOK, {"s", "b"}) + entering == 27

Taking flow back: the residual graph

The fix for the stuck approach is to let a later path cancel flow an earlier path sent. Given a flow $f$, the residual graph $G_f$ has, for every edge $u\to v$:

• a forward arc $u\to v$ with room $c(u,v)-f(u,v)$: how much more can be sent;
• a reverse arc $v\to u$ with room $f(u,v)$: how much can be taken back.

An augmenting path is a path from $s$ to $t$ in $G_f$ using only arcs with room above 0. Its bottleneck $b$ is the least room on it. To push $b$ along it, add $b$ to the flow on each forward arc's edge and subtract $b$ from the edge of each reverse arc.

Lemma (pushing keeps a flow). After a push the flow still obeys both rules, and its value has grown by $b$. Proof. A forward arc had room at least $b$, so its edge stays within capacity. A reverse arc's edge carried at least $b$, so it stays at 0 or more. Every vertex inside the path has one arc in and one arc out. Whatever the directions, the changes at that vertex cancel: $+b$ in and $+b$ out along two forward arcs; $-b$ out and $-b$ in along two reverse arcs; and $+b$ in and $-b$ in, or $+b$ out and $-b$ out, when the arcs are mixed. The first arc leaves $s$ and adds $b$ to the net outflow of $s$. $◻$

Ford–Fulkerson is this loop. Start with the zero flow. While $G_f$ has an augmenting path, push its bottleneck along it.

Ford–Fulkerson on the pipeline

The paths depend on how the search chooses, so we fix a rule: depth-first search, trying each vertex's residual neighbours in sorted order, never entering a vertex twice.

From $s$ the first neighbour is $a$, from $a$ it is $b$, from $b$ it is $d$, and then $t$. The search finds s a b d t with bottleneck 4, the same first move as before. Now look at the residual graph:

From $s$ the search tries $a$ first, but $s\to a$ is full, so it goes to $b$. From $b$ the first neighbour is $a$, and the arc $b\to a$ has room 4: it is the reverse of $a\to b$, which carries 4. From $a$ it tries $b$ (already seen), then $c$. Every arc with room out of $c$ leads back to a vertex already seen, so the search backs up to $a$, skips $s$, and takes $a\to t$. The path is s b a t, with rooms 9, 4 and 2, so the bottleneck is 2.

Pushing 2 along $b\to a$ subtracts 2 from $a\to b$. Two of the four units that went $a\to b$ now leave $a$ by $a\to t$ instead, which is exactly the correction the stuck approach couldn't make.

The third search finds s b d t with bottleneck 4, since $b\to d$ has room 4 again. The value is now $4+2+4=10$. The fourth search fails.

F1 = {("s", "a"): 4, ("a", "b"): 4, ("b", "d"): 4, ("d", "t"): 4}
F2 = {("s", "a"): 4, ("a", "b"): 2, ("a", "t"): 2,
      ("s", "b"): 2, ("b", "d"): 4, ("d", "t"): 4}
F3 = {("s", "a"): 4, ("a", "b"): 2, ("a", "t"): 2,
      ("s", "b"): 6, ("b", "d"): 8, ("d", "t"): 8}
assert [value_of(HOOK, f) for f in (F1, F2, F3)] == [4, 6, 10]
assert F1[("a", "b")] - F2[("a", "b")] == 2   # 2 units taken back

Why it stops at the maximum

Proof. (1) ⇒ (2): an augmenting path would raise the value by its bottleneck, which is positive. (3) ⇒ (1): by weak duality no flow exceeds $c(S)$, and $f$ reaches it.

(2) ⇒ (3) is the heart of it. Let $S$ be the set of vertices reachable from $s$ in $G_f$. Then $s\in S$, and $t\notin S$ because there is no augmenting path, so $S$ is a cut. Take any edge $u\to v$ leaving $S$. If it had room, its forward arc would make $v$ reachable, so it is full: $f(u,v)=c(u,v)$. Take any edge $v\to u$ entering $S$ (with $u$ in $S$). If it carried any flow, its reverse arc $u\to v$ would have room and make $v$ reachable, so it carries zero. By weak duality,

$$|f|=f(\text{out of }S)-f(\text{into }S)=c(S)-0=c(S).◻$$

The step not to skip is the one about entering edges. Without reverse arcs, a stuck flow can have flow on an edge entering the reachable set, and then $|f|<c(S)$. The stuck flow of 8 is such a case. From $s$, following edges with room, you reach $b$ and $c$, so $S=\{s,b,c\}$, with capacity $4+8=12$. The edge $a\to b$ enters $S$ and carries 4, and $8=12-4$. Those 4 units are exactly what a reverse arc would let the search take back.

The certificate for the manager is the final picture. The pipes $a\to t$ and $b\to d$ are full and together hold 10. Everything that leaves $\{s,a,b,c\}$ must use one of them, so no routing gets more than 10 through.

S = {"s", "a", "b", "c"}
leaving = [e for e in HOOK if e[0] in S and e[1] not in S]
entering = [e for e in HOOK if e[0] not in S and e[1] in S]
assert all(F3.get(e, 0) == HOOK[e] for e in leaving)      # full
assert all(F3.get(e, 0) == 0 for e in entering)           # empty
assert cut_capacity(HOOK, S) == value_of(HOOK, F3) == 10

T = {"s", "b", "c"}     # reachable in the stuck flow of 8
assert cut_capacity(HOOK, T) == 12
into_T = [e for e in HOOK if e[0] not in T and e[1] in T]
assert sum(STUCK.get(e, 0) for e in into_T) == 4

Cost and integrality

We count residual arcs inspected: each time a search looks at an arc, that is one step. A graph search inspects each of the $2E$ residual arcs at most once, so one search costs $O(V+E)$.

Theorem (integrality). If every capacity is an integer, every flow Ford–Fulkerson holds is integral: every edge carries an integer. Proof: by induction over the pushes. The zero flow is integral. If the flow is integral, every room is an integer, so the bottleneck is too, and the flow after the push is integral again. $◻$

So every bottleneck is at least 1, and each push raises the value by at least 1. The value can never pass $|f^{*}|$, the maximum, so there are at most $|f^{*}|$ successful searches plus the one that fails: Ford–Fulkerson terminates, and it ends with an integral maximum flow. The worst-case cost is

$$O((|f^{*}|+1)·E)=O(|f^{*}|·E)$$

for a connected network with $|f^{*}|\ge 1$. This bound depends on the numbers in the input, not just its size. Multiply every capacity by a million and the bound grows a millionfold, though the input is barely longer. Module 12 builds a network where a bad choice of paths really does take that long, and gives rules for choosing paths whose cost doesn't depend on the capacities. With irrational capacities it can be worse: a badly chosen sequence of paths need not terminate at all, and its values can even converge to a number below the maximum (stated here, not shown). Rational capacities are safe: multiply them all by a common denominator and they become integers.

Integrality has a second use, bigger than the running time: an integer maximum flow always exists when the capacities are integers. Other maximum flows may split units into fractions, but you never need them.

Matching as flow

Five people and five jobs. Each person can do some of the jobs:

(0,0) (0,2) (1,1) (1,3) (1,4) (2,0) (2,1) (2,4) (3,0) (4,4)

A matching is a set of these pairs in which nobody appears twice. What is the largest one?

The obvious method: go through the people in order and give each the first job on their list that is still free. It gives $(0,0)$, $(1,1)$ and $(2,4)$. Then person 3 wants only job 0, which is taken, and person 4 wants only job 4, also taken. It stops at 3.

The reduction: add a source $s$ with an edge of capacity 1 to every person, an edge of capacity 1 from person $x$ to job $y$ for every allowed pair, and an edge of capacity 1 from every job to a sink $t$. In an integral flow, each person receives at most one unit and so sends it along at most one pair. Each job passes on at most one unit, so it is used at most once. The pairs carrying a unit form a matching whose size is the flow's value, and every matching gives such a flow. By integrality, a maximum flow can be taken integral, so the maximum flow is the maximum matching.

On this network, once the greedy pairs carry flow, an augmenting path for person 3 is $s\to P_3\to J_0$, then back along the reverse arc $J_0\to P_0$, then $P_0\to J_2\to t$. Pushing along it takes job 0 from person 0 and moves person 0 to job 2. That is the reverse arc again: a later choice undoes an earlier one. One more augmenting path, for person 4, moves person 2 from job 4 to job 1 and person 1 from job 1 to job 3. The maximum matching has all five pairs, $(0,2)(1,3)(2,1)(3,0)(4,4)$. It is also the only one, since persons 3 and 4 each have a single allowed job, which then forces the rest: person 0 to job 2, person 2 to job 1 and person 1 to job 3.

from itertools import permutations

PAIRS = [(0, 0), (0, 2), (1, 1), (1, 3), (1, 4),
         (2, 0), (2, 1), (2, 4), (3, 0), (4, 4)]
used, greedy = set(), []
for x in range(5):
    for p, y in PAIRS:
        if p == x and y not in used:
            used.add(y)
            greedy.append((x, y))
            break
assert greedy == [(0, 0), (1, 1), (2, 4)]
perfect = [list(enumerate(jobs)) for jobs in permutations(range(5))
           if all(pair in PAIRS for pair in enumerate(jobs))]
assert perfect == [[(0, 2), (1, 3), (2, 1), (3, 0), (4, 4)]]
forced = {3: 0, 4: 4}                  # the only job each of them may take
for x in (0, 2, 1):                    # then each of these has one free job left
    free = [y for p, y in PAIRS if p == x and y not in forced.values()]
    assert len(free) == 1
    forced[x] = free[0]
assert sorted(forced.items()) == perfect[0]

With left side $L$, right side $R$ and $E$ allowed pairs, the network has $E+|L|+|R|$ edges. The maximum is at most $|L|$, so there are at most $|L|$ augmentations: $O(|L|·(E+|L|+|R|))$ in the worst case, which is $O(|L|·E)$ when every person and every job has at least one allowed pair. Compare trying every subset of the pairs.

Measure the claim

The bound says at most $(|f^{*}|+1)·2E$ arc inspections. Here is what the course's rule (depth first, sorted neighbours) actually inspects on matching networks with $n$ people, $n$ jobs and up to 4 random allowed jobs per person, with every capacity 1:

Augmentations equal $|f^{*}|$ exactly: with unit capacities every push moves one unit. The inspections stay far below the bound because a successful search stops as soon as it reaches $t$, often after a few steps. That is a measurement on these instances, not a guarantee. The bound is a worst case, and module 12 builds a small network on which a bad choice of paths needs thousands of augmentations.

A problem that looks different

Two data centres are joined by a mesh of cables through a dozen relay rooms. An attacker wants to cut as few cables as possible to disconnect them. An engineer wants as many routes as possible between them, no two sharing a cable, so that one cut cable never takes down two routes. Why might those two numbers always be equal? Nothing here mentions water, and the lab's last problem is a different one.

Practise

In the lab you write the push that can take flow back and watch every frame stay a valid flow; predict, then trace, the paths a search finds on a new network and read the certificate off the last one; write maximum flow with its certificate and use it for matching; count the arcs the searches inspect against the bound; and solve a staffing problem that doesn't say what it is.

Recap

You can now: check a flow's capacity and conservation rules and a cut's capacity; build the residual graph and push along a path that takes flow back; prove that maximum flow equals minimum cut, reading the cut off the final residual graph; and reduce matching to flow using integrality.

Invariant: Ford–Fulkerson always holds a valid flow. When no augmenting path is left, the edges leaving the reachable set are full and the edges entering it are empty, so the value equals that cut's capacity.

Complexity achieved: $O(|f^{*}|·E)$ worst case with integer capacities, and $O(|L|·E)$ for bipartite matching with $E$ allowed pairs. Certifying optimality by brute force means trying $2^{V-2}$ cuts.

Failure mode: no reverse arcs. The search stops at a flow that is not maximum (8 instead of 10 here), and nothing in the output warns you.

In real software: SciPy's scipy.sparse.csgraph.maximum_flow offers method='edmonds_karp' and method='dinic', and maximum_bipartite_matching computes matchings with Hopcroft–Karp. NetworkX's minimum_cut returns the cut value together with the two sides of the cut.

Retrieval (module 08): after the last search you need the set of vertices reachable from $s$ in the residual graph. Could union-find compute it?

Check yourself

1. When no augmenting path is left, why is the set of vertices reachable from $s$ a minimum cut? Include the edges that enter it.
2. Change the capacity of $b\to d$ to 8.5 and leave the rest alone. What is the maximum flow, and does the integrality theorem still apply?
3. On the pipeline, compare the approach that never takes flow back with Ford–Fulkerson. Where exactly does the first get stuck, and which residual arc frees it?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.