Bootstrapping Dynamic Distance Oracles

Sebastian Forster*, Gramoz Goranci*, Yasamin Nazari*, Antonis Skarlatos*

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Designing approximate all-pairs distance oracles in the fully dynamic setting is one of the central problems in dynamic graph algorithms. Despite extensive research on this topic, the first result breaking the O(√n) barrier on the update time for any non-trivial approximation was introduced only recently by Forster, Goranci and Henzinger [SODA’21] who achieved m1/ρ+o(1) amortized update time with a O(log n)3ρ−2 factor in the approximation ratio, for any parameter ρ ≥ 1. In this paper, we give the first constant-stretch fully dynamic distance oracle with small polynomial update and query time. Prior work required either at least a poly-logarithmic approximation or much larger update time. Our result gives a more fine-grained trade-off between stretch and update time, for instance we can achieve constant stretch of O(1/ρ2)4/ρ in amortized update time Õ(nρ), and query time Õ(nρ/8) for any constant parameter 0 < ρ < 1. Our algorithm is randomized and assumes an oblivious adversary. A core technical idea underlying our construction is to design a black-box reduction from decremental approximate hub-labeling schemes to fully dynamic distance oracles, which may be of independent interest. We then apply this reduction repeatedly to an existing decremental algorithm to bootstrap our fully dynamic solution.

Original languageEnglish
Title of host publication31st Annual European Symposium on Algorithms (ESA 2023)
Subtitle of host publication[Proceedings]
EditorsInge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-16
Number of pages16
ISBN (Electronic)9783959772952
DOIs
Publication statusPublished - 2023
Event31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Netherlands
Duration: 4 Sept 20236 Sept 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume274
ISSN (Print)1868-8969

Conference

Conference31st Annual European Symposium on Algorithms, ESA 2023
Country/TerritoryNetherlands
CityAmsterdam
Period4/09/236/09/23

Bibliographical note

Funding Information:
Funding This work is supported by the Austrian Science Fund (FWF): P 32863-N. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 947702).

Publisher Copyright:
© Sebastian Forster, Gramoz Goranci, Yasamin Nazari, and Antonis Skarlatos.

Funding

Funding This work is supported by the Austrian Science Fund (FWF): P 32863-N. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 947702).

Keywords

  • Distance Oracles
  • Dynamic graph algorithms
  • Shortest Paths

Fingerprint

Dive into the research topics of 'Bootstrapping Dynamic Distance Oracles'. Together they form a unique fingerprint.

Cite this