Transfinite Ford–Fulkerson on a finite network

Article type: Research Article

Authors: Backman, Spencer^{a; *} | Huynh, Tony^b

Affiliations: [a] Institute of Mathematics, Goethe University, Frankfurt, Germany. backman@math.uni-frankfurt.de | [b] Département de Mathématique, Université libre de Bruxelles, Brussels, Belgium. tony.bourbaki@gmail.com

Correspondence: [*] Corresponding author. backman@math.uni-frankfurt.de.

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

DOI: 10.3233/COM-180082

Journal: Computability, vol. 7, no. 4, pp. 341-347, 2018