0
$\begingroup$

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"?

Improve this question
$\endgroup$
6
  • $\begingroup$ Asking "do you know of papers that contain my idea?" probably aren't very useful. Instead, it's better to answer a technical question. What are you planning to do with those papers? What questions do you want to be able to answer, that you think you could answer if you could find those papers? $\endgroup$ – D.W.♦ Feb 7 '16 at 18:06
  • $\begingroup$ Incidentally, your claim that ~"in practice Wikipedia's counterexample does not work"~ is wrong. The example absolutely does work. It is a counterexample for a particular algorithm. You seem to have the idea that if you introduce a different algorithm, then that counterexample would no longer apply to your different algorithm. But that raises the question of whether there might be some other counterexample, and what properties can be proven of your proposed new algorithm. $\endgroup$ – D.W.♦ Feb 7 '16 at 18:07
  • $\begingroup$ """ What are you planning to do with those papers? """ To read achivements of people, who already thought about. To understand, is this topic already described... or it may become new publication. Also when I read lections about flows, I say "in theory FF should not terminate, should not work in polynomial time, but on real data it does...". And no more. For me it's insufficient. Let me correct the last term "FF always terminates" to "FF, implemented via dfs, always terminates". $\endgroup$ – Sergey Kopeliovich Feb 7 '16 at 19:40
  • 1
    $\begingroup$ IIRC, there is one in the original paper. $\endgroup$ – Raphael♦ Feb 7 '16 at 20:00
  • 1
    $\begingroup$ Your question is answered on cstheory: cstheory.stackexchange.com/a/5127/40. $\endgroup$ – Yuval Filmus Feb 7 '16 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.