Nontermination with Irrational Capacities

Why Irrational Capacities Require Care

With integer capacities, every Ford–Fulkerson augmentation increases the flow value by at least one. Since the flow value is bounded above, this gives a finite-termination argument. For irrational capacities, positive bottlenecks need not be bounded away from zero. An algorithm may therefore make infinitely many valid augmentations whose sizes tend to zero. This is a failure of finite termination, not a failure of the flow values to converge.

Throughout, a network is a finite directed graph with a source \(s\), a sink \(t\), and a nonnegative capacity on each arc. A feasible flow respects every capacity and satisfies flow conservation at every vertex other than \(s\) and \(t\). For an arc \(uv\), its forward residual capacity is its capacity minus its current flow; the reverse residual arc \(vu\) has residual capacity equal to the current flow on \(uv\). An augmenting path is a directed \(s\)-to-\(t\) path in the residual network. Its bottleneck is the smallest residual capacity on its arcs. Augmenting by this bottleneck preserves feasibility.

The important distinction is between an algorithm that continues to find augmenting paths and one that finishes after finitely many steps. If the method makes infinitely many augmentations, it does not terminate, even if the flow values approach the maximum-flow value. The choice of path can matter: Ford–Fulkerson does not prescribe a unique path-choice rule.

An Irrational-Capacity Counterexample

The standard counterexample uses a finite directed network with irrational capacities and a path-choice rule that repeatedly uses residual routes to undo part of the preceding routing. Its essential feature is a sequence of positive bottlenecks that becomes arbitrarily small. The network has a finite maximum-flow value, but this rule produces infinitely many augmentations instead of reaching a maximum flow in finitely many steps.

This result is specific to the termination claim: it says that finite termination is not guaranteed for arbitrary irrational capacities and arbitrary path choices. It does not say that every run on every irrational-capacity network is infinite. A favorable path choice may terminate quickly, and some irrational-capacity instances have an obvious finite sequence of augmentations.

To understand the mechanism, let \(f_k\) be the flow after \(k\) augmentations and let \(\delta_k\) be the bottleneck used at step \(k\). Each \(\delta_k\) is positive, so every step is a genuine augmentation. But if \(\delta_k\) tends to zero, there need not be a positive lower bound on the increments. A bounded increasing sequence of flow values can have infinitely many positive increments.

The formula records the increase in flow value at each augmentation. The edge flows themselves may be rerouted: using a reverse residual arc cancels some previously sent flow. The total flow value still increases by the bottleneck, but a particular original arc need not carry a monotone sequence of flows.

What the Integer-Capacity Argument Used

For integer capacities, if the current flow is integer-valued on every arc, then every residual capacity is an integer. The bottleneck of an augmenting path is therefore a positive integer, hence at least \(1\). Starting from zero flow, after \(k\) augmentations the flow value is at least \(k\), while it is bounded above by the sum of capacities leaving \(s\). Only finitely many augmentations are possible.

Proof. Initially, every arc flow is an integer. Suppose every arc flow before an augmentation is an integer. Each forward residual capacity is the integer capacity minus the integer flow, and each reverse residual capacity is an integer flow. Thus every residual capacity is an integer. The bottleneck along an augmenting path is the minimum of finitely many positive integer residual capacities, so it is a positive integer and is at least \(1\). Augmenting by that amount leaves all arc flows integer-valued. By induction, every augmentation increases the flow value by at least \(1\). The flow value cannot exceed the total capacity of the arcs leaving \(s\), which is finite because the network has finitely many arcs. Consequently, only finitely many augmentations can occur. \(\square\)

The proof has two distinct ingredients: the bottleneck is an integer, and the flow value has a finite upper bound. The upper-bound ingredient remains true for real capacities. The integer ingredient does not: a positive real bottleneck may be smaller than \(1\), and successive positive bottlenecks may approach zero.

Convergence Is Not Finite Termination

Suppose an infinite run has bottlenecks \(\delta_1,\delta_2,\ldots\), all positive, and their sum is finite. Then the flow values increase and approach a finite limit. This observation is arithmetic, not a guarantee that the limiting flow has already been reached at any finite step. For example, the partial sums of a convergent series of positive terms are strictly below their limit at every finite stage.

This numerical sequence explains the logical gap in trying to extend the integer-capacity proof. It is not, by itself, a Ford–Fulkerson run: an actual run must obtain its bottlenecks from residual capacities on paths in a fixed network. The standard counterexample stated above supplies such a network and path-choice rule. The lesson is to distinguish a general sequence argument from a verified network example.

What Infinite Augmentation Does and Does Not Show

An infinite run shows that this path-choice rule does not terminate. It does not show that the network has no maximum flow. A finite network with finite capacities has a finite upper bound on the flow value; the issue is whether the algorithm reaches a maximum in finitely many augmentations. Nor does the existence of one nonterminating run rule out a different path-choice rule that terminates.

In particular, one must not infer that every positive augmentation is at least some fixed \(\varepsilon>0\). Integer capacities supplied such a lower bound, namely \(1\), but irrational capacities need not. If an argument relies on a uniform lower bound, it must establish that bound from the specific network and path rule rather than assume it.

Common mistake. A tempting but invalid argument is: “The flow value increases at every step and is bounded above, so the algorithm must stop.” A bounded increasing sequence need not become constant after finitely many terms. It may increase at every step while converging to its supremum. The correction is to show a positive lower bound on every augmentation, as the integer-capacity proof does, or to use a different termination argument whose hypotheses apply.

Another mistake is to confuse “no augmenting path remains” with “the current flow values are close to their limiting value.” The algorithm’s stopping condition is the absence of a residual \(s\)-to-\(t\) path. Approximation to a limit does not establish that condition. The maximum-flow min-cut theorem, proved later in the course, gives a certificate for a flow when the residual network has no augmenting path; it does not turn an infinite sequence into a finite algorithm.

Practical Consequences

When applying Ford–Fulkerson, keep the capacity assumptions and path-selection rule visible. Integer capacities guarantee finite termination under arbitrary augmenting-path choices. Irrational capacities remove that guarantee; they do not automatically cause nontermination. If termination is important, an algorithm with a specified path rule and a termination proof under the relevant capacity assumptions is needed.

The central pitfall is not that a maximum flow fails to exist. It is that repeated valid progress need not reach the maximum after finitely many steps. In the irrational-capacity setting, the bottleneck can be positive at every iteration while having no uniform positive lower bound. That is precisely why the integer-capacity proof cannot be transferred unchanged.