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

<p>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 α). </p>

<p>Here is a PDF summing up my attempt : <a href="https://louis.jachiet.com/tmp/jQwbrkSMLNU_draft.pdf" rel="nofollow noreferrer">https://louis.jachiet.com/tmp/jQwbrkSMLNU_draft.pdf</a> (sorry it is a  bit laconic for the moment but don't hesitate for ask questions)</p>

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

CC BY-SA 3.0
2018-04-15T16:33:10.007Z
2018-04-15T16:33:10.007Z
Louis
<p>The answer is that for every irrational number $r$, there exists a network </p>

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

<p>This has been proved in the paper</p>

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

CC BY-SA 4.0
2023-08-05T19:53:07.213Z
Wow, that's a cool result!
Per Alexandersson
CC BY-SA 3.0
2018-04-16T12:44:23.230Z
2018-04-16T12:44:23.230Z
Gamow
<p>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 <em>wrong</em> 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 <span class="math-container">$\phi' = (\sqrt{5}-1)/2$</span>, and other values that are either rational, or are rational multiples of <span class="math-container">$\phi'$</span>. My main question is:</p>
<blockquote>
<p>General Question: What happens with other irrational values?</p>
</blockquote>
<p>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):</p>
<blockquote>
<ol>
<li><p>Given any <span class="math-container">$\alpha \in \mathbb{R}$</span>, can one construct (or even show existence of) such counterexamples?</p>
</li>
<li><p>More weakly: are there examples known that use an irrational value <em>essentially different</em> from <span class="math-container">$\phi'$</span>? That is, is there some <span class="math-container">$\alpha$</span> which is not a rational multiple of <span class="math-container">$\phi'$</span> (or more strongly not in <span class="math-container">$\mathbb{Q}(\phi')$</span>) and such that there are counterexamples to Ford-Fulkerson and/or Edmonds-Karp where all the weights lie in <span class="math-container">$\mathbb{Q}(\alpha)$</span>?</p>
</li>
<li><p>In the other direction, does there exist an irrational <span class="math-container">$\alpha$</span> such that Ford-Fulkerson (resp., Edmonds-Karp) halts with the correct value on <em>all graphs</em> whose weights are all from <span class="math-container">$\mathbb{Q} \cup \{q\alpha : q \in \mathbb{Q}\}$</span>? (Or more strongly, from <span class="math-container">$\mathbb{Q}(\alpha)$</span>?)</p>
</li>
</ol>
</blockquote>
<p>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.</p>
<p>(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.)</p>
<p><strong>References</strong></p>
<ul>
<li><p>A minimal counterexample for Ford-Fulkerson was given by <a href="https://doi.org/10.1016/0304-3975(95)00022-O" rel="nofollow noreferrer">Zwick TCS 1999</a></p>
</li>
<li><p>A counterexample for Edmonds-Karp was given by Queyranne or <a href="https://doi.org/10.1287/moor.5.2.258" rel="nofollow noreferrer">Queyranne Math. Oper. Res. 1980</a>, though I don't know if that one's minimal.</p>
</li>
<li><p>These can both be found in <a href="https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf" rel="nofollow noreferrer">Jeff Erickson's book</a>, with the first at the end of Section 10.4, and the second as Exercise 18 of Chapter 10.</p>
</li>
</ul>

<ds.algorithms><graph-algorithms><max-flow>
Counterexample to max-flow algorithms with irrational weights?
Joshua Grochow
# Counterexample to max-flow algorithms with irrational weights?

(Asked by: username_0 on 2018-04-12)

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**

* A minimal counterexample for Ford-Fulkerson was given by [Zwick TCS 1999](https://doi.org/10.1016/0304-3975(95)00022-O)
* A counterexample for Edmonds-Karp was given by Queyranne or [Queyranne Math. Oper. Res. 1980](https://doi.org/10.1287/moor.5.2.258), though I don't know if that one's minimal.
* These can both be found in [Jeff Erickson's book](https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf), with the first at the end of Section 10.4, and the second as Exercise 18 of Chapter 10.

**Tags:** ds.algorithms, graph-algorithms, max-flow

---

## 2 answers

### Answer by username_2 on 2018-04-16. Score: 17 | Accepted answer

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>

> **Comments:**
> **username_3**: Wow, that's a cool result!  

---

### Answer by username_1 on 2018-04-15. Score: -1

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.


---

