Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
Julia Chuzhoy, Merav Parter · Society for Industrial and Applied Mathematics eBooks · 2025
A t-spanner of an undirected n-vertex graph G is a sparse subgraph H of G that preserves all pairwise distances between its vertices to within multiplicative factor t, also called the stretch. Spanners play an important role in the design of efficient algorithms for distance-based graph optimization problems, as they allow one to sparsify the graph, while approximately preserving all distances. It is well known that any n-vertex graph admits a (2k — 1)-spanner with O (n1+1/k) edges, and that this stretch-size tradeoff is optimal assuming the Erdos Girth Conjecture. In this paper we investigate the problem of efficiently maintaining spanners in the fully dynamic setting with an adaptive adversary. Despite a long and intensive line of research, this problem is still poorly understood: for example, no algorithm achieving a sublogarithmic stretch, with a sublinear in n update time, and a strongly subquadratic in n bound on the size of the spanner is currently known in this setting. One of our main results is a deterministic (and therefore, adaptive-adversary) algorithm, that, for any 512 ≤ k ≤ (log n )1/49 and 1/k ≤ δ ≤ 1/400, maintains a spanner H of a fully dynamic graph with stretch poly(k ) · 2o (1/δ6) and size |E (H )| ≤ O (n 1+O (1/k )), with worst-case update time n O(δ ) and recourse n O(1/k ).