A shortest cycle for each vertex of a graph

We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs.We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n   vertices and integer weights in 1,…,M1,…,M, it runs in O˜(Mn(ω+3)/2) time where ω<2.376ω<2.376 is the exponent of matrix multiplication. As a by-product, our algorithm can be used to determine which vertices lie on cycles of length at most t   in O˜(Mnωt) time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of ϵ   in O˜(n(ω+6)/3) time.

► We design an algorithm that finds a shortest containing cycle for each graph vertex. ► A randomized algorithm for the undirected case runs in O(M1/2n2.688)O(M1/2n2.688) time. ► For bounded real weights, a variant algorithm solves the problem slightly slower. ► The variant achieves an additive error of ϵ   in O(n2.792)O(n2.792) time.