on weighted directed graphs $G$ returns a $O(k\log n)$-roundtrip spanner with $\tilde{O}(n^{1+1/k})$ edges and an $O(k\log n)$ approximation to the girth. Up to a logarithmic approximation factor, this matches the sparsity and runtime known for spanners on undirected weighted graphs and girth on sparse graphs.

The result of Pachocki [*et al.*]{} [@PRSTV18] constitutes one of small, but rapidly growing [@CohenKPPRSV17; @CohenKKPPRS18], set of instances where it is possible to obtain robust nearly linear time approximations to fundamental quantities of directed graphs in nearly linear time, overcoming typical running time gaps between solving problems on directed and undirected graphs.

However, a fundamental open problem left open by this work is whether it is possible to achieve subquadratic algorithms for constant factor approximation of the girth in directed graphs, and more ambitiously to fully close this gap and provide algorithms for $O(k)$ girth approximation and $O(k)$ roundtrip spanners in directed graphs that fully match the runtime and sparsity of those in undirected graphs. This is the primary problem this paper seeks to address and this paper provides multiple new girth approximation algorithms with improved runtime, approximation quality, and dependency on randomness.

Our Results
-----------

In this paper we provide a subquadratic algorithm 