Abstract-We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a weighted graph. In particular, we show that the minimum weight cycle problem in an undirected n-node graph with edge weights in {1, . . . , M } or in a directed n-node graph with edge weights in {−M, . . . , M } and no negative cycles can be efficiently reduced to finding a minimum weight triangle in an Θ(n)−node undirected graph with weights in {1, . . . , O(M )}. Roughly speaking, our reductions imply the following surprising phenomenon: a minimum cycle with an arbitrary number of weighted edges can be "encoded" using only three
However, it was shown in REF that the minimum weight cycle problem in directed graphs can be reduced to the problem of finding a minimum triangle in an undirected graph which implies that the minimum weight cycle in directed graphs can be computed inÕ(M n ω ) time, improving the original result.
Minimum Weight Cycles and Triangles: Equivalences and Algorithms
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
Mathematics Computer Science