A variation of Ford Fulkerson Algorithm

Question

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- x (x is the adjacent node to s). So in the case when we allow edges into s we can have a cycle like

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.

Answer 1

I think your intuitive ideas are already quite enough for a proof. Let's consider two graphs: in a graph G1 we allow edges into s, and in a graph G2 we do not.

Now, suppose the Ford-Fulkerson algorithm finds a larger flow in G1 then it does in G2. As all augmenting paths in G2 are also valid in G1, we can use the same augmenting paths on both graphs for as long as possible, and then obtain a state for the residual network in which there is an augmenting path in G1, but not in G2.

However, as you pointed out, any augmenting path that is valid in G1 is also valid in G2, provided that we remove every edge that comes before the last visit to s. Therefore our assumption is wrong and such a situation cannot exist -- Ford-Fulkerson will produce the same output on both G1 and G2.