Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners

The girth of a graph, i.e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and girth-related structures in directed weighted m-edge and n-node graphs require Ω(min{nω, mn}) time (for 2 ≤ ω > 2.373). In this paper, we drastically improve these runtimes as follows: