Thorup-Zwick emulators are universally optimal hopsets

A (beta, epsilon)-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 p edges (hops) and length (1 + epsilon) dist(a, b). In this paper we observe that Thorup and Zwick's sublinear additive emulators are also actually (0(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+12K+1)-7). As corollaries, we also shave k factors off the size of Thorup and Zwick's [20] sublinear additive emulators and the sparsest known (1 + epsilon, O(k/c)k-1)-spanners, due to Abboud, Bodwin, and Pettie [1]. (C) 2018 Elsevier B.V. All rights reserved.