Transfinite Ford–Fulkerson on a finite network

Abstract

It is well-known that the Ford–Fulkerson algorithm for finding a maximum flow in a network need not terminate if we allow the arc capacities to take irrational values. Every non-terminating example converges to a limit flow, but this limit flow need not be a maximum flow. Hence, one may pass to the limit and begin the algorithm again. In this way, we may view the Ford–Fulkerson algorithm as a transfinite algorithm.

We analyze the transfinite running-time of the Ford–Fulkerson algorithm using ordinal numbers, and prove that the worst case running-time is $ω^{Θ (| E |)}$ . An upper bound of $ω^{| E |}$ is established via induction on $| E |$ . For the lower bound, we first show that we can model the Euclidean algorithm via Ford–Fulkerson on a certain network. By running this example on a pair of incommensurable numbers, we obtain a new robust non-terminating example. We then describe how to carefully glue k copies of our Euclidean example in parallel and describe a run of the Ford–Fulkerson algorithm that requires at least $ω^{Ω (| E |)}$ steps. This run includes an infinite number of “recharging” steps that reinitialize the k copies of our Euclidean example.

Keywords

Network flows ordinals

1. Introduction

The Ford–Fulkerson algorithm [12] is a classic algorithm for computing the maximum flow in a network. At each step, the algorithm chooses an augmenting path P from the source vertex s to the sink vertex t and then pushes as much flow as possible along P. This procedure is then iterated, until no such augmenting path exists. It is well-known that in certain networks with irrational capacities, the Ford–Fulkerson algorithm does not necessarily terminate if the augmenting paths are not chosen carefully. The smallest non-terminating example is due to Zwick [19].

Dinits [9] and Edmonds and Karp [10] independently showed that if one always chooses an augmenting path of minimum length, then the Ford–Fulkerson algorithm will necessarily terminate. We emphasize that whenever we refer to the Ford–Fulkerson algorithm, we mean the original version where augmenting paths are chosen arbitrarily.

It is fairly easy to show that if the Ford–Fulkerson algorithm does not terminate, then it will converge to a (not necessarily maximum) flow f. Thus, after ω steps, we may begin the algorithm anew, starting with the limit flow f. By iterating this procedure, we can view the Ford–Fulkerson algorithm as a transfinite algorithm and ask what its worst case running-time is in terms of ordinal numbers. Note that the notion of using ordinals in computability theory dates back at least to the work of Turing [18].

The following theorem, which is the main result of this paper, determines this worst case ordinal running-time up to a constant factor in the exponent.

Theorem 1.
The worst case running-time of the Ford–Fulkerson algorithm is $ω^{Θ (| E (N) |)}$ .

This theorem is established via the following two lemmas.
Lemma 2.
For every network N, every run of the Ford–Fulkerson algorithm terminates after at most $ω^{| E (N) |}$ steps.

Although we are working with ordinal numbers where transfinite induction might seem like a natural tool, the proof of Lemma 2 proceeds by finite induction on the exponent $| E (N) |$ .
Lemma 3.
For every $ℓ \in N$ , there exists a network $N (ℓ)$ on ℓ arcs and a run of the Ford–Fulkerson algorithm on $N (ℓ)$ with run-time at least $ω^{⌊ \frac{ℓ}{25} ⌋}$ .

To prove Lemma 3, we first construct a new non-terminating example of Ford–Fulkerson. The main idea is to demonstrate that the Euclidean algorithm can be modelled by applying Ford–Fulkerson to a particular network. Thus, a run of the Euclidean algorithm on two incommensurable numbers gives a non-terminating example of Ford–Fulkerson. We then carefully glue k copies of our Euclidean example in parallel and describe a run of the Ford–Fulkerson algorithm that requires at least $ω^{Ω (| E |)}$ steps. This particular run includes an infinite number of “recharging” steps that reinitialize the k copies of our Euclidean example.

Paper organization. In Section 2 we define ordinal running-time. We prove our upperbound in Section 3 and our lowerbound in Section 4. We finish by giving some concluding remarks in Section 5.
2. Ordinal running-time

We now describe how we intend to measure running-time via ordinal numbers. For an introduction to ordinals and network flow theory, we refer the reader to [15] and [7], respectively. We use an extended notion of a Turing machine that can complete an infinite number of steps of computation, and continue computing afterwards. This matches the notion of infinite time Turing machines by Hamkins and Lewis [13]. The ordinal running-time is then quite natural; it is the worst case running-time of performing brute-force search over all choices of augmenting paths. We give the precise details below.

All networks considered will always be finite with finite arc capacities. Each step of the Ford–Fulkerson algorithm will be indexed by an ordinal α and the corresponding flow after step α will be denoted $f_{α}$ (we allow $f_{0}$ to be any valid flow). A run of the algorithm is obtained by choosing an augmenting path $P_{β + 1}$ for $f_{β}$ (if it exists) for each successor ordinal $β + 1$ , and setting $f_{β + 1}$ to be the flow obtained from $f_{β}$ by pushing as much flow as possible along $P_{β + 1}$ . If no augmenting path exists at step $β + 1$ , we define $f_{β + 1}$ to be $f_{β}$ . If α is a limit ordinal, we define $f_{α}$ to be a certain limit flow. Some care must be taken to ensure that this limit flow is well-defined and this is the content of Lemma 4.

The run-time of a particular run is the least ordinal α such that $f_{α} = f_{α + 1}$ . For a fixed network N, the (worst case) running-time of the Ford–Fulkerson algorithm on N is the maximum of the run-times over all runs of the algorithm on N. The main result of this section is that transfinite Ford–Fulkerson is a well-defined procedure.

Lemma 4.
For every ordinal α, every run of the Ford–Fulkerson algorithm assigns a well-defined flow $f_{α}$ after step α.
Proof.
Let $N = (V, E)$ be a network with a source $s \in V$ , a sink $t \in V$ , and non-negative finite capacities $c (u, v)$ for each arc $(u, v) \in E$ . We proceed by transfinite induction. We let $f_{0}$ be any valid initial flow. Now, let α be an ordinal, and assume that $f_{β}$ is defined for all ordinals $β < α$ .

First suppose α is a successor ordinal, say $α = β + 1$ . If there is no augmenting path for $f_{β}$ , then we set $f_{α} : = f_{β}$ . Otherwise, if we choose the augmenting path $P_{β + 1}$ for $f_{β}$ , then we define $f_{α}$ to be the flow obtained from $f_{β}$ by pushing as much as possible along $P_{β + 1}$ .

If α is a limit ordinal, we proceed as follows. For each arc e and ordinal $β < α$ , we define a ${- 1, 0, 1}$ -valued variable $y (e, β)$ as follows. If $β : = γ + 1$ and we chose $P_{γ + 1}$ as the augmenting path for $f_{γ}$ , then we set $y (e, β)$ to be 1 if e is a forward arc of $P_{β}$ , −1 if e is a backward arc of $P_{β}$ , and 0 otherwise. We initialize $y (e, 0) : = 0$ . We also let $x_{0}$ be the value of the initial flow $f_{0}$ and set $x_{β}$ to be the amount of flow pushed by $P_{β}$ . If β is a limit ordinal or there is no augmenting path at step β, we set both $y (e, β)$ and $x_{β}$ to be 0.

Consider $\sum_{β < α} x_{β}$ . Observe that at most countably many terms are non-zero, since this sum is bounded (by the capacity of a minimum cut). Moreover, this series converges absolutely, since each term is non-negative. Therefore, this sum is independent of the order of summation and is hence well-defined. We define a flow $f_{α}$ by setting $\begin{matrix} f_{α} (e) = f_{0} (e) + \sum_{β < α} y (e, β) x_{β} \end{matrix}$ for each $e \in E$ . Observe that $\sum_{β < α} y (e, β) x_{β}$ is an absolutely convergent series, since $\sum_{β < α} x_{β}$ converges. Therefore, $\sum_{β < α} y (e, β) x_{β}$ is also a well-defined sum. Evidently, $0 ⩽ f_{α} (u, v) ⩽ c (u, v)$ for all $(u, v) \in E$ since $0 ⩽ f_{β} (u, v) ⩽ c (u, v)$ for all $β < α$ . It remains to verify that $f_{α}$ satisfies conservation of flow. Let $u \in V ∖ {s, t}$ . Observe that $\begin{array}{l} \sum_{(v, u) \in E} f_{α} (v, u) - \sum_{(u, v) \in E} f_{α} (u, v) & = \sum_{(v, u) \in E} lim_{β \to α} f_{β} (v, u) - \sum_{(u, v) \in E} lim_{β \to α} f_{β} (u, v) \\ = lim_{β \to α} (\sum_{(v, u) \in E} f_{β} (v, u) - \sum_{(u, v) \in E} f_{β} (u, v)) \\ = 0 \end{array}$ where the last equality follows from conservation of flow for $f_{β}$ . □

3. The upperbound

Given a flow f, an arc e is a zero-arc if $f (e) = 0$ , is saturated if $f (e)$ is equal to the capacity of e, and is extreme if it is saturated or a zero-arc.

Lemma 5.
For every $k \in N$ , every network N, and every run of the Ford–Fulkerson algorithm on N, either the algorithm has already terminated after $ω^{k}$ steps or there are at least $k + 1$ extreme arcs in $f_{ω^{k}}$ .
Proof.
We proceed by (finite) induction on k. Since some arc must be extreme after pushing as much flow along an augmenting path, the lemma clearly holds for $k = 0$ (note $ω^{0} = 1$ ). We inductively assume that the claim holds for k. Now, for each $j \in N$ , let $A_{j}$ be the set of extreme arcs for the flow $f_{j ω^{k}}$ . Since $ω^{k}$ steps have passed between $j ω^{k}$ and $(j + 1) ω^{k}$ , by induction we may assume that $| A_{j} | ⩾ k + 1$ for all j. Next note that each arc can only switch between being a zero-arc and a saturated arc a finite number of times because the value of the flow is always bounded. This implies that for all sufficiently large j, there is an arc $a_{j} \notin A_{j}$ such that $a_{j}$ is extreme in $f_{j ω^{k} + 1}$ . Let A be such that $A_{j} = A$ infinitely often and a be such that $a_{j} = a$ infinitely often. Since ${lim}_{β \to ω^{k + 1}} f_{β} = {lim}_{j \to ω} f_{j ω^{k}}$ , it follows that each edge $e \in A$ is extreme for $f_{ω^{k + 1}}$ . On the other hand, since $f_{ω^{k + 1}} = {lim}_{j \to ω} f_{j ω^{k} + 1}$ , we conclude that a is also extreme for $f_{ω^{k + 1}}$ . Thus, $f_{ω^{k + 1}}$ has at least $k + 2$ extreme arcs, as required. □

Using Lemma 5, we now prove our upperbound, restated for convenience. Lemma 2.
For every network N, every run of the Ford–Fulkerson algorithm terminates after at most $ω^{| E (N) |}$ steps.
Proof.
If the algorithm has not terminated after $ω^{| E (N) |}$ steps, then Lemma 5 implies that for all $j \in N$ , every arc of N is extreme in $f_{j ω^{| E (N) | - 1}}$ . Let c be the smallest non-zero capacity over all arcs of N. Since all arcs are extreme in $f_{j ω^{| E (N) | - 1}}$ , the flow increases by at least c at step $j ω^{| E (N) | - 1} + 1$ (for all j). This is a contradiction since the value of $f_{ω^{| E (N) |}}$ is finite. □

4. The lowerbound

Let $a, b \in R_{+}$ . We begin by constructing a network $N_{a, b}$ and a run of the Ford–Fulkerson algorithm on $N_{a, b}$ which simulates the Euclidean algorithm on a and b.

Figure 1.

A network $N_{a, b}$ and two augmenting paths which allow for the subtraction of b from a.

Lemma 6.

Let $N_{a, b}$ be the network depicted in Fig. 1 . If $\frac{a}{b} \notin Q$ , then there is a run of the Ford–Fulkerson algorithm on $N_{a, b}$ with run-time at least ω.

Proof.

The labelled arcs of Fig. 1 (denoted $e_{a}$ and $e_{b}$ ) have capacities a and b with $0 < b ⩽ a$ . The other arcs have large capacity (which we will specify later). Given a flow f and an arc e, the residual capacity of e, denoted $c^{'} (e)$ , is defined to be $c (e) - f (e)$ . Let $P_{1}$ and $P_{2}$ be the augmenting paths given by the dashed arcs. Now, starting from the zero-flow, if we push flow along $P_{1}$ and $P_{2}$ , then $c^{'} (e_{a})$ becomes $a - b$ and $c^{'} (e_{b})$ is still b. We continue this process until $a_{1} : = a - n_{1} b ⩽ b$ . At this point, note that the value of the current flow is $2 n_{1} b$ and that the roles of $a_{1}$ and b are reversed.

Let $P_{1}^{'}$ and $P_{2}^{'}$ be the reflections of $P_{1}$ and $P_{2}$ through the vertical line from s to t. By next pushing flow along the augmenting paths $P_{1}^{'}$ and $P_{2}^{'}$ , we can convert the residual capacity of $e_{b}$ to $b - a_{1}$ . We continue this process until $b_{1} : = b - m_{1} a_{1} ⩽ a_{1}$ . Note that the horizontal arcs are backward arcs of $P_{1}^{'}$ and $P_{2}^{'}$ . However, since $2 m_{1} a_{1} ⩽ 2 b ⩽ 2 n_{1} b$ , there is enough flow along the horizontal arcs to perform these $2 m_{1}$ augmentations. The roles of $a_{1}$ and $b_{1}$ have been reversed again and we continue inductively. Therefore, this example “computes” the greatest common divisor of a and b. If $\frac{a}{b} \notin Q$ , it will have run-time at least ω, as required. However, it remains to check that the total flow is still bounded after ω steps (so that we may specify the capacities). Claim 1.

The total flow after ω steps of the Euclidean run on $N_{a, b}$ is at most $4 (a + b)$ .

Proof.

Let $a = a_{0} > b = b_{0} > a_{1} > b_{1} > \dots$ be the intermediate outputs of the Euclidean algorithm. Observe that for all $n ⩾ 0$ , $a_{n + 1} ⩽ \frac{1}{2} a_{n}$ and $b_{n + 1} ⩽ \frac{1}{2} b_{n}$ . Therefore, the total flow after ω steps is at most $2 \sum_{n = 0}^{\infty} (a_{n} + b_{n}) ⩽ 4 (a + b)$ , as required. □

Thus, for all arcs $e \notin {e_{a}, e_{b}}$ , we can take $c (e) = 4 (a + b)$ . □

This example is quite robust in that a small perturbation of the arc capacities will almost certainly produce another non-terminating example. We will now “glue” k copies of $N_{a, b}$ in parallel to obtain a run of the Ford–Fulkerson algorithm with run-time at least $ω^{k}$ . This proves Lemma 3. A key property of our gluing construction is that we can use one copy of the Euclidean example to “recharge” another copy.

Lemma 3.

For every $ℓ \in N$ , there exists a network $N (ℓ)$ on ℓ arcs and a run of the Ford–Fulkerson algorithm on $N (ℓ)$ with run-time at least $ω^{⌊ \frac{ℓ}{25} ⌋}$ .

Proof.

For each $k \in N$ , we define a network $N_{a, b}^{k}$ and show that there is a run of the Ford–Fulkerson algorithm on $N_{a, b}^{k}$ with run-time at least $ω^{k}$ . For simplicity, we only illustrate the case $k = 2$ ; the general case is similar. Figure 2 depicts the corresponding network for $k = 2$ . The labelled arcs have capacities $a, b, a$ , and b respectively with $b < a$ incommensurate. We denote these arcs as $ℓ_{1}, \dots, ℓ_{4}$ from left to right. The remaining arcs have large capacities, which we will specify later. We denote the three middle vertical arcs as $e_{1}, e_{2}$ and $e_{3}$ from left to right.

Note that there are “left” and “right” copies of $N_{a, b}$ sitting in $N_{a, b}^{2}$ , depicted by dashed edges in Fig. 2.

Figure 2.

A network $N_{a, b}^{2}$ (depicted twice) that admits a run of Ford–Fulkerson that takes $ω^{2}$ iterations. Left and right copies of $N_{a, b}$ in $N_{a, b}^{2}$ are shown by dashed edges.

Let $a = a_{0} > b = b_{0} > a_{1} > b_{1} > \dots$ be the intermediate outputs of the Euclidean algorithm for $(a, b)$ . We begin by running the Euclidean algorithm on the left copy of $N_{a, b}$ . This takes ω steps. We then run two steps of the Euclidean algorithm on the right copy of $N_{a, b}$ , obtaining residual capacities $a_{1} > b_{1}$ for $ℓ_{3}$ and $ℓ_{4}$ , respectively. We next perform a recharging step (described below), and then re-run the (full) Euclidean algorithm on the left copy of $N_{a, b}$ . We then run another two steps of the Euclidean algorithm on the right copy of $N_{a, b}$ , obtaining residual capacities $a_{2} > b_{2}$ and proceed iteratively.

The Recharging Step. At the beginning of the nth recharging step the residual capacities of $ℓ_{1}, ℓ_{2}, ℓ_{3}$ and $ℓ_{4}$ are $0, 0, a_{n}$ and $b_{n}$ , respectively. We first use the two augmenting paths in Fig. 3 (shown by dashed arcs) to recharge the residual capacity of $ℓ_{1}$ without drastically changing the rest of the network. Observe that neither $e_{2}$ nor $e_{3}$ belong to the left or right copy of $N_{a, b}$ in $N_{a, b}^{2}$ . The arcs $e_{2}$ and $e_{3}$ will always have zero-flow except during this recharging step. By pushing flow along the two dashed augmenting paths, $c^{'} (ℓ_{1})$ becomes $a_{n}$ and $c^{'} (ℓ_{2}), c^{'} (ℓ_{3})$ and $c^{'} (ℓ_{4})$ are unchanged. Note that both $e_{2}$ and $e_{3}$ have zero-flow after the recharging step, as claimed. Similarly, using two augmenting paths similar to the dashed ones, we can recharge $c^{'} (ℓ_{2})$ to $b_{n}$ without changing $c^{'} (ℓ_{1}), c^{'} (ℓ_{3})$ , and $c^{'} (ℓ_{4})$ .

One easily checks that there is always sufficient flow along backward arcs to run the Euclidean algorithm on the right copy of $N_{a, b}$ and to perform the recharging steps. Furthermore, since a and b are incommensurate, $a_{n}$ and $b_{n}$ are also incommensurate for all n. Therefore, this run of Ford–Fulkerson on $N_{a, b}^{2}$ requires at least $ω^{2}$ steps. By Claim 1, the total flow after $ω^{2}$ steps is at most $\begin{matrix} 4 (a + b) + 4 \sum_{n = 0}^{\infty} (a_{n} + b_{n}) + 2 \sum_{n = 1}^{\infty} (a_{n} + b_{n}) ⩽ 14 (a + b), \end{matrix}$ where the first term corresponds to the Euclidean run on the right copy of $N_{a, b}$ , the second term corresponds to all the Euclidean runs on the sequence of left networks $N_{a_{0}, b_{0}}, N_{a_{1}, b_{1}}, \dots$ , and the third term corresponds to the total flow produced by the recharging steps.

We can therefore take $c (e) = 14 (a + b)$ for all $e \notin {ℓ_{1}, \dots, ℓ_{4}}$ . The proof is complete as it is straightforward to check that $N_{a, b}^{k}$ contains at most $25 k$ edges for all k. □

Figure 3.

A sequence of two augmenting paths that recharges the far left vertical edge is shown by dashed edges.

Note that our example for the lowerbound starts with the zero-flow, while our proof for the upperbound is valid starting with any initial flow.

5. Conclusion

In this paper, we determined the ordinal running-time of the Ford–Fulkerson algorithm exactly, up to a constant factor c in the exponent of ω. It is an interesting open question what the correct value of c is. Our upperbound gives $c ⩽ 1$ , while our lowerbound gives $c ⩾ \frac{1}{25}$ .

One possible moral of this story is that the original Ford–Fulkerson algorithm is actually correct; it simply requires transfinite time to terminate. Moreover, in some sense the running-time of $ω^{| E |}$ is very efficient (it converges on the ω scale). For example, a priori, it is possible that the algorithm would require $ω^{ω}$ steps.

Of course, it is possible to define and analyze the ordinal running-time of any non-terminating algorithm which converges to a limit. As far as we know, the only other example where this has been carried out is a result by Backman [1] on chip-firing [2] in metric graphs. Indeed, this was the impetus for our work, since chip-firing on metric graphs [16] and Ford–Fulkerson are in some sense “dual” to each other. Unfortunately, we were unable to find a single theorem which proves both results simultaneously.

Footnotes

Acknowledgements

This research was supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC Grant Agreement no. 279558. We would like to thank Matt Baker, Diane Maclagan, and Vic Reiner for each noting the similarity between the non-termination of Ford–Fulkerson and the non-termination of metric chip-firing. We also thank Marco Macchia for help with the figures.

References

Backman, Infinite reduction of divisors on metric graphs, European Journal of Combinatorics 35 (2014), 67–74. doi:10.1016/j.ejc.2013.06.024.

Backman, Riemann–Roch theory for graph orientations, Adv. Math. 309 (2017), 655–691. doi:10.1016/j.aim.2017.01.005.

Bak,

Tang and

Wiesenfeld, Self-organized criticality, Physical Review A 38(1) (1988), 364. doi:10.1103/PhysRevA.38.364.

Baker and

Norine, Riemann–Roch and Abel–Jacobi theory on a finite graph, Advances in Mathematics 215(2) (2007), 766–788. doi:10.1016/j.aim.2007.04.012.

N.L.

Biggs, Chip-firing and the critical group of a graph, Journal of Algebraic Combinatorics 9(1) (1999), 25–45. doi:10.1023/A:1018611014097.

Björner,

Lovász and

P.W.

Shor, Chip-firing games on graphs, European Journal of Combinatorics 12(4) (1991), 283–291. doi:10.1016/S0195-6698(13)80111-4.

W.J.

Cook,

W.H.

Cunningham,

W.R.

Pulleyblank and

Schrijver, Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1998, p. 355.

Dhar, Self-organized critical state of sandpile automaton models, Physical Review Letters 64(14) (1990), 1613–1616. doi:10.1103/PhysRevLett.64.1613.

Dinits, Algorithm of solution to problem of maximum flow in network with power estimates, Doklady Akademii Nauk SSSR 194(4) (1970), 754.

10.

Edmonds and

R.M.

Karp, Theoretical improvements in algorithmic efficiency for network flow problems, in: Combinatorial Structures and Their Applications, Proc. Calgary Internat. Conf., Calgary, Alta., 1969, Gordon and Breach, New York, 1970, pp. 93–96.

11.

Engel, The probabilistic abacus, Educational Studies in Mathematics 6(1) (1975), 1–22. doi:10.1007/BF00590021.

12.

L.R.

Ford Jr. and

D.R.

Fulkerson, Maximal flow through a network, Canad. J. Math. 8 (1956), 399–404. doi:10.4153/CJM-1956-045-5.

13.

J.D.

Hamkins and

Lewis, Infinite time Turing machines, J. Symbolic Logic 65(2) (2000), 567–604. doi:10.2307/2586556.

14.

Hladký,

Kráľ and

Norine, Rank of divisors on tropical curves, J. Combin. Theory Ser. A 120(7) (2013), 1521–1538. doi:10.1016/j.jcta.2013.05.002.

15.

Hrbacek and

Jech, Introduction to Set Theory, 3rd edn, Monographs and Textbooks in Pure and Applied Mathematics, Vol. 220, Marcel Dekker, Inc., New York, 1999, p. 291.

16.

Luo, Rank-determining sets of metric graphs, Journal of Combinatorial Theory, Series A 118(6) (2011), 1775–1793. doi:10.1016/j.jcta.2011.03.002.

17.

Mosesian, Strongly basable graphs, in: Akad. Nauk. Armian. SSR Dokl., Vol. 54, 1972, pp. 134–138.

18.

A.M.

Turing, Systems of logic based on ordinals, Proc. London Math. Soc. S2-45(1), 161. doi:10.1112/plms/s2-45.1.161.

19.

Zwick, The smallest networks on which the Ford–Fulkerson maximum flow procedure may fail to terminate, Theoret. Comput. Sci. 148(1) (1995), 165–170. doi:10.1016/0304-3975(95)00022-O.