I have been assigned the question:

Let $G$ be a flow network and $f^*$ be the maximum flow computed by the Ford-Fulkerson algorithm. Consider a new flow network $G'$ constructed by increasing the capacity of exactly one of $G$'s edges by one.

Using the maximum-flow and minimum-cut theorem, argue that if we run the Ford-Fulkerson algorithm on $G'$ with $f^*$ as the initial flow, the while-loop shall terminate in at most one iteration.

But I feel like the loop can run more than once...

Considering a base case where $G$ has one edge between the sink and source with a capacity of 1.

Then $G'$ will have one edge with a capacity of 2.

So then when we run the Ford–Fulkerson algorithm with an initial flow of $f^* = 1$, the first loop will leave a residual graph with an edge with a capacity of 1, and therefore the loop will run for a second time.

  • 1
    $\begingroup$ So what's your question? $\endgroup$ – David Richerby Nov 14 '16 at 8:16
  • $\begingroup$ How many times will the Ford-Fulkerson Algorithm loop if there are ONLY source and sink vertices, and the inital augmented flow is < the capacity? (regarding my example) $\endgroup$ – Eric Nelson Nov 14 '16 at 9:07
  • $\begingroup$ This is a question-and-answer site, so we need you to explicitly articulate a specific question that you want answered. $\endgroup$ – D.W. Dec 4 '16 at 3:11

You are interpreting the question too literally. The question claims that only one augmentation step will be performed. In your example, we augment $f^*$ by pushing one more unit of flow, and then we reach the maximum flow of the updated network.


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