Max flow algorithm running time

Question

I have the following two questions.

1. True or false: We can always find a sequence of flow augmenting s-t paths in the Ford-Fulkerson algorithm such that we reach the maximum flow in a polynomial number of iterations.
2. True or false: We can always find a sequence of flow augmenting s-t paths in the Ford-Fulkerson algorithm such that we reach the maximum flow only after an exponential number of iterations.

Answer 1

The first answer is definitely false. Because the running time of the Ford-Fulkerson algorithm is not polynomial - it's exponential.

Hence in order to find all s-t paths to reach the maximum flow will take exponential time.

The running time of the Ford-Fulkerson algorithm is O(nV), more precisely O((n+m)V), where n is the number of nodes, m is the number of edges in the graph. And V is the maximum capacity the graph is having.

Hence, it might look like a polynomial time algorithm. However, if V is large and let us assume that this large number can be expressed as 2^k, then the running time becomes O(n. 2^k) - which is exponential.

The second answer is not true in some cases as well, but mostly true if you are considering integer/rational numbers for the capacity values in the graph. We know that the algorithm takes exponential time - there is no problem with that. However, if the capacity values of the graph are irrational, then the Ford-Fulkerson algorithm does not guarantee to terminate. Hence the second statement is somewhat false as well. However, it is true for most of the cases as in most cases, the capacities are either integer or rational values.