# Bootstrapping Dynamic Distance Oracles

arXiv: https://arxiv.org/abs/2303.06102 · HTML: https://mlsanity.com/paper/2303.06102/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2023.

## Built on by (most cited first, 1 of 1)

- [The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations](https://mlsanity.com/paper/2307.08890/) (2023)

## Abstract (arXiv)

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 a 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(frac1ρ2)4/ρ in amortized update time tildeO(nρ), and query time tildeO(nρ/8) for a constant parameter ρ <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.