6.7.2. Bounding the Number of Iterations

Lemma 6.30 provides the means to implement each iteration of the minimum mean cycle cancelling algorithm in \(O(nm)\) time. To analyze the running time of the algorithm, we have to determine how many cycle cancellations it carries out. Bounding the number of cycle cancellations requires some care. We structure this argument as follows:

Let \(f^{(0)}\) be the initial feasible flow the algorithm starts with, and let \(f^{(1)}, \ldots, f^{(t)}\) be the sequence of flows produced by cycle cancellations. \(f^{(t)}\) is the final minimum-cost flow returned by the algorithm. For all \(0 \le i \le t-1\), let \(C^{(i)}\) be the minimum mean cost cycle in \(G^{f^{(i)}}\) cancelled to produce \(f^{(i+1)}\).

Ideally, we would like to make steady progress towards having no negative cycle: We would like that

\[\mu^*_{f^{(0)}} < \cdots < \mu^*_{f^{(t)}} = 0.\]

Unfortunately, this is not necessarily the case. Our first step towards bounding the running time of the algorithm is to show that none of the cycle cancellations makes things worse:

\[\mu^*_{f^{(0)}} \le \cdots \le \mu^*_{f^{(t)}}.\]

The second step is to prove that every now and then, we do actually make progress. Specifically, we show that after every \(m\) cycle cancellations, \(\mu^*_f\) increases by a factor of at least \(1 - \frac{1}{n}\). Since \(\mu^*_f < 0\) as long as the algorithm does not terminate, this is indeed an increase.

This will allow us to prove a preliminary bound on the number of cycle cancellations of \(O(nm\lg(nC))\) if the input graph has integral edge costs between \(-C\) and \(C\). Thus, the algorithm runs in \(O\bigl(n^2m^2\lg(nC)\bigr)\) time for such inputs.

The final step in the proof is to show that after every \(nm\lg(2n)\) cycle cancellations, at least one edge gets "fixed" in the sense that we no longer send any flow along this edge during the remaining iterations of the algorithm. Since there are only \(m\) edges in \(G\), we run out of edges along which we can send flow after at most \(nm^2\lg(2n)\) cycle cancellations. Since each cycle cancellation takes \(O(nm)\) time, we obtain our final bound of \(O\bigl(n^2m^3\lg n\bigr)\) on the running time of the algorithm.