How can a directed cycle exist in the residual graph of a Bipartite Flow Network with a perfect matching?

Question

I am studying the analysis of algorithms. I am currently reading on Network Flow algorithms. I am considering an application of Network Flow algorithms concerning finding bipartite matchings of minimum cost.

• Let G with corresponding Network Flow G'
• Let M be a perfect matching in G
• Let G<sub>M</sub> be the residual graph associated with this matching

From Jon Kleinberg and Eva Tardos' Algorithm Design 7.13 on page 406,

Theorem 7.62 states:

(7.62) Let M be a perfect matching. If there is a negative-cost directed cycle C in G_M, then M is not minimum cost

This theorem makes sense however, I am confused as to how a bipartite flow network's residual graph of a perfect matching can actually contain a cycle. The only way I could see a cycle is if the sink or source were involved.

However in a perfect matching the source would contain no edges leaving it, and the sink would contain no edges entering it. Also, a cycle occurring in the inner nodes would seem to contradict the definition of a Bipartite graph.

Can someone provide an example of such a cycle in the residual graph?

Answer 1

Sure. Consider the graph where a = cost and c = capacity:

  a=3,c=1
Ao----->oB
  \    ^
   \  /a=1,c=1
    \/
    /\
   /  \a=1,c=1
  /    v
Co----->oD
  a=3,c=1

So there are obviously 2 possible max flows. One uses the horizontal edges and the other the diagonals.

For the flow along the horizontals, we have a residual graph:

  a=-3,c=1
Ao<-----oB
  \    ^
   \  /a=1,c=1
    \/
    /\
   /  \a=1,c=1
  /    v
Co<-----oD
 a=-3,c=1

Notice the cycle B->A->D->C with capacity 1 and cost -3 + 1 -3 + 1 = -4.

The intuitive explanation for this cycle is that every increase in flow of one unit going along the edges in the cycle - or conversely every decrease in flow going along its edges in the opposite direction - we will decrease total cost of flow by 4 because we will be substituting flow along the cheaper diagonal edges for flow along the comparatively expensive horizontal edges.

In the augmenting path algorithm for min cost flow, we'd go ahead and push 1 unit of flow along this cycle and end up with a new, cheaper flow along the diagonals. This would provide the new residual graph:

  a=3,c=1
Ao----->oB
  ^    /
   \  /a=-1,c=1
    \/
    /\
   /  \a=-1,c=1
  v    \
Co----->oD
  a=3,c=1

Now the cycle is A->B->C->D and has cost 3 - 1 + 3 - 1 = 4, so the max flow along diagonals is a min cost max flow.