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):
Given any $\alpha \in \mathbb{R}$, can one construct (or even show existence of) such counterexamples?
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)$?
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
A minimal counterexample for Ford-Fulkerson was given by Zwick TCS 1999
A counterexample for Edmonds-Karp was given by Queyranne or Queyranne Math. Oper. Res. 1980, though I don't know if that one's minimal.
These can both be found in Jeff Erickson's book, with the first at the end of Section 10.4, and the second as Exercise 18 of Chapter 10.
