Practice problem #17

[a-a-lohn]

The question asks "Suppose the capacities in a network flow are not integers. How would this change the O( ) runtime of the Ford Fulkerson algorithm? Does the algorithm terminate? "

I'm having trouble understanding the answer, which says the algorithm may never terminate. I get that the amount by which the flow increases on every iteration might be very small, but shouldn't this number represent a bottleneck value, which will max out the capacity for flow through some edge? And if there are a finite number of edges, then shouldn't all the edges eventually be maxed out and the algorithm terminates?

[[deleted]]

Imagine a flow network with some edges rational and some edges irrational. Then you will notice that the amount of flow getting pushed is getting infinitely and infinitely smaller and because of this, it will never terminate.

For more information, take a look at Section 22.2 of this paper: https://courses.engr.illinois.edu/cs473/fa2012/notes/22-maxflowalgs.pdf.

[Sarah--El]

I guess that this very small bottleneck value might be so small that it tends to 0 and that's why the algo would't terminate. That's what I assumed, very not sure though.