6.7.1.2. Finding the Cycle

Given \(\mu^*_f\), it remains to show how to find a cycle \(C\) whose mean cost is \(\mu^*_f\). Consider once again the adjusted edge costs

\[c^r_{x,y} = c^f_{x,y} - \mu^*_f,\]

which are easily computed in \(O(m)\) time once we have computed \(\mu^*_f\) using (6.11). As argued in the proof of Lemma 6.31, a minimum mean cost cycle has cost \(0\) with respect to these edge costs. Conversely, any cycle whose cost is \(0\) with respect to these edge costs must be a minimum mean cost cycle with respect to both the adjusted edge costs \(c^r\) and the original edge costs \(c^f\). Thus, it suffices to find a cost-\(0\) cycle with respect to \(c^r\).

We start by computing the shortest path distances \(d^r\) from \(s\) to all vertices in \(G^f\) with respect to the edge costs \(c^r\). Since there is no negative-cost cycle in \(G^f\) with respect to these edge costs, these distances are well defined. In particular,

\[d^r_x = \min_{0 \le i \le n-1} \left(\ell^{(i)}_x - i\mu^*_f\right).\]

Thus, these distances can be computed in \(O\bigl(n^2\bigr)\) time, given the shortest walk lengths \(\ell^{(0)}, \ldots, \ell^{(n-1)}\) computed as part of the computation of \(\mu^*_f\). As observed in the argument for the case when \(\mu^*_f = 0\) in the proof of Lemma 6.31, if we set \(\pi_x = -d^r_x\), then every edge in \(G^f\) has a non-negative reduced cost

\[c^\pi_{x,y} = c^r_{x,y} - \pi_x + \pi_y\]

and the reduced cost of every cycle is the same as its cost with respect to \(c^r\). Thus, a cycle has cost \(0\) if and only if every edge \((x,y)\) in the cycle has reduced cost \(0\), that is, if and only if \(d^r_y = d^r_x + c^r_{x,y}\). We can identify all edges in \(G^f\) that satisfy this condition in \(O(m)\) time, and then we run depth-first search to find a cycle in the resulting subgraph, which takes \(O(n + m)\) time. This cycle is the desired minimum mean cost cycle. Overall, finding this cycle takes \(O\bigl(n^2 + m\bigr) = O\bigl(n^2\bigr)\) time in addition to the cost of finding \(\mu^*_f\). Since we can find \(\mu^*_f\) in \(O(nm)\) time, we can thus find a minimum mean cost cycle in \(O(nm)\) time. This proves Lemma 6.30.