2026-08-25T17:34:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27291 2026-08-25T13:18:21Z ddc:004 open_access

A General Reduction from Near-Additive Emulators to Near-Exact Hopsets Aeri, Julian Forster, Sebastian Grilnberger, Mara hopsets shortest paths emulator-to-hopset-reduction Graph emulators and hopsets are two fundamental concepts for distance approximation. For a given graph G, an (α,β)-emulator is a sparse graph on the same vertex set that preserves the distances of G up to a multiplicative stretch α and additive stretch β. In contrast, an (α,β)-hopset is a set of additional edges that, when added to G, ensures that distances can be approximated up to a multiplicative stretch α, using paths containing at most β edges. When α = 1+ε for arbitrarily small ε > 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+ε',β)-emulator, with 0 ≤ ε' ≤ 1 and β ≥ 1, of size S_𝒜(n, ε',β), can be used to obtain a (1+ε, O(β²/ε² ln(n/ε)))-hopset of size O((S_𝒜(n + m β/ε², ε/294, β) 1/ε + n) ln(n/ε)), for any 0 < ε ≤ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julian Aeri and Sebastian Forster and Mara Grilnberger 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.155 urn:nbn:de:0030-drops-272919 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.155 eng https://creativecommons.org/licenses/by/4.0/legalcode