Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow.

I was thinking that when we augment a path the residual capacity of reverse edge increases and can be used to decrease the flow in that edge (but overall increase the network flow) if needed. So if we disallow the edges into $s$ that means we are not allowing decrease in flow in edges $s\to x$ ($x$ is the adjacent node to $s$). So in the case when we allow edges into $s$ we can have a cycle like

$\qquad \displaystyle s \to x_1 \leadsto y \leadsto x_2 \to s \to x_3 \leadsto t$.

But if we disallow edges into $s$ again we can find the same path with out the cycle. All the above are intuitive ideas but I want a formal proof.

The question is from Introduction to Algorithms by Cormen et al.

  • 2
    $\begingroup$ Do you have an argument for why increasing the flow along the cycle can never be fruitful? $\endgroup$ – Raphael Sep 2 '12 at 13:18
  • 1
    $\begingroup$ @Raphael very good question you have raised. I have thought the same question after I wrote the question but didn't edited it. Well I think - let there be any edge $e \in C \( C = \{e : e \in s\rightarrow x_1 \rightsquigarrow y \rightsquigarrow x_2 \rightarrow s \})$ which we are going to augment, after augmentation that cycle will vanish and we are left with the remaining path($s \rightarrow x_3 \rightsquigarrow t$) an again we will augment it. And this whole procedure will have the same effect of augmenting the path without the cycle (i.e. $s\rightarrow x_3 \rightsquigarrow t$). $\endgroup$ – justice league Sep 2 '12 at 19:04
  • 1
    $\begingroup$ For reference to others: this problem appears in CLRS Introduction to Algorithms: Third Edition as problem 26.2-8 on p. 731, which offers useful context for the direction the framers of the problem intended us to go with this. Since this is a common homework problem (homework policy: meta.cs.stackexchange.com/questions/460/… ), @Raphael offers a useful hint, above. In fact, the chapter offers everything you need to form a solution. :) $\endgroup$ – MrGomez Sep 7 '12 at 18:50
  • $\begingroup$ @MrGomez I have tried to answer Raphael question. Is my reasoning correct?? $\endgroup$ – justice league Sep 16 '12 at 3:34
  • 1
    $\begingroup$ @justiceleague, would you like to answer your own question? $\endgroup$ – Merbs Nov 29 '12 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.