A General Reduction from Near-Additive Emulators to Near-Exact Hopsets

Abstract

Graph emulators and hopsets are two fundamental concepts for distance approximation. When the multiplicative stretch is $1+\epsilon$ for arbitrarily small $\epsilon >0$, these structures are known as near-additive emulators and near-exact hopsets, respectively. Prior work showed that there is a remarkable similarity between the constructions and guarantees of these two objects. In their survey on this topic, Elkin and Neiman [Bull. EATCS 130, 2020] explicitly asked whether one can obtain a general reduction between near-additive emulators and near-exact hopsets. Following that, Kogan and Parter [FOCS, 2022] provided a general reduction from hopsets to emulators and spanners. In this paper, we address the reverse direction and show that any construction for a near-additive emulator for undirected unweighted graphs can be leveraged as a black box to construct a hopset for an undirected weighted graph with comparable size, stretch, and a hopbound comparable to the emulator's additive stretch. Specifically, we show that any algorithm that constructs a $(1+{\epsilon }^{\prime },\beta )$-emulator, with $0\le {\epsilon }^{\prime }\le 1$ and $\beta \ge 1$, of size $S_{\mathcal{A}}(n,{\epsilon }^{\prime },\beta )$, can be used to obtain a $(1+\epsilon ,O(\frac{{\beta }^2}{{\epsilon }^2}\ln (\frac{n}{\epsilon })))$-hopset of size $O((S_{\mathcal{A}}(n+m\frac{\beta }{{\epsilon }^2},\frac{\epsilon }{294},\beta )\frac{1}{\epsilon }+n)\ln (\frac{n}{\epsilon }))$, for any $0<\epsilon \le 1$. Therefore, our reduction answers the question of Elkin and Neiman [Bull. EATCS 130, 2020] for sparse graphs and further advances the understanding of the formal connection between these two structures. Designing a reduction resulting in a hopset size that does not depend on $m$ remains an intriguing open question.

arXiv comment29 Pages, accepted to ESA