{"ID":6138173,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T09:17:56.117045019Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07190","arxiv_id":"2607.07190","title":"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+ε$ for arbitrarily small $ε\u003e0$, 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+ε',β)$-emulator, with $0 \\le ε' \\le 1$ and $β\\ge 1$, of size $S_{\\mathcal{A}}(n, ε',β)$, can be used to obtain a $(1+ε, O(\\frac{β^2}{ε^2} \\ln(\\frac{n}ε)))$-hopset of size $O((S_{\\mathcal{A}}(n+m\\fracβ{ε^2}, \\fracε{294},β) \\frac{1}ε + n)\\ln(\\frac{n}ε))$, for any $0 \u003c ε\\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.","short_abstract":"Graph emulators and hopsets are two fundamental concepts for distance approximation. When the multiplicative stretch is $1+ε$ for arbitrarily small $ε\u003e0$, these structures are known as near-additive emulators and near-exact hopsets, respectively. Prior work showed that there is a remarkable similarity between the const...","url_abs":"https://arxiv.org/abs/2607.07190","url_pdf":"https://arxiv.org/pdf/2607.07190v1","authors":"[\"Julian Aeri\",\"Sebastian Forster\",\"Mara Grilnberger\"]","published":"2026-07-08T09:27:05Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[\"Generative Adversarial Network\"]","has_code":false}