  It is known that a better than $2$-approximation algorithm for the girth in
dense directed unweighted graphs needs $n^{3-o(1)}$ time unless one uses fast
matrix multiplication. Meanwhile, the best known approximation factor for a
combinatorial algorithm running in $O(mn^{1-\epsilon})$ time (by Chechik et
al.) is $3$. Is the true answer $2$ or $3$?
  The main result of this paper is a (conditionally) tight approximation
algorithm for directed graphs. First, we show that under a popular hardness
assumption, any algorithm, even one that exploits fast matrix multiplication,
would need to take at least $mn^{1-o(1)}$ time for some sparsity $m$ if it
achieves a $(2-\epsilon)$-approximation for any $\epsilon>0$. Second we give a
$2$-approximation algorithm for the girth of unweighted graphs running in
$\tilde{O}(mn^{3/4})$ time, and a $(2+\epsilon)$-approximation algorithm (for
any $\epsilon>0$) that works in weighted graphs and runs in $\tilde{O}(m\sqrt
n)$ time. Our algorithms are combinatorial.
  We also obtain a $(4+\epsilon)$-approximation of the girth running in
$\tilde{O}(mn^{\sqrt{2}-1})$ time, improving upon the previous best
$\tilde{O}(m\sqrt n)$ running time by Chechik et al. Finally, we consider the
computation of roundtrip spanners. We obtain a $(5+\epsilon)$-approximate
roundtrip spanner on $\tilde{O}(n^{1.5}/\epsilon^2)$ edges in $\tilde{O}(m\sqrt
n/\epsilon^2)$ time. This improves upon the previous approximation factor
$(8+\epsilon)$ of Chechik et al. for the same running time.
