2026-08-16T22:37:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24582 2025-12-16T14:01:07Z ddc:004 open_access

Bootstrapping Dynamic APSP via Sparsification Kyng, Rasmus Meierhans, Simon Zöcklein, Gernot Dynamic Graph Algorithms Spanners Vertex Sparsification Bootstrapping 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 Õ(1) per query. We produce a data structure that mimics Thorup-Zwick distance oracles [Thorup and Zwick, 2005], 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 maintain these smaller graphs by (a) reducing vertex count using the dynamic distance-preserving core graphs of Kyng-Meierhans-Probst Gutenberg [Kyng et al., 2024] in a black-box manner and (b) reducing edge-count using a dynamic spanner akin to Chen-Kyng-Liu-Meierhans-Probst Gutenberg [Chen et al., 2024]. 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 a spanner and a dynamic APSP data structure. Notably, our approach does not need expander graphs, an otherwise ubiquitous tool in derandomization. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rasmus Kyng and Simon Meierhans and Gernot Zöcklein 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.113 urn:nbn:de:0030-drops-245826 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.113 eng https://creativecommons.org/licenses/by/4.0/legalcode