A search for room that never ends

The bottleneck is the whole story proved the max-flow min-cut theorem: the most a network of roads can carry from a source to a sink equals the smallest total capacity of roads whose removal separates them. The proof was a method. Start with nothing flowing. Look for a route from source to sink along which every road still has room — counting, as room, the chance to cancel flow already sent the other way along a road. Push as much as the tightest road on that route allows. Repeat. When no route with room remains, the roads that block every route form a cut, and its capacity equals the flow.

That proof contains a quiet assumption, and the assumption is that the method stops. Lester Ford and Delbert Fulkerson, who published the method in 1956, noted that it stops whenever the capacities are whole numbers, because every push then adds at least one unit and the flow cannot exceed the capacity of any cut. They also showed that it need not stop otherwise. This essay builds a small network on which it does not, and watches what happens instead.

Six places and three special roads #

The network has a source $s$, a sink $t$ and four places between them. Six ordinary roads, from $s$ to three of the places and from three of the places to $t$, each carry up to two units; they are never the tight ones. Three special roads join the middle places: $e_1$ from $v_2$ to $v_1$ with capacity 1, $e_2$ from $v_4$ to $v_3$ with capacity $r = (\sqrt5 - 1)/2 \approx 0.618$, and $e_3$ from $v_2$ to $v_3$ with capacity 1. Networks of this kind go back to Ford and Fulkerson’s own example of 1962, and Uri Zwick found in 1995 the smallest ones on which the method can fail to stop, of which this is essentially one; the number $r$ is chosen for a single property, that

$$r^2 = 1 - r.$$

The maximum flow is 5. A cut that separates $s$ from $t$ with capacity 5 exists — the road from $s$ to $v_4$, the road from $v_1$ to $t$, and $e_3$, which between them block every route out of the places $s$, $v_1$, $v_2$ — and a flow of 5 exists, which the method finds in three pushes when it chooses its routes well, as a figure below shows. The failure is entirely about the choice.

Room, counted both ways #

The method’s notion of room deserves a closer look, because the bad routes depend on it. A road that already carries some flow has two kinds of room. It can carry more in its own direction, up to its capacity: that is its forward room. And flow along it can be cancelled by pushing in the opposite direction, up to the amount it carries: that is its backward room. The residual network records both, and a route with room is a route in that network — it may go along some roads and against others.

Going against a road is what lets the method correct its earlier choices. When several pairs share the roads showed what goes wrong without it, for several commodities at once: a greedy choice of routes blocks better ones, and nothing undoes it. With backward room, a later route can reroute flow that an earlier one sent the wrong way, and the max-flow min-cut theorem follows because, when no route with room is left, the places the source can still reach form one side of a cut whose roads are all full forwards and all empty backwards. The cheapest way to send used the same residual network with prices, where pushing against a road refunds its price, and found that a flow is cheapest exactly when no cycle in the residual network pays to push round.

In the example, every one of the bad routes uses backward room. The route $p_1$ goes against $e_3$, undoing part of the opening push; $p_2$ goes against $e_2$; $p_3$ goes against $e_1$. The method keeps undoing and redoing, and each undo leaves a little more room than it should for the next redo. Backward room is what makes the method correct when it stops, and it is also what lets it circle for ever without stopping.

The same position, smaller #

The bad choice is a fixed cycle of four routes after one opening route. The opening route $p_0$ goes $s, v_2, v_3, t$ and fills $e_3$. Then the routes repeat: $p_1$, which goes $s, v_4, v_3, v_2, v_1, t$ — along $e_2$, back against the flow on $e_3$, along $e_1$ — then $p_2$, which goes $s, v_2, v_3, v_4, t$, then $p_1$ again, then $p_3$, which goes $s, v_1, v_2, v_3, t$.

The figure follows the room on the three special roads. After the opening push it is $1$, $r$ and $0$. The route $p_1$ is limited by $e_2$, so it pushes $r$, emptying $e_2$’s room and freeing $r$ on $e_3$; $p_2$ pushes $r$ back through, refilling $e_2$’s room and emptying $e_3$’s. The second $p_1$ is now limited by $e_1$, whose room has fallen to $1 - r = r^2$; it pushes $r^2$. And $p_3$ pushes $r^2$, restoring $e_1$’s room. At the end of the round the room is $r^2$, $r^3$ and $0$ — the starting position with every number multiplied by $r^2$, which is exactly what the identity $r^2 = 1 - r$ arranges.

So the next round is the same round, smaller, and the one after it smaller again, for ever. Every route the method uses has room, every push is positive, and the stopping rule — no route with room — is never met. The figure checks the pattern exactly, in numbers of the form $a + b\sqrt5$ computed in whole numbers, for ten rounds: the room after round $m$ is $r^{2m}$, $r^{2m+1}$ and exactly $0$.

Converging, but not to the answer #

The flow pushed in each round is $2r^{2m+1} + 2r^{2m+2} = 2r^{2m}$, and the total, with the opening unit, is

$$1 + 2\left(1 + r^2 + r^4 + \cdots\right) = 1 + \frac{2}{1 - r^2} = 1 + \frac{2}{r} = 2 + \sqrt5 \approx 4.236.$$

The sum is the golden ratio’s arithmetic doing in a network what it does in the rectangle that eats itself: there, cutting a square from a golden rectangle leaves a golden rectangle scaled by $r$, and the squares’ sides form a geometric series in $r$ adding up to the rectangle’s length; here, each round of pushes leaves the same position scaled by $r^2$, and the pushes form a geometric series adding up to $2 + \sqrt5$. The sum is finite for the same reason the golden rectangle is: a geometric series with ratio less than one converges, however many terms it has.

The gap to the limit shrinks by $r^2 \approx 0.382$ every four pushes, so the flow converges quickly — by forty pushes it is within $10^{-8}$ of $2 + \sqrt5$. And the shortfall from the maximum, $5 - (2 + \sqrt5) = 3 - \sqrt5 \approx 0.764$, never changes. The method has converged, in every practical sense, to a wrong answer, and it has not stopped, so it never announces one.

The method’s two guarantees — that the flow only increases, and that if it stops it stops at the maximum — say nothing about the limit of a run that does not stop.

Choosing the shortest route #

Jack Edmonds and Richard Karp showed in 1972 that one rule for choosing routes repairs everything: always push along a route with the fewest roads.

On this network the rule finds $s, v_1, t$ and $s, v_4, t$ first, two roads each, pushing 2 along each, and then $s, v_2, v_3, t$, pushing 1 along $e_3$ — a flow of 5 in three pushes. The rule’s guarantee is general and does not care about capacities. Each push fills some road on a shortest route, and a filled road can only become usable again when flow is pushed back along it, which happens only on a route that is longer; so the shortest-route distance from the source to each place never decreases, and a given road can be the tight one only about as many times as there are places. The method stops after at most a number of pushes proportional to the places times the roads, whatever the capacities are — rational, irrational, or as unhelpful as $0.618\ldots$ — and it stops at the maximum, by the max-flow min-cut theorem.

The bad routes in the essay’s example are longer than necessary at every step: $p_1$ uses five roads where routes of two exist. Edmonds and Karp’s rule would never choose it. The non-terminating run is a run in which the method is allowed to choose badly, and the theorem is that the method, as originally stated, does not forbid it. The difference matters in practice wherever maximum flow is a step inside something larger: the cut trees of one tree for every cut are built from a maximum flow between each of many pairs of places, and a method that might not stop at any one of them could not be the foundation of the others.

A min-max theorem whose proof is a search #

The max-flow min-cut theorem is one of a family that two numbers that have to meet described in general: a largest quantity of one kind equals a smallest quantity of another, and each certifies the other. One bottleneck and nothing else found the same shape in Hall’s theorem on matchings, which is the flow theorem on a network with unit capacities, and there too the proof is a search for an improving route that stops when none exists.

The example shows that such proofs carry two separate claims. One is that a stopped search proves optimality — when no route has room, the flow equals a cut and is therefore the largest. That claim is unconditional. The other is that the search stops, and that claim needs whole numbers, or a rule for choosing routes, or some other measure of progress that cannot shrink for ever. With whole numbers the measure is the flow itself, which rises by at least one each time. With Edmonds and Karp’s rule it is the shortest-route distance, which can rise only finitely often. With an irrational capacity and a free choice there is no such measure, and the example is the proof that none can be found.

The theorem itself survives, by another route. For real capacities, the maximum flow is the optimum of a linear programme whose dual is the minimum cut, and linear programming duality proves the theorem without any search at all. What fails is not the theorem but one constructive proof of it, which needed a hidden finiteness that the integers had been supplying all along.

Rounding stops what arithmetic cannot #

The run above is computed exactly. Computed in ordinary floating point, as almost every program would compute it, it behaves differently.

In floating point, $r$ is a binary fraction close to $(\sqrt5 - 1)/2$, and $r^2 = 1 - r$ holds only up to rounding. The repeating pattern depends on that identity at every round, and it magnifies the discrepancy — each round divides the positions by $r^2$ to compare with the last, and so multiplies any error relative to them by about $1/r^2 \approx 2.6$. Near step 80, when the amounts being pushed are around $10^{-8}$, a road’s room comes out not as a small positive number but as nought or slightly less, the next route seems to have no room, and the program stops. It reports a flow of $4.23606796$, within $2 \times 10^{-8}$ of $2 + \sqrt5$, and believes the network is full.

That is a sharper failure than not stopping. A program that runs for ever is visibly broken. A program that stops and reports $4.236$ for a network whose true maximum is $5$ gives no sign that anything has gone wrong, and the residual network it leaves behind even appears to contain a cut of capacity $4.236$ — a cut that does not exist, assembled from roads whose room is nought only because of rounding. The orbit a computer draws met the same phenomenon in iteration, where rounding replaced a true orbit by one that looked plausible and was not, and the moral is the same: floating point can turn an argument that relies on an exact identity into a different computation altogether.

Whole numbers stop it, eventually #

With whole-number capacities, stopping is guaranteed, and the guarantee is still weaker than it sounds.

The standard example has four outer roads of capacity $C$ and one middle road of capacity 1 joining the two intermediate places. Routing every push through the middle road — forwards, then backwards against the flow just sent, then forwards again — moves one unit per push, and reaching the maximum flow of $2C$ takes $2C$ pushes. With $C = 1000$ that is two thousand pushes for a network that shortest routes fill in two. The number of pushes is bounded by the size of the answer, and the size of the answer can be exponential in the number of digits needed to write the capacities down, so the plain method is not a polynomial-time algorithm even when it stops. Edmonds and Karp’s paper, which introduced the shortest-route rule, was among the first to make that distinction explicit — between an algorithm that stops and one that stops quickly.

An algorithm and an irrational number #

The failure has a family resemblance worth naming. The oldest algorithm, drawn as a tiling showed that Euclid’s algorithm, applied to two lengths in an irrational ratio, never stops: it keeps cutting squares from a rectangle whose shape repeats, smaller each time, exactly as the room on the three roads repeats here. The golden rectangle is the extreme case there — each step leaves a smaller golden rectangle — and the golden ratio is the extreme case here, because $r^2 = 1 - r$ is the identity that makes the position repeat after the fewest pushes.

In both, a procedure that terminates on whole numbers is turned into a self-similar process by an irrational input. And in both, what terminates the procedure on a machine is not the mathematics but the finite precision with which the machine represents the input. The difference is that Euclid’s algorithm was never claimed to stop on irrational lengths — its non-termination is the proof that the lengths are incommensurable — while the augmenting-path method is routinely run on real-valued capacities, by programs that inherit the textbook assumption that it stops.

What the exact computation does and does not show #

Every number in the figures except the floating-point run is exact, in the field of numbers $a + b\sqrt5$, so the claims that each push is positive, that the room returns to the scaled position, and that the flow stays below $2 + \sqrt5$ are checked without rounding for forty pushes. They are not checked for ever; the proof that the pattern continues is the one-line induction from $r^2 = 1 - r$, which the figure’s ten rounds illustrate.

The figures also show only one bad choice of routes. The method may choose any route with room, and on this network many choices terminate. Non-termination is a property of the method’s freedom, exhibited by one adversarial sequence, not something every run does — which is precisely why it went unnoticed by anyone who ran the method rather than reasoning about it.

Still open: how few pushes are needed #

The shortest-route rule bounds the number of pushes by a multiple of places times roads. The best algorithms for maximum flow now do much better than augmenting one route at a time: preflow-push methods of Andrew Goldberg and Robert Tarjan, and, in 2022, an algorithm of Li Chen, Rasmus Kyng, Yang Liu, Richard Peng, Maximilian Probst Gutenberg and Sushant Sachdeva running in time close to linear in the number of roads, for integer capacities. Whether maximum flow can be computed in truly linear time, and whether the near-linear methods, which rely on continuous optimisation and careful rounding, can be made practical, are open. So, in a sense the example makes vivid, is the question of what “computing” a maximum flow means when the capacities are real numbers that no machine represents exactly: the exact field arithmetic used here works for quadratic irrationals, and for general real capacities there is no finite representation to compute with at all.