Karps minimum mean-weight cycle algorithm Let G D .V; E/

Chapter 24, Problem 24-5

(choose chapter or problem)

Karps minimum mean-weight cycle algorithm Let G D .V; E/ be a directed graph with weight function w W E ! R, and let n D jV j. We define the mean weight of a cycle c D he1; e2;:::;eki of edges in E to be .c/ D 1 k X k iD1 w.ei/ : Let D minc .c/, where c ranges over all directed cycles in G. We call a cycle c for which .c/ D a minimum mean-weight cycle. This problem investigates an efficient algorithm for computing . Assume without loss of generality that every vertex 2 V is reachable from a source vertex s 2 V . Let .s; / be the weight of a shortest path from s to , and let k.s; / be the weight of a shortest path from s to consisting of exactly k edges. If there is no path from s to with exactly k edges, then k.s; / D 1. a. Show that if D 0, then G contains no negative-weight cycles and .s; / D min0 k n1 k.s; / for all vertices 2 V . b. Show that if D 0, then max 0 k n1 n.s; / k.s; / n k 0 for all vertices 2 V . (Hint: Use both properties from part (a).) c. Let c be a 0-weight cycle, and let u and be any two vertices on c. Suppose that D 0 and that the weight of the simple path from u to along the cycle is x. Prove that .s; / D .s; u/ C x. (Hint: The weight of the simple path from to u along the cycle is x.) d. Show that if D 0, then on each minimum mean-weight cycle there exists a vertex such that max 0 k n1 n.s; / k.s; / n k D 0 : (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 D 0, then min 2V max 0 k n1 n.s; / k.s; / n k D 0 : f. Show that if we add a constant t to the weight of each edge of G, then increases by t. Use this fact to show that D min 2V max 0 k n1 n.s; / k.s; / n k : g. Give an O.VE/-time algorithm to compute .