1
$\begingroup$

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.

$\endgroup$
  • 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
0
$\begingroup$

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.

$\endgroup$

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