This is for the 454 class that is preparing for ICPC.

In discussing a maxflow algorithm I asked how adding a backward flow could be justified.  This slightly simplified version of Larry's example might help.

A -> B: 2

B -> D: 2

A -> C: 1

C -> D: 1

B -> C: 1

We want the maximal flow A --> D.

I suggest that you draw it out to see what this network looks like. It's similar to what we talked about in class. It's a diamond with a flow of 2 along the top, a flow of 1 along the bottom, and a link from the middle of the top to the middle of the bottom with a capacity of 1.

Clearly the maximum flow is 3. (The flow along the top + the flow along the bottom.) Note that there is no backward flow at all from C to B. 

The algorithm might find as its first flow A -> B -> C -> D: 1.  The only flow left is A -> B -> D: 1. That gives us a total flow of 2 , which is wrong since the answer should be 3. (The capacity A -> C: 1 is not used because the flow C -> D is taken..)

The way to get 3 is to add a flow C -> B: 1 when we use up the flow B -> C.

What is the justification for this? I believe the way to explain it is that in adding the backflow(s) we are making the decisions of each flow that we find non-deterministic. So, in effect the first flow A -> B -> C -> D also allows the decision made at B to go to C later to be reversed to go to D instead. So this is not a matter of extra capacity. (The original network has no C -> B capacity.) Creating an artificial one is a way of saying that the decision to direct the flow A -> B -> C -> D had another option at B and we want to make that available for later.

With the additional "backwards" flow, we can now generate A -> C -> B -> D: 1. With this additional flow we now have a total flow of 3, which is the right answer. Our three flows are: A -> B -> C -> D: 1; A -> B -> D: 1; and A -> C -> B -> D: 1. But look at the first and last flows. One includes B -> C; the other includes C -> B. In this case we have the same flow in both directions. So we can eliminate these links from the two flows and get  A -> B -> D: 1; and A -> C -> D: 1. In other words, we split the flows at the bidirectional link and have them exchange heads and tails. These new flows don't use the artificial backward link. The backward link just allowed us to find unused capacity, which appeared as the tail of a new flow.  We switched that tail with the tail of the first flow, and used the tail of the first flow as the tail of the new flow.