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 $Omega(min{n^{omega}, mn})$ time (for $2leqomega<2.373$). In this paper, we drastically improve these runtimes as follows: * Multiplicative Approximations in Nearly Linear Time: We give an algorithm that in $widetilde{O}(m)$ time computes an $widetilde{O}(1)$-multiplicative approximation of the girth as well as an $widetilde{O}(1)$-multiplicative roundtrip spanner with $widetilde{O}(n)$ edges with high probability (w.h.p). * Nearly Tight Additive Approximations: For unweighted graphs and any $alpha in (0,1)$ we give an algorithm that in $widetilde{O}(mn^{1 - alpha})$ time computes an $O(n^alpha)$-additive approximation of the girth w.h.p, and partially derandomize it. We show that the runtime of our algorithm cannot be significantly improved without a breakthrough in combinatorial Boolean matrix multiplication. Our main technical contribution to achieve these results is the first nearly linear time algorithm for computing roundtrip covers, a directed graph decomposition concept key to previous roundtrip spanner constructions. Previously it was not known how to compute these significantly faster than $Omega(min{n^omega, mn})$ time. Given the traditional difficulty in efficiently processing directed graphs, we hope our techniques may find further applications.
Download