Consider Ford–Fulkerson algorithm (FF).
Look to wiki :
The following example shows the first steps of Ford–Fulkerson in a flow network with 4 nodes, source A and sink D. This example shows the worst-case behaviour of the algorithm. In each step, only a flow of 1 is sent across the network. If breadth-first-search were used instead, only two steps would be needed.
In practice this example does not work, because each vertex has fixed (determenistic) order of outgoing edges.
We've introduced simple test for "determenistic order of edges" with number of pathes $2^{n/4}$.
At beggining of FF you may shuffle all the edges. After it during the algorithm the order of the edges is immutable. The optimization breaks our simple test with $2^{n/4}$ pathes, but there is another test with subexponential number of pathes: $2^{n/(8logn)}$. More precisely: probability that "number of pathes is $2^{n/(8logn)}$" over all $m!$ shuffles of $m$ edges seeks to $1$ with $n$ seeks to $\infty$.
Look more to wiki:
Non-terminating example
If you use dfs with deterministic order of edges (as in practice!) then FF always terminates. Even for graphs with real capacities of edges.
Our question. Do you know papers, books, lection notes, which contain such tests and the proof of the proposition "FF, implemented via dfs, always terminates"?
