Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915759682224128 |
|---|---|
| author | Chuzhoy, Julia Parter, Merav |
| author_facet | Chuzhoy, Julia Parter, Merav |
| contents | 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 \emph{stretch}. We investigate the problem of maintaining spanners in the fully dynamic setting with an adaptive adversary. Despite a long line of research, this problem is still poorly understood: no algorithm achieving a sublogarithmic stretch, a sublinear in $n$ update time, and a strongly subquadratic in $n$ spanner size is currently known.
One of our main results is a deterministic algorithm, that, for any $512 \leq k \leq (\log n)^{1/49}$ and $1/k\leq δ\leq 1/400$, maintains a spanner $H$ of a fully dynamic graph with stretch $poly(k)\cdot 2^{O(1/δ^6)}$ and size $|E(H)|\leq 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, called low-diameter router decomposition. 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 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. A similar graph decomposition notion was introduced by [Haeupler et al., STOC 2022] and strengthened by [Haeupler et al., FOCS 2024]. However, in contrast to these and other prior works, the decomposition that our algorithm maintains is proper, ensuring that the routing paths between the pairs of vertices of each cluster $C$ are contained inside $C$, rather than in the entire graph $G$. We show additional applications of our router decomposition, including dynamic algorithms for fault-tolerant spanners and low-congestion spanners. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_20718 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition Chuzhoy, Julia Parter, Merav Data Structures and Algorithms 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 \emph{stretch}. We investigate the problem of maintaining spanners in the fully dynamic setting with an adaptive adversary. Despite a long line of research, this problem is still poorly understood: no algorithm achieving a sublogarithmic stretch, a sublinear in $n$ update time, and a strongly subquadratic in $n$ spanner size is currently known. One of our main results is a deterministic algorithm, that, for any $512 \leq k \leq (\log n)^{1/49}$ and $1/k\leq δ\leq 1/400$, maintains a spanner $H$ of a fully dynamic graph with stretch $poly(k)\cdot 2^{O(1/δ^6)}$ and size $|E(H)|\leq 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, called low-diameter router decomposition. 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 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. A similar graph decomposition notion was introduced by [Haeupler et al., STOC 2022] and strengthened by [Haeupler et al., FOCS 2024]. However, in contrast to these and other prior works, the decomposition that our algorithm maintains is proper, ensuring that the routing paths between the pairs of vertices of each cluster $C$ are contained inside $C$, rather than in the entire graph $G$. We show additional applications of our router decomposition, including dynamic algorithms for fault-tolerant spanners and low-congestion spanners. |
| title | Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.20718 |