Math Is Fun Forum

Complexity

Member

From: Denmark

Registered: 2013-12-27

Posts: 16

Negative cycles - Graph theory

Once again I have to ask for your help.
This time it is regarding the algorithm known as Cycle Canceling in which we start out by finding the maximum flow in a graph/network (which has integer capacities and integer weights). By a theorem (theorem 2 in my link below) we know, that if any negative cycles in the residual network of the graph exists, then we do not have the optimal solution, and therefore by sending flow through this negative cycle (canceling the cycle), this exact cycle will be removed, however a new might be created. My question is:
Can we be sure, that by 'canceling' one cycle we will achieve a total cost smaller than the previous cost?

I don't know if the above can be deduced from the theorems of the page below, I just need to know why above is the case, because that will be why we can expect a solution after a number of iterations.

EDIT: Since I am not an established member, I can't post the link, however a search for "cycle canceling topcoder" on google shows the link as the first option (in my case).

ShivamS

Member

Registered: 2011-02-07

Posts: 3,648

Re: Negative cycles - Graph theory

Are you asking for the proof of that theorem?

Complexity

Member

From: Denmark

Registered: 2013-12-27

Posts: 16

Re: Negative cycles - Graph theory

I am just wondering how all the sources I find regarding the cycle canceling claim this:
"Any cycle canceling decreases the objective function by a strictly positive amount."
(This, as far as I understand, claim that we reduce the cost of the flow after each iteration).

If there is a proof for it, then I am asking for it, however it just seems like it is implied in one of the theorems (and those theorems I have proofs for) and I am missing out on something.