License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.81
URN: urn:nbn:de:0030-drops-170192
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17019/
Go to the corresponding LIPIcs Volume Portal

Neiman, Ofer ; Shabat, Idan

A Unified Framework for Hopsets

pdf-format:
LIPIcs-ESA-2022-81.pdf (0.7 MB)

Abstract

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).

BibTeX - Entry

@InProceedings{neiman_et_al:LIPIcs.ESA.2022.81,
  author =	{Neiman, Ofer and Shabat, Idan},
  title =	{{A Unified Framework for Hopsets}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{81:1--81:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17019},
  URN =		{urn:nbn:de:0030-drops-170192},
  doi =		{10.4230/LIPIcs.ESA.2022.81},
  annote =	{Keywords: Graph Algorithms, Shortest Paths, Hopsets}
}

Keywords: Graph Algorithms, Shortest Paths, Hopsets
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI