Deterministic improved round-trip spanners

- We study the first deterministic algorithm for constructing round-trip spanners.
- Our deterministic algorithm out-performs the state-of-the-art randomized algorithm.
- We re-raise the question that how best we can hope for the stretch-size trade-off.

In this paper, we study the deterministic construction of round-trip spanners for weighted directed graphs. We propose a deterministic algorithm which constructs, for any n-vertex graph G(V,E), a round-trip spanner H(V,E′⊆E) of stretch 2k+ϵ and size O((k/ϵ)⋅n1+1/klog⁡(nw)), where w is the maximum edge weight of G. Notably, this is the first deterministic construction of round-trip spanners and its stretch-size trade-off even improves the previous state-of-the-art randomized algorithm by Roditty et al. More specifically, the size is asymptotically reduced by a factor of k while the stretch factor remains the same. The result is the first clear improvement on round-trip spanners after about ten years and re-raises the open question that how best we can hope for the stretch-size trade-off of round-trip spanners in digraphs.