Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition

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(n 1+1/k ) edges, and that this stretch-size tradeoff is optimal assuming the Erdös 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) • 2 O(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) .

Our algorithm relies on a new technical tool that we develop, and that we believe to be of independent interest, called low-diameter router decomposition. Specifically, we design a deterministic algorithm that maintains a decomposition of a fully dynamic graph into edge-disjoint clusters with bounded vertex overlap, where each cluster C is guaranteed to be a bounded-diameter router, meaning that any reasonable multicommodity demand over the vertices of C can be routed along short paths and with low congestion inside C. A similar graph decomposition notion was introduced by [Haeupler et al., STOC 2022] and recently strengthened by [Haeupler et al., FOCS 2024]; the latter result was already used to obtain fast algorithms for multicommodity flows [Haeupler et al., STOC 2024] and dynamic distance oracles [Haeupler et al., FOCS 2024]. However, in contrast to these and other prior works, the decomposition that our algorithm maintains is guaranteed to be proper, in the sense that the routing paths between the pairs of vertices of each cluster C are contained inside C (rather than in the entire graph G). Additionally, our algorithm maintains, for each cluster C of the decomposition, a subgraph C ′ ⊆ C of a prescribed density, that also has strong routing properties.

We show additional applications of our low-diameter router decomposition, by obtaining new deterministic dynamic algorithms for fault-tolerant spanners and low-congestion spanners. Several of these applications crucially rely on the fact that our router decomposition is proper.