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 = (e1,...,ek), is the sum of weights of the edges: w(p) = w(e1) + ... + w(ek). 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 Hk(v) as the maximum cost of a path of length k from s to v; if no such path exists, then Hk(v) = minus infinity.
The main lemma says that the maximum mean cycle weight of G equals(*) max v ∈ V min 0 ≤ k ≤ n − 1 H n ( v ) − H k ( v ) n − k {\displaystyle \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 kv be the length of this maximum-cost path. Then Hkv(v) >= Hn(v), so the expression inside the min in (*) is at most 0 when k = kv. As kv <= 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 P0 be a maximum-cost path from s to w. For every t >= 1, let Pt be a concatenation of P0 with t copies of the cycle; as the cost of Pt equals the cost of P0, 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, Pt has a prefix of length n; it is a maximum-cost path from s to some node w'. Then Hn(w') >= Hk(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 Hk 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 Hn(v) and Hk(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
References
