do not exist in all directed graphs. For example, any directed spanner for the “directed" complete bipartite graph with $n$ vertices on the left directed towards $n$ vertices on the right clearly requires all $n^2$ edges. This problem seems to arise from the fact that the distance metric $d(u, v)$ in directed graphs is asymmetric. Therefore, if we want to construct sparse spanners, it is natural to work instead with the symmetric *roundtrip distance* metric, defined as $d(u {\leftrightarrows}v) := d(u, v) + d(v, u)$ [@CowenW04] and similarly define an $\alpha$-*roundtrip spanner* of a directed graph $G$ to be a subgraph that multiplicatively preserves roundtrip distances up to a factor of $\alpha$.

Interestingly, there do exist roundtrip spanners for directed graphs with comparable sparsity as spanners for undirected graphs. A result of Roditty, Thorup, and Zwick [@RTZ08] shows that for any $k \ge 1$ and ${\varepsilon}> 0$, every graph has a $(2k+{\varepsilon})$-roundtrip spanner with $O(k^2 n^{1+ 1/k}\log(nW) {\varepsilon}^{-1})$ edges, where $W$ is the maximum edge weight. Unforunately, this algorithm ran in time $\Omega(mn)$, as it requires the computation of all pairs distances in the graph. Recent work Pachocki [*et al.*]{} [@PRSTV18] gave a randomized algorithm running in time $\tilde{O}(m^{1+1/k})$ which 