Bootstrapping Dynamic APSP via Sparsification
<|reference_start|>Bootstrapping Dynamic APSP via Sparsification: We give a simple algorithm for the dynamic approximate All-Pairs Shortest Paths (APSP) problem. Given a graph $G = (V, E, l)$ with polynomially bounded edge lengths, our data structure processes $|E|$ edge insertions and deletions in total time $|E|^{1 + o(1)}$ and provides query access to $|E|^{o(1)}$-approximate distances in time $\tilde{O}(1)$ per query.   We produce a data structure that mimics Thorup-Zwick distance oracles [TZ'05], but is dynamic and deterministic. Our algorithm selects a small number of pivot vertices. Then, for every other vertex, it reduces distance computation to maintaining distances to a small neighborhood around that vertex and to the nearest pivot. We maintain distances between pivots efficiently by representing them in a smaller graph and recursing. We construct these smaller graphs by (a) reducing vertex count using the dynamic distance-preserving core graphs of Kyng-Meierhans-Probst Gutenberg [KMPG'24] in a black-box manner and (b) reducing edge-count using a dynamic spanner akin to Chen-Kyng-Liu-Meierhans-Probst Gutenberg [CKL+'24]. Our dynamic spanner internally uses an APSP data structure. Choosing a large enough size reduction factor in the first step allows us to simultaneously bootstrap our spanner and a dynamic APSP data structure.   Notably, our approach does not need expander graphs, an otherwise ubiquitous tool in derandomization.<|reference_end|>
@article{kyng2024bootstrapping,
    title={Bootstrapping Dynamic APSP via Sparsification},
    author={Rasmus Kyng, Simon Meierhans, Gernot Z"ocklein},
    journal={arXiv preprint arXiv:2408.11375},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.11375},
    primaryClass={cs.DS}
}