2023/03/10 by Forster, Sebastian, Goranci, Gramoz, Nazari, Yasamin +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2303.06102
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((1)/(ρ2))4/ρ in amortized update time O(nρ), and query time O(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.