A roundtrip spanner of a directed graph $G$ is a subgraph of $G$ preserving roundtrip distances approximately for all pairs of vertices. Despite extensive research, there is still a small stretch gap between roundtrip spanners in directed graphs and undirected graphs. For a directed graph with real edge weights in $[1,W]$, we first propose a new deterministic algorithm that constructs a roundtrip spanner with $(2k-1)$ stretch and $O(k n^{1+1/k}log (nW))$ edges for every integer $k> 1$, then remove the dependence of size on $W$ to give a roundtrip spanner with $(2k-1)$ stretch and $O(k n^{1+1/k}log n)$ edges. While keeping the edge size small, our result improves the previous $2k+epsilon$ stretch roundtrip spanners in directed graphs [Roditty, Thorup, Zwick02; Zhu, Lam18], and almost matches the undirected $(2k-1)$-spanner with $O(n^{1+1/k})$ edges [Althofer et al. 93] when $k$ is a constant, which is optimal under Erdos conjecture.
تحميل البحث