2026-07-20T07:30:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17019 2024-03-06T10:58:59Z ddc:004 open_access

A Unified Framework for Hopsets Neiman, Ofer Shabat, Idan Graph Algorithms Shortest Paths Hopsets Given an undirected graph G = (V,E), an (α,β)-hopset is a graph H = (V,E'), so that adding its edges to G guarantees every pair has an α-approximate shortest path that has at most β edges (hops), that is, d_G(u,v) ≤ d_{G∪H}^(β)(u,v) ≤ α⋅ d_G(u,v). Given the usefulness of hopsets for fundamental algorithmic tasks, several different algorithms and techniques were developed for their construction, for various regimes of the stretch parameter α. In this work we devise a single algorithm that can attain all state-of-the-art hopsets for general graphs, by choosing the appropriate input parameters. In fact, in some cases it also improves upon the previous best results. We also show a lower bound on our algorithm. In [Ben-Levy and Parter, 2020], given a parameter k, a (O(k^ε),O(k^{1-ε}))-hopset of size Õ(n^{1+1/k}) was shown for any n-vertex graph and parameter 0 < ε < 1, and they asked whether this result is best possible. We resolve this open problem, showing that any (α,β)-hopset of size O(n^{1+1/k}) must have α⋅β ≥ Ω(k). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ofer Neiman and Idan Shabat 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.81 urn:nbn:de:0030-drops-170192 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.81 eng https://creativecommons.org/licenses/by/4.0/legalcode