nearly match the optimal algorithms in undirected graphs for $O(k)$ girth approximation and the construction of $O(k)$ spanners.

For any weighted directed graph $G$ with $n$ vertices, $m$ edges, and unknown girth $g$ we can compute in $\tilde{O}(m)$ time an estimate $g'$ such that $g \le g' \le O(\log n) \cdot g$.

For any weighted directed graph $G$ with $n$ vertices and $m$ edges, we can compute in $\tilde{O}(m)$ time an $O(\log n)$ multiplicative roundtrip spanner with $\tilde{O}(n)$ edges.

Interestingly, our results for constant factor randomized approximations and our results for deterministic approximations are achieved in different ways. Highlighting this, in \[sec:klogk\_approx\] we show how to combine the techniques of these algorithms to obtain both $O(k \log k)$ multiplicative approximations to the girth and $O(k \log k)$ multiplicative roundtrip spanners of size ${\tilde{O}}(n^{1 + 1/k})$ in ${\tilde{O}}(m n^{1/k})$ time with high probability in $n$.

\[thm:const\_girth\] For any integer $k \ge 1$ and any weighted directed graph $G$ with $n$ vertices, $m$ edges, and unknown girth $g$ we can compute in $\tilde{O}(m^{1 + 1/k})$ time an estimate $g'$ such that $g \le g' \le O(k \log k) \cdot g$ with high probability in $n$.

\[thm:arb\_const\_spanner\] For any integer $k \ge 1$ 