directed graph $G$ with $n$ vertices, $m$ edges, integer non-negative edge weights, we can compute in $\tilde{O}(m\sqrt{n})$ time an $8$-multiplicative roundtrip spanner with ${\tilde{O}}(n^{3/2})$ edges with high probability in $n$.

Then, in \[sec:algo\] we give algorithms for a $O(k\log\log n)$-multiplicative approximation of the the girth and construct $O(k \log\log n)$ multiplicative roundtrip spanners with ${\tilde{O}}(n^{1+1/k})$ edges for a weighted directed graph $G$ with $n$ vertices and $m$ edges in $\tilde{O}(m^{1 + 1/k})$ time. These algorithms are deterministic and constitute the first deterministic nearly linear time algorithms for $\tilde{O}(1)$ multiplicative approximation of the girth and $\tilde{O}(1)$ multiplicative roundtrip spanners with $\tilde{O}(n)$ edges.

\[thm:girth\] For any integer $k \ge 1$ and 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\log n) \cdot g$.

\[thm:spanner\] For any integer $k \ge 1$ 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\log n)$ multiplicative roundtrip spanner with $\tilde{O}(n^{1 + 1/k})$ edges.

Setting $k = \frac{\log n}{\log\log n}$ yields the following corollaries. For $k = \Omega(\log n)$ these results 