---
abstract: |
    In this paper we provide a ${\tilde{O}}(m\sqrt{n})$ time algorithm that computes a $3$-multiplicative approximation of the girth of a $n$-node $m$-edge directed graph with non-negative edge lengths. This is the first algorithm which approximates the girth of a directed graph up to a constant multiplicative factor faster than All-Pairs Shortest Paths (APSP) time, i.e. $O(mn)$. Additionally, for any integer $k \ge 1$, we provide a deterministic algorithm for a $O(k\log\log n)$-multiplicative approximation to the girth in directed graphs in ${\tilde{O}}(m^{1+1/k})$ time. Combining the techniques from these two results gives us an algorithm for a $O(k\log k)$-multiplicative approximation to the girth in directed graphs in ${\tilde{O}}(m^{1+1/k})$ time. Our results naturally also provide algorithms for improved constructions of roundtrip spanners, the analog of spanners in directed graphs.

    The previous fastest algorithms for these problems either ran in All-Pairs Shortest Paths (APSP) time, i.e. $O(mn)$, or were due Pachocki [*et al.*]{} [@PRSTV18] which provided a randomized algorithm that for any integer $k \ge 1$ in time $\tilde{O}(m^{1+1/k})$ computed with high probability a $O(k\log n)$ multiplicative approximation of the girth. Our first algorithm constitutes the first sub-APSP-time algorithm for approximating the girth to constant accuracy, our second removes the need for 