9
$\begingroup$

It is known that Ford-Fulkerson or Edmonds-Karp with the fat pipe heuristic (two algorithms for max-flow) need not halt if some of the weights are irrational. In fact, they can even converge on the wrong value! However, all the examples I could find in the literature [references below, plus references therein] use just a single irrational value: the conjugate golden ratio $\phi' = (\sqrt{5}-1)/2$, and other values that are either rational, or are rational multiples of $\phi'$. My main question is:

General Question: What happens with other irrational values?

For example (but don't feel like you have to answer all of these to post - I'd find interesting an answer to any one, or to other questions that fall under the above general question):

  1. Given any $\alpha \in \mathbb{R}$, can one construct (or even show existence of) such counterexamples?

  2. More weakly: are there examples known that use an irrational value essentially different from $\phi'$? That is, is there some $\alpha$ which is not a rational multiple of $\phi'$ (or more strongly not in $\mathbb{Q}(\phi')$) and such that there are counterexamples to Ford-Fulkerson and/or Edmonds-Karp where all the weights lie in $\mathbb{Q}(\alpha)$?

  3. In the other direction, does there exist an irrational $\alpha$ such that Ford-Fulkerson (resp., Edmonds-Karp) halts with the correct value on all graphs whose weights are all from $\mathbb{Q} \cup \{q\alpha : q \in \mathbb{Q}\}$? (Or more strongly, from $\mathbb{Q}(\alpha)$?)

In all cases, I want to assume something like the real RAM model, so that exact arithmetic and exact comparisons of real numbers are done in constant time.

(There are other max-flow algorithms that are known to run in strongly polynomial time, even with arbitrary real weights, which is perhaps why this type of question may not have been further explored. But having just taught these algorithms in my undergrad algorithms class, I'm still curious about this.)

References

$\endgroup$
12
$\begingroup$

The answer is that for every irrational number $r$, there exists a network

  • with $n=6$ vertices and $m=8$ arcs,
  • in which seven arcs have integer capacity,
  • in which one arc has capacity $r$,
  • and on which Ford-Fulkerson may fail to terminate.

This has been proved in the paper

Toshihiko Takahashi:
"The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate"
Journal of Information Processing 24, pp 390-394, 2016.
Link: https://www.jstage.jst.go.jp/article/ipsjjip/24/2/24_390/_article

$\endgroup$
-1
$\begingroup$

Thank you for the question that I found not really natural but quite amusing none the less.

I have looked into the Ford-Ferkulson part and I think I have found a graph that is a counter-example and has only one edge with irrational capacity α (the graph can work for any α).

Here is a PDF summing up my attempt : https://louis.jachiet.com/tmp/jQwbrkSMLNU_draft.pdf (sorry it is a bit laconic for the moment but don't hesitate for ask questions)

Obviously the Ford-Felkurson lets us choose augmenting path as we wish... I have not sure this would be possible for Edmond-Karp.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.