# Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners

arXiv: https://arxiv.org/abs/1611.00721 · HTML: https://mlsanity.com/paper/1611.00721/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2016.

## Built on by (most cited first, 1 of 1)

- [Generative Artificial Intelligence: Evolving Technology, Growing Societal Impact, and Opportunities for Information Systems Research](https://mlsanity.com/paper/2503.05770/) (2025)

## Abstract (arXiv)

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(minnω, mn) time (for 2≤ω<2.373). In this paper, we drastically improve these runtimes as follows: * Multiplicative Approximations in Nearly Linear Time: We give an algorithm that in widetildeO(m) time computes an widetildeO(1)-multiplicative approximation of the girth as well as an widetildeO(1)-multiplicative roundtrip spanner with widetildeO(n) edges with high probability (w.h.p). * Nearly Tight Additive Approximations: For unweighted graphs and any α ∈ (0,1) we give an algorithm that in widetildeO(mn1 - α) time computes an O(nα)-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(minnω, mn) time. Given the traditional difficulty in efficiently processing directed graphs, we hope our techniques may find further applications.