Lesson 7

If capacities are arbitrary real numbers and the augmenting paths are chosen badly, the Ford–Fulkerson method may run forever. Even worse, the flow values may converge to a number strictly smaller than the maximum flow.

Here is one classical example. Let \(X>2\) and let \(\rho = \frac{\sqrt{5} - 1}{2}\). We will use the identities \(\rho^{2}=1-\rho\) and \(\rho+\rho^{2}=1\).

The picture below is the initial network. The cut \(\{s,a,b\}\) has capacity \(2X+1\), and this value can be achieved by sending \(X\) units through \(s\to a\to t\), \(X\) units through \(s\to d\to t\), and \(1\) unit through \(s\to b\to c\to t\). Hence the maximum flow value is \(2X+1\).

Now choose augmenting paths in the following unfortunate way. First send \(1\) unit along \[P_{0}:\; s\to b\to c\to t.\] This saturates \(b\to c\), so the residual network receives the reverse edge \(c\to b\) of capacity \(1\).

After that, for each odd \(i=1,3,5,…\), repeat the following four augmentations: \[\begin{align*}P_{1}(i)&:\; s\to d\to c\to b\to a\to t,&&\Delta=\rho^{i}, \\ P_{2}(i)&:\; s\to b\to c\to d\to t,&&\Delta=\rho^{i}, \\ P_{3}(i)&:\; s\to d\to c\to b\to a\to t,&&\Delta=\rho^{i+1}, \\ P_{4}(i)&:\; s\to a\to b\to c\to t,&&\Delta=\rho^{i+1}.\end{align*}\] Here \(\Delta\) is the bottleneck capacity of the chosen residual path. The first block is shown below. Red edges are reverse residual edges created by previous augmentations.

The reason the construction works is that after these four augmentations the same situation repeats with powers of \(\rho\) shifted by two. The identities \(\rho^{2}=1-\rho\) and \(\rho+\rho^{2}=1\) make the bottlenecks come out exactly as written above. Thus the algorithm really has an infinite sequence of augmenting paths.

The total flow value after the first augmentation is \(1\). Then the blocks add \[2\rho+2\rho^{2}+2\rho^{3}+2\rho^{4}+\dotsb,\] so the values converge to \[1+\sum_{k=1}^{\infty}2\rho^{k}=1+\frac{2\rho}{1-\rho}=2+\sqrt{5}\approx 4.236.\] Since \(X>2\), the maximum flow value is \(2X+1>5\). Therefore the algorithm does not merely take infinitely many steps; with arbitrary real capacities and bad choices of paths, it may fail to converge to an optimal flow value.