Thorup-Zwick Emulators are Universally Optimal Hopsets

Abstract

A $(\beta ,\epsilon )$-$\text{hopset}$ is, informally, a weighted edge set that, when added to a graph, allows one to get from point $a$ to point $b$ using a path with at most $\beta$ edges ("hops") and length $(1+\epsilon )\mathrm{dist}(a,b)$. In this paper we observe that Thorup and Zwick's $\text{sublinear additive}$ emulators are also actually $(O(k/\epsilon {)}^k,\epsilon )$-hopsets for every $\epsilon >0$, and that with a small change to the Thorup-Zwick construction, the size of the hopset can be made $O(n^{1+\frac{1}{2^{k+1}-1}})$. As corollaries, we also shave "$k$" factors off the size of Thorup and Zwick's sublinear additive emulators and the sparsest known $(1+\epsilon ,O(k/\epsilon {)}^{k-1})$-spanners, due to Abboud, Bodwin, and Pettie.