and any weighted directed graph $G$ with $n$ vertices and $m$ edges, we can compute in $\tilde{O}(m^{1 + 1/k})$ time an $O(k \log k)$ multiplicative roundtrip spanner with $\tilde{O}(n^{1 + 1/k})$ edges with high probability in $n$.

This shows that for any fixed ${\varepsilon}> 0$, that there is an algorithm running in time $m^{1+{\varepsilon}}$ that approximates the girth of a directed graph to within a constant depending on ${\varepsilon}$, but not on $m$ or $n$. Additionally, this almost matches the $O(k)$-multiplicative girth approximation algorithms running in $m^{1+1/k}$ time in undirected graphs.

Comparison to previous work
---------------------------

While the existence of roundtrip spanners matching the quality in undirected graphs was shown in [@RTZ08], the runtime was $O(mn)$ and required an APSP computation. Our results, \[thm:3girth\], \[thm:const\_spanner\] are the first to show that constant factor girth approximation and construction of constant factor roundtrip spanners with ${\tilde{O}}(n\sqrt{n})$ edges can be built in subquadratic ${\tilde{O}}(m\sqrt{n})$ time. This algorithm leverages new randomized techniques for testing a notion we call *similarity* between vertices not present in previous girth approximation and roundtrip spanner algorithms and we believe is of independent interest.

Our \[thm:girth\] and \[thm:spanner\] offer direct improvements over the analogous results in [@PRSTV18]. Specifically, our algorithms 