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 language | English |
---|---|
Title of host publication | 31st Annual European Symposium on Algorithms (ESA 2023) |
Subtitle of host publication | [Proceedings] |
Editors | Inge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Pages | 1-16 |
Number of pages | 16 |
ISBN (Electronic) | 9783959772952 |
DOIs | |
Publication status | Published - 2023 |
Event | 31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Netherlands Duration: 4 Sept 2023 → 6 Sept 2023 |
Publication series
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Volume | 274 |
ISSN (Print) | 1868-8969 |
Conference
Conference | 31st Annual European Symposium on Algorithms, ESA 2023 |
---|---|
Country/Territory | Netherlands |
City | Amsterdam |
Period | 4/09/23 → 6/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