24-5 Karp's minimum mean-weight cycle algorithm

Let $G = (V, E)$ be a directed graph with weight function $w: E \to \mathbb R$, and let $n = |V|$. We define the mean weight of a cycle $c = \langle e_1, e_2, \ldots, e_k \rangle$ of edges in $E$ to be

$$\mu(c) = \frac{1}{k} \sum_{i = 1}^k w(e_i).$$

Let $\mu^* = \min_c \mu(c)$, where $c$ ranges over all directed cycles in $G$. We call a cycle $c$ for which $\mu(c) = \mu^*$ a minimum mean-weight cycle. This problem investigates an efficient algorithm for computing $\mu^*$.

Assume without loss of generality that every vertex $v \in V$ is reachable from a source vertex $s \in V$. Let $\delta(s, v)$ be the weight of a shortest path from $s$ to $v$, and let $\delta_k(s, v)$ be the weight of a shortest path from $s$ to $v$ consisting of exactly $k$ edges. If there is no path from $s$ to $v$ with exactly $k$ edges, then $\delta_k(s, v) = \infty$.

a. Show that if $\mu^* = 0$, then $G$ contains no negative-weight cycles and $\delta(s, v) = \min_{0 \le k \le n - 1} \delta_k(s, v)$ for all vertices $v \in V$.

b. Show that if $\mu^* = 0$, then

$$\max_{0 \le k \le n - 1} \frac{\delta_n(s, v) - \delta_k(s, v)}{n - k} \ge 0$$

for all vertices $v \in V$. ($\textit{Hint:}$ Use both properties from part (a).)

c. Let $c$ be a $0$-weight cycle, and let $u$ and $v$ be any two vertices on $c$. Suppose that $\mu^* = 0$ and that the weight of the simple path from $u$ to $v$ along the cycle is $x$. Prove that $\delta(s, v) = \delta(s, u) + x$. ($\textit{Hint:}$ The weight of the simple path from $v$ to $u$ along the cycle is $-x$.)

d. Show that if $\mu^* = 0$, then on each minimum mean-weight cycle there exists a vertex $v$ such that

$$\max_{0 \le k \le n - 1} \frac{\delta_n(s, v) - \delta_k(s, v)}{n - k} = 0.$$

($\textit{Hint:}$ Show how to extend a shortest path to any vertex on a minimum meanweight cycle along the cycle to make a shortest path to the next vertex on the cycle.)

e. Show that if $\mu^* = 0$, then

$$\min_{v \in V} \max_{0 \le k \le n - 1} \frac{\delta_n(s, v) - \delta_k(s, v)}{n - k} = 0.$$

f. Show that if we add a constant $t$ to the weight of each edge of $G$, then $\mu^*$ increases by $t$. Use this fact to show that

$$\mu^* = \min_{v \in V} \max_{0 \le k \le n - 1} \frac{\delta_n(s, v) - \delta_k(s, v)}{n - k}.$$

g. Give an $O(VE)$-time algorithm to compute $\mu^*$.

a. If $\mu^* = 0$, then we have that the lowest that $\frac{1}{k}_{i = 1}^k w(e_i)$ can be zero. This means that the lowest $\sum_{i = 1}^k w(e_i)$ can be $0$. This means that no cycle can have negative weight. Also, we know that for any path from $s$ to $v$, we can make it simple by removing any cycles that occur. This means that it had a weight equal to some path that has at most $n - 1$ edges in it. Since we take the minimum over all possible number of edges, we have the minimum over all paths.

b. To show that

$$\max_{0 \le k \le n - 1} \frac{\delta_n(s, v) - \delta_k(s, v)}{n - k} \ge 0,$$

we need to show that

$$\max_{0 \le k \le n - 1} \delta_n(s, v) - \delta_k(s, v) \ge 0.$$

Since we have that $\mu^* = 0$, there aren't any negative weight cycles. This means that we can't have the minimum cost of a path decrease as we increase the possible length of the path past $n - 1$. This means that there will be a path that at least ties for cheapest when we restrict to the path being less than length $n$. Note that there may also be cheapest path of longer length since we necessarily do have zero cost cycles. However, this isn't guaranteed since the zero cost cycle may not lie along a cheapest path from $s$ to $v$.

c. Since the total cost of the cycle is $0$, and one part of it has cost $x$, in order to balance that out, the weight of the rest of the cycle has to be $-x$. So, suppose we have some shortest length path from $s$ to $u$, then, we could traverse the path from $u$ to $v$ along the cycle to get a path from $s$ to $u$ that has length $\delta(s, u) + x$. This gets us that $\delta(s, v) \le \delta(s, u) + x$.

To see the converse inequality, suppose that we have some shortest length path from $s$ to $v$. Then, we can traverse the cycle going from $v$ to $u$. We already said that this part of the cycle had total cost $-x$. This gets us that $\delta(s, u) \le \delta(s, v) - x$. Or, rearranging, we have $\delta(s, u) + x \le \delta(s, v)$. Since we have inequalities both ways, we must have equality.

d. To see this, we find a vertex $v$ and natural number $k \le n - 1$ so that $\delta_n(s, v) - \delta_k(s, v) = 0$. To do this, we will first take any shortest length, smallest number of edges path from $s$ to any vertex on the cycle. Then, we will just keep on walking around the cycle until we've walked along $n$ edges. Whatever vertex we end up on at that point will be our $v$. Since we did not change the $d$ value of $v$ after looking at length $n$ paths, by part (a), we know that there was some length of this path, say $k$, which had the same cost. That is, we have $\delta_n(s, v) = \delta_k(s,v)$.

e. This is an immediate result of the previous problem and part (b). Part (a) says that the inequality holds for all $v$, so, we have

$$\min_{v \in V} \max_{0 \le k \le n - 1} \frac{\delta_n(s, v) - \delta(s, v)}{n - k} \ge 0.$$

The previous part says that there is some $v$ on each minimum weight cycle so that

$$\max_{0 \le k \le n - 1} \frac{\delta_n(s, v) - \delta(s, v)}{n - k} = 0,$$

which means that

$$\min_{v \in V} \max_{0 \le k \le n - 1} \frac{\delta_n(s, v) - \delta_k(s, v)}{n - k} \le 0.$$

Putting the two inequalities together, we have the desired equality.

f. If we add $t$ to the weight of each edge, the mean weight of any cycle becomes

$$\mu(c) = \frac{1}{k} \sum_{i = 1}^k (w(e_i) + t) = \frac{1}{k} \Big(\sum_i^k w(e_i) \Big) + \frac{kt}{k} = \frac{1}{k} \Big(\sum_i^k w(e_i) \Big) + t.$$

This is the original, unmodified mean weight cycle, plus $t$. Since this is how the mean weight of every cycle is changed, the lowest mean weight cycle stays the lowest mean weight cycle. This means that $\mu^*$ will increase by $t$. Suppose that we first compute $\mu^*$. Then, we subtract from every edge weight the value $\mu^*$. This will make the new $\mu^*$ equal zero, which by part (e) means that

$$\min_{v \in V} \max_{0 \le k \le n - 1} \frac{\delta_n(s, v) - \delta_k(s, v)}{n - k} = 0.$$

Since they are both equal to zero, they are both equal to each other.

g. By the previous part, it suffices to compute the expression on the previous line. We will start by creating a table that lists $\delta_k(s, v)$ for every $k \in \{1, \ldots, n\}$ and $v \in V$. This can be done in time $O(V(E + V))$ by creating a $|V|$ by $|V|$ table, where the $k$th row and vth column represent $\delta_k(s, v)$ when wanting to compute a particular entry, we need look at a number of entries in the previous row equal to the in degree of the vertex we want to compute.

So, summing over the computation required for each row, we need $O(E + V)$. Note that this total runtime can be bumped down to $O(VE)$ by not including in the table any isolated vertices, this will ensure that $E \in \Omega(V)$. So, $O(V(E + V))$ becomes $O(VE)$. Once we have this table of values computed, it is simple to just replace each row with the last row minus what it was, and divide each entry by $n - k$, then, find the min column in each row, and take the max of those numbers.