has in expectation ${\tilde{O}}(\sqrt{n})$ vertices that could possibly be in a cycle of length $O(R)$ through that vertex. By then checking each of these sets for a cycle and being careful about the degrees of the vertices (and therefore the cost of the algorithm) this approach yields essentially a $4$-approximation to the girth in ${\tilde{O}}(m\sqrt{n})$ time with high probability in $n$.

Our $3$-approximation is then obtained by carefully applying this argument to both outballs and inballs and leveraging the simple fact that if a vertex $v$ is on a cycle $C$ of length $R$ then for every $c \in C$ either $d(v,c) \leq R/2$ or $d(c,v) \leq R/2$.

#### Overview of deterministic $O(k \log \log n)$ results:

Our deterministic algorithm in \[sec:algo\] is based on a different approach than our randomized constant approximation algorithms in \[sec:constantapprox\]. We think this approach is of independent interest and further demonstrate its utility in \[sec:klogk\_approx\] by showing how to combine the insights that underly it with the algorithm from \[sec:algo\] to achieve arbitrary constant approximations.

For the sake of simplicity, we focus on unweighted directed graphs $G$ and for a parameter $R$, construct a subgraph (roundtrip spanner) $H$ so that if the roundtrip distance 