Polynomial-Time Max Flow

Four vertices, fourteen thousand augmentations

Here is a network with four vertices and five edges. Capacities are in units per second:

s→a 7000, s→b 9000, a→t 9000, b→t 7000, a→b 1

The maximum flow is 14,000, and you can see it without any algorithm. Send 7,000 along s a t and 7,000 along s b t. The cut $\{s,b\}$ has capacity $7000+7000=14,000$, and by the max-flow min-cut theorem of module 11 nothing can do better. Two augmenting paths are enough.

Module 11's Ford–Fulkerson method pushes along any augmenting path until none is left. Which path matters enormously: one plausible rule takes 14,000 augmentations here, and two other rules make the running time depend only on the size of the graph, never on the capacities.

This module assumes module 11: residual graphs, augmenting paths, and the max-flow min-cut theorem. It also uses breadth-first search (BFS), which labels every vertex with its distance in arcs from the start.

The naive rule and where it wastes work

A rule that sounds reasonable: take the augmenting path with the most arcs. A depth-first search tends to find such paths.

On this network the longest path is s a b t, through the rung $a\to b$. Its bottleneck is the rung's capacity, 1. After that push the rung is full, but the residual graph now has a reverse arc $b\to a$ with room 1, and the longest path is s b a t, which takes the unit back. Its bottleneck is 1 again. The two paths alternate, each carrying one unit, until $s\to a$ and $b\to t$ are full.

def residual(nodes, edges):
    """room[u][v]: residual capacity; every edge also gets its reverse arc."""
    room = {u: {} for u in nodes}
    for u, v, c in edges:
        room[u][v] = room[u].get(v, 0) + c
        room[v].setdefault(u, 0)
    return room

def augment(room, path):
    b = min(room[u][v] for u, v in zip(path, path[1:]))
    for u, v in zip(path, path[1:]):
        room[u][v] -= b
        room[v][u] += b
    return b

def paths_with_room(room, s, t):
    """Every simple s-t path whose arcs all have room, in sorted order.
    Exhaustive: fine for a handful of vertices, hopeless beyond."""
    out = []
    def extend(path):
        if path[-1] == t:
            out.append(list(path))
            return
        for v in sorted(room[path[-1]]):
            if v not in path and room[path[-1]][v] > 0:
                path.append(v)
                extend(path)
                path.pop()
    extend([s])
    return out

def run(nodes, edges, s, t, choose):
    room, value, pushes = residual(nodes, edges), 0, []
    while (options := paths_with_room(room, s, t)):
        path = choose(options)
        pushes.append(("".join(path), augment(room, path)))
        value += pushes[-1][1]
    return value, pushes, room

longest = lambda options: max(options, key=len)
shortest = lambda options: min(options, key=len)

def rung(k):
    return "sabt", [("s", "a", 7 * k), ("s", "b", 9 * k), ("a", "t", 9 * k),
                    ("b", "t", 7 * k), ("a", "b", 1)]

for k in (1, 10, 100, 1000):
    value, pushes, _ = run(*rung(k), "s", "t", longest)
    assert value == 14 * k and len(pushes) == 14 * k
    assert pushes[:2] == [("sabt", 1), ("sbat", 1)]
    value, pushes, _ = run(*rung(k), "s", "t", shortest)
    assert value == 14 * k and len(pushes) == 2

With capacities $7k$ and $9k$ the longest-path rule makes exactly $14k$ augmentations: 14, 140, 1,400 and 14,000 for $k=1,10,100,1000$. Always taking the path with the fewest arcs makes two, whatever $k$ is.

The waste is plain to see: every long path squeezes through the rung, so every push moves one unit. Module 11's bound, $O(|f^{*}|·E)$ with $|f^{*}|$ the maximum flow's value, is honest here and useless. The input is five numbers of at most 14 bits each. Multiply the capacities by 1,000 and the input grows by 10 bits per number, while the work grows a thousandfold. A running time that grows with the values in the input, rather than with its length, is called pseudo-polynomial. It is exponential in the number of bits.

The model: what we count

We count three things. An augmentation is one push along one path. A phase (in Dinic's algorithm, below) is one BFS followed by many pushes. An arc scan is one look at one residual arc, and it is the unit of time: a BFS or a DFS costs one scan per arc it looks at.

$V$ is the number of vertices and $E$ the number of edges; the residual graph has at most $2E$ arcs. A bound is strongly polynomial if it depends on $V$ and $E$ alone and not on the capacities. Everything proved below is a worst-case bound in that sense.

Shortest augmenting paths

Edmonds–Karp is Ford–Fulkerson with one rule: always augment along a path with the fewest arcs, found by BFS. On the rung network that gives s a t and s b t, and it stops.

A single example proves nothing, so here is a larger one, the network $D$:

s→a 7, s→c 5, a→b 9, a→c 6, a→d 4, a→e 5, b→c 8, b→e 4, c→d 9, d→t 4, e→t 7

Ties between equally short paths are broken by trying neighbours in alphabetical order. The first two augmentations are s a d t (bottleneck 4) and s a e t (bottleneck 3), both with 3 arcs. After them $s\to a$ is full, and no path of 3 or 4 arcs is left. The third augmentation has 5 arcs:

s c d a e t uses the arc $d\to a$, the reverse of $a\to d$, to take back 2 of the 4 units that went $a\to d\to t$ and send them on through $e$. The fourth augmentation, s c d a b e t, has 6 arcs. The flow is then 11, which equals the capacity of the cut "everything but $t$" ($4+7$), so it is maximum.

DN = "sabcdet"
DE = [("s", "a", 7), ("s", "c", 5), ("a", "b", 9), ("a", "c", 6), ("a", "d", 4),
      ("a", "e", 5), ("b", "c", 8), ("b", "e", 4), ("c", "d", 9), ("d", "t", 4),
      ("e", "t", 7)]

value, pushes, room = run(DN, DE, "s", "t", shortest)
assert pushes == [("sadt", 4), ("saet", 3), ("scdaet", 2), ("scdabet", 2)]
assert value == 11 == 4 + 7

The lengths went 3, 3, 5, 6. They never went down, and that is no accident.

(The lesson's code lists every path and picks the shortest. That is a stand-in, fine for seven vertices. The real algorithm finds the path with one BFS, and you write it in the lab.)

The invariant: distances never shrink

Let $d_f(v)$ be the BFS distance from $s$ to $v$ in the residual graph $G_f$, counting only arcs with room.

Proof. Suppose some vertex gets closer. Among those, take a $v$ whose new distance $d_{f^{\prime }}(v)$ is smallest. Let $u$ be the vertex before $v$ on a shortest $s\to v$ path in $G_{f^{\prime }}$, so $d_{f^{\prime }}(u)=d_{f^{\prime }}(v)-1$. Since $u$ is nearer than $v$ in $G_{f^{\prime }}$, the choice of $v$ means $u$ did not get closer: $d_{f^{\prime }}(u)\ge d_f(u)$. There are two cases for the arc $u\to v$.

• It already had room in $G_f$. Then BFS in $G_f$ gives $d_f(v)\le d_f(u)+1\le d_{f^{\prime }}(u)+1=d_{f^{\prime }}(v)$, so $v$ did not get closer after all.
• It had no room in $G_f$. Then the augmentation created its room, which happens only by pushing along the opposite arc $v\to u$. That arc was on a shortest path of $G_f$, so $d_f(u)=d_f(v)+1$. Then $d_{f^{\prime }}(v)=d_{f^{\prime }}(u)+1\ge d_f(u)+1=d_f(v)+2$: $v$ got farther away, not closer.

Both cases contradict the choice of $v$. $◻$

The step not to skip is the second case. New arcs appear only as reverses of arcs just used, and a shortest path climbs one level per arc, so every new arc points one level down. An arc that points down can't shorten anything.

def dist_from(room, s):
    """Fewest arcs from s to each vertex, over arcs with room (stand-in for BFS)."""
    best = {s: 0}
    def extend(path):
        for v in room[path[-1]]:
            if v not in path and room[path[-1]][v] > 0:
                if len(path) < best.get(v, len(path) + 1):
                    best[v] = len(path)
                extend(path + [v])
    extend([s])
    return best

room, seen = residual(DN, DE), []
while (options := paths_with_room(room, "s", "t")):
    seen.append(dist_from(room, "s"))
    augment(room, shortest(options))
seen.append(dist_from(room, "s"))
for before, after in zip(seen, seen[1:]):
    assert all(after.get(v, 99) >= before[v] for v in before)
assert seen[0] == {"s": 0, "a": 1, "c": 1, "b": 2, "d": 2, "e": 2, "t": 3}
assert seen[2] == {"s": 0, "c": 1, "d": 2, "a": 3, "b": 4, "e": 4, "t": 5}

Look at $a$: at distance 1 at the start and at distance 3 after the second push, once $s\to a$ is full and the only way in is $scda$.

Theorem (Edmonds–Karp). At most $VE$ augmentations, so $O(V{E}^2)$ time in the worst case, whatever the capacities.

Proof. Call a residual arc $u\to v$ critical in an augmentation if it is a bottleneck; the push removes all its room. At that moment it lies on a shortest path, so $d(v)=d(u)+1$. For it to be critical again it must first regain room, which needs a push along $v\to u$ on a shortest path, at a time when $d^{\prime }(u)=d^{\prime }(v)+1$. By the lemma $d^{\prime }(v)\ge d(v)$, so $d^{\prime }(u)\ge d(u)+2$. Between two critical moments of the same arc, the distance of its tail grows by at least 2. A distance is at most $V-2$ for the tail of an arc on a path to $t$, so each arc is critical at most $V/2$ times. There are at most $2E$ residual arcs, and every augmentation has a critical arc, so there are at most $2E·V/2=VE$ augmentations. Each is one BFS, $O(E)$. $◻$

Dinic: all the shortest paths at once

Edmonds–Karp spends a BFS on every augmentation, though on $D$ the first two found the same distances. Dinic's algorithm reuses one BFS for every path of the current length. Each phase does three things:

1. Run BFS from $s$ in $G_f$. The distance of $v$ is its level.
2. Keep only the arcs with room that climb exactly one level, $u\to v$ with $\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}(v)=\mathrm{l}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{l}(u)+1$. That subgraph is the level graph. Its $s\to t$ paths are exactly the shortest augmenting paths.
3. Push a blocking flow in the level graph: keep pushing along $s\to t$ paths of the level graph until every one of them has a full arc.

Stop when BFS no longer reaches $t$.

On $D$ the first level graph has four columns. Its blocking flow pushes 4 along s a d t and 3 along s a e t. Red arcs are the ones the blocking flow filled, green arcs still have room, and each number is the arc's room at the start of the phase:

Every $s\to t$ path in that picture now crosses a red arc, so the phase is over. The next BFS finds $t$ at level 5, not 3:

The arc $d\to a$ is the reverse arc from before, and here it climbs a level. The blocking flow pushes 2 and fills $a\to e$. The third phase has $t$ at level 6, a single path, and pushes 2 more:

Three phases, with $(d(s,t),\text{pushed})=(3,7),(5,2),(6,2)$. Here they push exactly Edmonds–Karp's four paths, grouped by length.

by_length = {}
for path, pushed in run(DN, DE, "s", "t", shortest)[1]:
    by_length[len(path) - 1] = by_length.get(len(path) - 1, 0) + pushed
assert list(by_length.items()) == [(3, 7), (5, 2), (6, 2)]

Lemma (a phase lengthens the shortest path). After a blocking flow, $d(s,t)$ is strictly larger.

Proof. Use the phase's levels $\ell$. Every arc with room before the phase goes up at most one level, because BFS would otherwise have given its head a smaller level. The pushes create new arcs only as reverses of level-graph arcs, and those go one level down. So after the phase, still no arc climbs more than one level. A path from $s$ (level 0) to $t$ (level $d$) therefore has at least $d$ arcs, and exactly $d$ only if every arc climbs one level. Such arcs are old level-graph arcs with room left, and a path made of them would be an $s\to t$ path in the level graph without a full arc. The blocking flow left none. So every path has more than $d$ arcs. $◻$

Since $d(s,t)$ grows every phase and is at most $V-1$, there are at most $V-1$ phases.

The cost of one phase. Finding the blocking flow is where care is needed. The pushes are found by depth-first searches from $s$ in the level graph. Each vertex keeps a current-arc pointer into its list of arcs. When an arc turns out useless (it is full, or the search behind it reached a dead end), the pointer moves past it and never comes back in this phase. The arc stays useless for the rest of the phase, because pushes only fill level-graph arcs and never add room to them.

So pointer moves total at most $2E$ per phase. Each successful search fills at least one arc, so there are at most $2E$ of them, and each walks at most $V$ arcs forward. A phase costs $O(VE)$, and Dinic's algorithm $O(V^{2}E)$ in the worst case. This is sketched, not fully proved: the pointer count is an amortized argument of the kind in module 07. Charge each pointer move to the arc it skips, and each arc can be skipped once.

Without the pointers the answers are still right, but every search can walk into the same dead ends again.

Unit capacities: $2\sqrt{E}$ phases

Many flow problems have every capacity equal to 1: disjoint routes, and matchings in module 11. Assume also that no two edges are antiparallel ($u\to v$ and $v\to u$). Then two things improve.

A phase costs $O(E)$. Every arc on a successful search has room 1, so the push fills all of them. The searches' forward steps then total at most $2E$, and so do the pointer moves.

Theorem. Dinic's algorithm uses at most $2\sqrt{E}$ phases on such a network, so $O(E^{3/2})$ time.

Proof. Look at the residual graph after any $k$ phases. By the phase lemma $d=d(s,t)\ge k+1$. For each $i=0,1,\dots ,d-1$ let $S_i$ be the vertices at level at most $i$. Each $S_i$ is a cut. An arc with room that leaves $S_i$ can't climb more than one level, so it goes from level exactly $i$ to level $i+1$. So the $d$ cuts use disjoint sets of arcs. With unit capacities and no antiparallel edges, each edge gives exactly one arc with room (forward if unused, reverse if used), $E$ in all. So some $S_i$ has at most $E/d$ arcs leaving it, and the flow still missing is at most $E/d<E/k$ by max-flow min-cut in the residual graph. Each further phase adds at least 1, so at most $E/k$ phases remain, and the total is at most $k+E/k$. Take $k=\sqrt{E}$. $◻$

Two further bounds are cited, not proved here. On unit-capacity graphs with no parallel edges the number of phases is also $O(V^{2/3})$ (Karzanov; Even and Tarjan), so Dinic runs in $O(E·min(V^{2/3},E^{1/2}))$. For bipartite matching, where every vertex other than $s$ and $t$ has only one unit to pass on, the same shape of argument gives $O(\sqrt{V})$ phases: after $\sqrt{V}$ phases the remaining augmenting paths are vertex-disjoint and each has more than $\sqrt{V}$ vertices, so fewer than $\sqrt{V}$ of them are left. That is the Hopcroft–Karp algorithm, $O(E\sqrt{V})$, sketched here.

Measure the claim

Dinic's algorithm on random unit-capacity networks with $E=4V$, where $s$ and $t$ are each joined to a fifth of the vertices (seed $451+V$):

On bipartite matching with $n$ vertices per side and 3 random partners each, the maximum matchings have 94, 947 and 4,711 pairs for $n=100,1000,5000$, found in 4, 7 and 9 phases. And Edmonds–Karp on random networks with capacities up to 100 needed 7, 8 and 29 augmentations for $V=20,40,80$ (64, 242 and 919 edges), against worst-case bounds $VE$ of 1,280, 9,680 and 73,520.

These are measurements on these instances, not theorems: random networks are easy, and the bounds are for the worst case. (The course's verification script computes these numbers.)

Which algorithm when?

Faster maximum-flow algorithms exist: push–relabel methods, and recent algorithms that run in almost linear time. They are beyond this module.

A problem that looks different

A company is choosing research projects. Each project earns a known profit, but needs some instruments, and each instrument costs money once, however many projects share it. Profits and costs run into the millions. Which projects should it choose? Somewhere in that question is a cut, and once you find it, you will want an algorithm whose running time doesn't depend on millions. The lab's last problem is a different one.

Practise

In the lab you build BFS levels and the level graph and watch every arc climb exactly one level; predict, then trace, Edmonds–Karp on a new network while the distances refuse to shrink, and count how badly the long-path rule does on a new rung network; write Dinic's algorithm with current-arc pointers, drawing a level graph per phase; count phases and arc scans on unit-capacity networks against $2\sqrt{E}$; and solve a dispatching problem that doesn't say what it is.

Recap

You can now: build a network on which a plausible path rule needs a number of augmentations proportional to the capacities; prove that shortest augmenting paths never get shorter and derive Edmonds–Karp's $O(V{E}^2)$; run Dinic's phases on level graphs and prove there are at most $V-1$; and prove the $2\sqrt{E}$ phase bound for unit capacities, knowing which bounds are only cited.

Invariant: under shortest-path augmentation no vertex's residual distance from $s$ ever decreases, and in Dinic's algorithm $d(s,t)$ strictly increases with every blocking flow.

Complexity achieved: Edmonds–Karp $O(V{E}^2)$ and Dinic $O(V^{2}E)$, whatever the capacities; $O(E^{3/2})$ for unit capacities (proved) and $O(E\sqrt{V})$ for bipartite matching (sketched), against Ford–Fulkerson's pseudo-polynomial $O(|f^{*}|·E)$.

Failure mode: a "Dinic" whose searches don't keep a current-arc pointer. It returns correct answers and re-explores the same dead ends in every search. A close second: finding paths by DFS and calling it Edmonds–Karp.

In real software: SciPy's scipy.sparse.csgraph.maximum_flow uses Dinic's algorithm by default (method='dinic') and offers method='edmonds_karp'; its maximum_bipartite_matching implements Hopcroft–Karp. NetworkX provides dinitz and edmonds_karp flow functions.

Retrieval (module 07): one Dinic phase may run hundreds of depth-first searches. Why do the pointer moves in a phase still total at most the number of arcs?

Check yourself

1. Prove that BFS distances in the residual graph never decrease under Edmonds–Karp. Which case of the proof needs the paths to be shortest?
2. Replace BFS by "any depth-first path" in Edmonds–Karp. Which bound survives? Give a concrete network.
3. On the rung network with capacities $7k$ and $9k$, how many BFS runs do Edmonds–Karp and Dinic's algorithm each make, and why does the rung never enter Dinic's level graph?

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.