Minimum mean weight cycle

In graph theory, a minimum mean weight cycle is a cycle whose average weight (total weight divided by length) is smallest among all cycles in the graph. An analogous problem is the maximum mean weight cycle. These problems have applications to embedded systems and logic chip design.

Definitions

Let G = (V,E) be a directed graph in which each edge has a weight (positive or negative). The weight of any path or cycle p = (e₁,...,e_k), is the sum of weights of the edges: w(p) = w(e₁) + ... + w(e_k). The mean weight of p is the weight of p divided by the number of edges in it: w(p)/len(p).

The minimum cycle mean weight in G is the minimum, over all directed cycles p in G, of w(p)/len(p). A minimum mean weight cycle is any cycle with the minimum mean weight.

Algorithms

Lawler presented an algorithm for computing a minimum mean weight cycle using O(log |V|) calls to an algorithm for solving the negative cycle problem. There exists such an algorithm that runs in time O(|V||E|), so the total runtime of Lawler's algorithm is O(|E||V|log |V|).

Karp's algorithm

Karp presented a characterization of the minimum cycle mean weight, and presented an algorithm that runs in time O(|V||E|). An analogous algorithm can be used for finding a maximum mean weight cycle.

Let G be any directed graph, and let s be a fixed vertex in G. For every nonnegative integer k and every vertex v in G, define H_k(v) as the maximum cost of a path of length k from s to v; if no such path exists, then H_k(v) = minus infinity.

The main lemma says that the maximum mean cycle weight of G equals

(*) $\max _{v\in V}\min _{0\leq k\leq n-1}{\frac {H_{n}(v)-H_{k}(v)}{n-k}}$

Proof. It is sufficient to prove the lemma for the case in which the maximum mean cycle weight equals 0. This is because adding a constant weight to each edge adds the same constant both to the maximum mean cycle cost and to the expression in (*).

Suppose the maximum mean cycle weight is 0. Then there is a cycle with cost exactly 0, but no cycles with a positive cost.

We first prove that (*) is at most 0. As G has no positive-cost cycles, for every node v, there is a maximum-cost path of length smaller than n from s to v. Let k_v be the length of this maximum-cost path. Then H_kv(v) >= H_n(v), so the expression inside the min in (*) is at most 0 when k = k_v. As k_v <= n-1, the minimum in (*) is at most 0. As this holds for every node v, the maximum in (*) is at most 0 too.

We now prove that (*) is at least 0. G has a zero-cost cycle; let w be some node in that cycle. Let P₀ be a maximum-cost path from s to w. For every t >= 1, let P_t be a concatenation of P₀ with t copies of the cycle; as the cost of P_t equals the cost of P₀, it is also a maximum-cost path from s to w.  Every prefix of a maximum-cost path is also a maximum-cost path from s to its endpoint. When t is sufficiently large, P_t has a prefix of length n; it is a maximum-cost path from s to some node w'. Then H_n(w') >= H_k(w') for all k, so the expression inside the min in (*) is at least 0 for all k, so the minimum in (*) is at least 0. Taking v=w' in the maximum shows that the maximum in (*) is at least 0 too.

Therefore, when the maximum mean cycle cost is 0, (*) equals 0, which is sufficient to complete the proof.

It is possible to compute H_k using dynamic programming in time O(|E||V|); then it is possible to find the maximum mean cycle weight using (*). The cycle itself can be found as follows:

• Find the maximizing v and the minimizing k in (*).
• As the outcome for this v and this k is finite, both H_n(v) and H_k(v) are finite. This means that there exists a maximum-weight path of length n from s to v, and a maximum-weight path of length k from s to v. Therefore, the path of length n contains a cycle of length n-k; this is the maximum mean weight cycle.

Chaturvedi and McConnell identified an error in Karp's algorithm for constructing a cycle attaining the minimum mean weight. They presented a corrected algorithm.

Newer algorithms

Dasdan and Gupta study maximum mean weight cycle, and present an algorithm that is provably always faster than Karp's algorithm.

Albrecht, Korte, Schietke and Vygen relate the problem of maximum mean weight cycle to the minimum balance problem: find a potential function such that the "slacks" of all edges are optimally balanced. Both problems can be solved by a parametric shortest path algorithm. They show that parametric shortest path can be used for solving more general variants of these problems, with constraints that are relevant to optimizing the clock schedule of a logic chip.

See also

• Negative cycle