Your friends have written a very fast piece of maximum-flow code based on repeatedly finding augmenting paths as in Section 7.1. However, after you’ve looked at a bit of output from it, you realize that it’s not always finding a flow of maximum value. The bug turns out to be pretty easy to find; your friends hadn’t really gotten into the whole backward-edge thing when writing the code, and so their implementation builds a variant of the residual graph that only includes the forward edges. In other words, it searches for s-t paths in a graph Gf consisting only of edges e for which f(e) < ce, and it terminates when there is no augmenting path consisting entirely of such edges. We’ll call this the Forward-Edge-Only Algorithm. (Note that we do not try to prescribe how this algorithm chooses its forward-edge paths; it may choose them in any fashion it wants, provided that it terminates only when there are no forward-edge paths.) It’s hard to convince your friends they need to reimplement the code. In addition to its blazing speed, they claim, in fact, that it never returns a flow whose value is less than a fixed fraction of optimal. Do you believe this? The crux of their claim can be made precise in the following statement.
There is an absolute constant b > 1 (independent of the particular input flow network), so that on every instance of the Maximum-Flow Problem, the Forward-Edge-Only Algorithm is guaranteed to find a flow of value at least 1/b times the maximum-flow value (regardless of how it chooses its forward-edge paths).
Decide whether you think this statement is true or false, and give a proof of either the statement or its negation.
Be sure to include:
an explanation of what the maximum flow in your graph is;
a sequence of paths that, if chosen by Ford-Fulkerson, leads to non-optimal flow;
an explanation of why there are no more paths of positive residual capacity after that sequence of paths when you omit backward edges from the residual graph; and
an explanation of how to generalize the above so that you end up with an arbitrarily small ratio of found flow to maximum flow.