Cut

Ford–Fulkerson is usually taught as a loop with a hole in it: while an augmenting path exists, push flow along it. Two things in that sentence are doing enormous work and neither of them looks like it is. The first is what counts as a path — the search is allowed to travel backwards along an edge that already carries flow, undoing a decision made twenty steps ago. The second is what happens when the loop ends, which is not “we gave up” but “we have constructed a proof”.

So this is a drawing of the residual graph with a switch on it. back-edges: off is the same algorithm with the same path search and the same loop, minus the single move that makes it correct. Everything below is the difference between those two runs.

The block

Four nodes, five edges of capacity 10, maximum flow 20: ten through u, ten through v. Pick the path s → u → v → t first — which a depth-first walk does, and which is not a mistake anyone would notice making — and the three edges it uses are now full. s → v is still open and v has nowhere to go. u → t is still open and nothing can reach u. The run stops at 10, which is exactly half.

The fix is not a better path rule. It is v → u, an edge that is not in the drawing, whose capacity is 10 because that is how much flow is currently sitting on u → v. The second augmenting path is s → v, then backwards up the middle, then u → t, and the net effect is to reroute the first push rather than add to it. Nothing was undone in the sense of being thrown away; the middle edge simply stops being used, and the two cheap routes it was blocking open up.

That is the entire idea. Everything else in max-flow is bookkeeping.

The switchback, and why “close enough” is the wrong intuition

The block costs you a factor of two, which is easy to file under heuristics are usually fine. So here is the same failure with the factor made as large as you like. Six independent routes s → xᵢ → yᵢ → t, every capacity 1, maximum flow 6 — and one switchback rung from each yᵢ back up to xᵢ₊₁.

A single depth-first walk threads every rung in one path: s → x₁ → y₁ → x₂ → y₂ → … → y₆ → t. Bottleneck 1. In spending that one unit it saturates all six of the xᵢ → yᵢ edges, which are the six routes. The forward-only run returns 1 of 6, and it is not a near miss, it is a sixth. At k = 12 it returns 1 of 12. The shortfall is not bounded by a percentage; it is bounded by the size of the graph.

Whose answer is it

The sharpest version of the claim is not about size at all. Shuffle the order the search considers edges in — nothing else, same graph, same capacities, same rule — and re-run 400 times:

The right-hand column is a lottery. The mesh returns eight different answers to the same question depending on which neighbour happened to be listed first. That is what the backward half-edge buys: not accuracy, well-definedness. With it, the number is a property of the network. Without it, the number is a property of your adjacency lists, and the program that computed it cannot tell you which.

As a control, every path rule here — shortest, first-found, widest, the adversary, and Dinic’s blocking flows — was run on all five instances and 200 random networks, 205 in total. All five rules agreed on the answer in every one.

The trap is that it usually works

Over 400 random layered networks, the forward-only run is already optimal on 342 of them. Its mean share of the maximum is 97.7%. If you shipped it you would be right 85% of the time and within a rounding error on average.

Its worst case in that sample is exactly half.

This is the uncomfortable shape of the thing: not a heuristic that fails loudly and gets replaced, but one that is nearly always right, is occasionally wrong by a factor you would never tolerate, and returns a bare integer either way.

The one-sided alarm

There is a test the forward-only run can perform on itself, and it is worth being precise about what it does and does not prove.

When it stops, look at the set S of nodes it can still reach. Every forward edge leaving S must be saturated, or it could have kept going. So the flow equals the capacity of that cut minus whatever flow crosses back into S — and that second term is exactly the amount it is leaving on the table. When it is zero, flow equals a cut’s capacity, and no flow can ever exceed any cut, so the run is provably finished.

Over 800 random networks:

Read both rows. A zero gap is a proof of optimality — 447 for 447, no exceptions, which is the min-cut theorem arriving empirically. And every one of the 91 suboptimal runs had a positive gap, so the test never missed. But 262 of the 353 alarms were raised on runs that were already optimal: a positive gap is a false alarm 74.2% of the time.

So the forward-only run can always tell when it is definitely finished, and can never tell when it is actually stuck. Which is the useless direction. The back-edge is not what detects the problem — it is the only thing that fixes one, and a detector with no repair attached is not worth much.

Same answer, different bill

Switch back-edges on and the answer is nailed down. What is still wide open is how long you take to get there, and the textbook statement of the algorithm says nothing about it at all — “find an augmenting path” is a hole the implementer fills in.

The rung: two fat sides of capacity 1000, one unit rung between them, maximum flow 2000.

The adversary is not cheating. It is the same loop, obeying the same specification, picking a legal augmenting path every time — the one that runs through the rung, which alternates direction and moves one unit per round. Scale every capacity by ten and the graph does not change at all, four nodes and five edges throughout, while the bill does:

That is the whole reason Edmonds–Karp is a named algorithm rather than a footnote: picking the shortest augmenting path replaces a bound that scales with the numbers written on the edges with one that scales with the graph. On the ten-node mesh the four rules take 8, 10, 5 and 12 augmentations — a real spread, and all four land on 20.

Worth saying plainly, though: over 300 random networks Edmonds–Karp’s O(VE) augmentation bound was never remotely approached. The worst instance used 6.5% of it, and the mean run took 4.6 augmentations. The adversary costs 1.84× the shortest-path rule in aggregate and 8× on the worst single instance. The bound is about what cannot happen, not about what does.

The proof is a side effect

The failed search is the interesting event. When no augmenting path remains, the set of nodes it managed to reach is a minimum cut — cheapest set of edges whose removal disconnects s from t — and its capacity equals the flow. You do not go looking for it. It is the wreckage of the last search.

On the mesh this is not a formality, because the cut is not guessable. Ten nodes, nineteen edges, and the minimum cut is S = {s, c, e}: two edges straight off the source, one out of c, two out of e. Five edges crossing three different depths of the drawing, summing to 20, which is the flow. There are 256 possible cuts of this network; brute force confirms this is the unique minimum, and the algorithm found it without enumerating any of them.

Across 300 random networks, every one checked both ways:

• the cut from the failed search equalled the flow — 300 of 300
• and equalled the brute-force minimum over every subset — 300 of 300, 234,880 cuts enumerated to say so
• every flow produced was feasible and conserved — 0 violations

One detail that is easy to miss: 63 of the 300 networks have more than one minimum cut, and in exactly those 63 the two extremes differ. Running the reachability forward from s gives you the smallest minimum cut; running it backward from t gives the largest. Same capacity, different edges. The capacity of a minimum cut is unique; the cut is not, and if you are using the cut to decide which links to buy, that distinction is the whole decision.

Matching, for free

Set every capacity to 1 and the same machine solves bipartite matching. The instance here is deliberately not perfectly matchable — L1, L2 and L3 between them have only two partners — so the maximum matching is 5, not 6.

The question “why can’t it be 6?” is usually answered by case analysis. Here the cut answers it. The minimum cut is {L4, L5, L6, R1, R2}, five vertices, and every one of the twelve edges touches at least one of them. That is a vertex cover of size 5, so no matching can exceed 5, because each matched edge needs its own cover vertex. Matching 5, cover 5, and they are the same five objects seen from two sides — König’s theorem, delivered by the same failed search, and the unique minimum among all 4096 cuts of the network.

What’s on screen

• Edges are pipes. The blue fill is the flow in them; amber means saturated. The number is flow/capacity.
• The dashed violet arcs are the residual graph’s backward half-edges — the undo capacity — drawn on the opposite side of each pipe so they cannot be confused with the edge itself. They exist only where flow already is. When the chosen path travels one, it lights up and says how much it is undoing. That mark is the subject of the piece.
• Nodes outlined in grey were reached by the current search; the teal path is the one it chose, and the panel says what it will push.
• When the run ends, the two sides of the cut are shaded (cool for S, warm for T) and the cut edges get a red halo and a slash. The panel prints the cut’s capacity next to the flow, and whether they match.
• pick by hand hands you the path choice. Click a neighbour to extend from the amber node, reach t and it pushes. Back-edges are legal moves, which is the point: take s → u → v → t on the block with back-edges off and you can watch yourself get stuck, then switch them on and find s → v → u → t by hand.
• back-edges: off is the control, not a bug mode.

Notes

• src/cut.mjs is framework-free and has no rendering in it: half-edges in reverse-indexed pairs, four path rules plus Dinic, a cut extractor, a brute-force cut enumerator for cross-checking, and the sweeps that produce every table above.
• Every number in this write-up is read off the running module by scripts/screenshot-demo.mjs, which checks 73 claims on every build. Several are deliberately checks that two things are identical, or that a count is zero, because those are the claims that rot silently.
• The mesh’s capacities were searched for, not chosen: the instance had to have a unique minimum cut, that cut had to be non-trivial on both sides and cross more than one depth, and the forward-only run had to get it wrong. Sixty thousand random capacity assignments were tried against those filters. Saying so matters — a hand-picked example that makes a point is a different kind of evidence from a random sample, and both appear above, labelled.
• The adversary (thinnest path) is an honest rule, not a sabotage: it picks the lowest-capacity residual edge still lying on some s–t walk and routes through it. That it reproduces the textbook Θ(f) worst case is the finding — the worst case is not bad luck, it is a strategy, and nothing in the specification forbids it.
• Capacities are integers throughout, which is why every augmentation moves a whole number and the loop terminates. With irrational capacities Ford–Fulkerson can fail to terminate at all; Edmonds–Karp cannot, and that is a second reason the path rule is not a detail.
• The event log records search steps only for the first 60 augmentations. The adversary on the rung runs 2000 of them and nobody watches 2000 searches; the flow still advances correctly past that point, and step widens its stride to match the length of the run.