title: A variation of Ford Fulkerson Algorithm
body: <blockquote>
    <p>Suppose that we redefine the residual network to disallow edges into <code>s</code>. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow.  </p>
  </blockquote>
  
  <p>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 <code>s</code> that means we are not allowing decrease in flow in edges <code>s- x</code> (<code>x</code> is the adjacent node to <code>s</code>). So in the case when we allow edges into <code>s</code> we can have a cycle like </p>
  
  <p><code>s to x_1 leadsto y leadsto x_2 to s to x_3 leadsto t</code>  </p>
  
  <p>But if we disallow edges into <code>s</code> again we can find the same path with out the cycle. All the above are intuitive ideas but I want a formal proof.  </p>
  
  <p>The question is from <em>Introduction to Algorithms</em> by Cormen et al.</p>