A Simple Dynamic Spanner via APSP

We present a simplified algorithm for maintaining a spanner of an edge-dynamic graph by reduction to an All-Pairs Shortest Paths (APSP) oracle. The underlying APSP oracle is a dynamic algorithm providing query access to approximate pairwise distances in a dynamic graph [9, 12, 11, 13].

We note in particular that the total recourse is almost-optimal and only depends on the number of vertices and deletions, and is therefore completely independent of the number of insertions.

Our simple algorithm yielding Theorem 2 is presented in Section 4. It can use any path-reporting approximate APSP data structure and only adds an $O(\log n)$ factor overhead in runtime and approximation. We refer the reader to Definition 5 and Theorem 12 for a more fine grained analysis of the dependency on the underlying APSP data structure.

Batching techniques allow us to extend our spanner to handle an arbitrary number of deletions, where the recourse becomes almost-linear in the number of deletions and vertices.

An originally independent work [8] recently introduced the idea of obtaining a dynamic spanner with stretch $\delta =o(\log n)$.³³3The first version of this article on arXiv precedes the announcement of [8], but their article prompted us to add Theorem 4 and Section 5. They remark that prior to their work, no algorithm with update time $o(n)$, $n^{1+o(1)}$ edges and stretch $o(\log n)$ existed. This motivated us to extend our spanner to handle arbitrary non-constant stretch as in Theorem 18. They heavily use ideas from [11] directly, which we completely black-box. We remark that our algorithm loses large sub-polynomial factors in update time and density compared to theirs.

Our algorithm yielding Theorem 4 is presented in Section 5. It depends on the APSP data structure of [11], which can get arbitrarily good approximation by trading it off for update time. We point out that the recourse achieved by our algorithm is again almost-optimal, since scaling linearly in the number of deletions is unavoidable.

In [2], the authors present a randomized dynamic spanner with poly-logarithmic stretch and amortized update time against an oblivious adversary.⁴⁴4Oblivious adversaries generate the sequence of updates at the start, i.e. independently from the random output of the algorithm. Adaptive adversaries can use the previous output to fool a randomized algorithm. Then [10] significantly reduced the poly-logarithmic overhead in both size and update time. In [3], the authors gave the first non-trivial algorithm for maintaining a dynamic spanner against an adaptive adversary. They maintain a spanner of near linear size with poly-logarithmic amortized update time and stretch. Deterministic algorithms for maintaining spanners of dynamic graphs with bounded degree that additionally undergo vertex splits were developed in the context of algorithms for minimum cost flow [7, 5, 6]. These have sub-polynomial overhead.

We let $G=(V,E)$ denote unweighted and undirected graphs with vertex set $V$ and edge set $E$. When we want to refer to the vertex/edge set of some graph $G$, we sometimes use $V(G)$ and $E(G)$ respectively.

We refer to $\left|E(G)\right|/\left|V(G)\right|$ as the density of a graph, and say a graph is sparse whenever its density is $n^{o(1)}$.

For a graph $G=(V,E)$ and a pair of vertices $u,v\in V$ we let ${\mathrm{dist}}_G(u,v)$ denote the length of a shortest $uv$-path in $G$. We call a graph edge-dynamic if it receives arbitrary updates to $E$ (i.e. edge insertions and deletions). We refer to the total number of such edge updates a graph receives as the recourse.

Given two graph $H$ and $G$ on the same vertex set such that $H\subseteq G$, we let ${\mathrm{\Pi }}_{G\to H}$ be a function that maps edges in $E(G)$ to paths in $H$. Given an embedding ${\mathrm{\Pi }}_{G\to H}$, we define the edge congestion $\mathrm{econg}({\mathrm{\Pi }}_{G\to H},e)\stackrel{\mathrm{def}}{=}|\{f\in E(G):e\in {\mathrm{\Pi }}_{G\to H}(f)\}|$ for $e\in E(H)$.

We first present a very simple dynamic variant of the greedy spanner that merely limits the number of changes to $H$, i.e. its recourse. Then we describe the necessary changes for obtaining an efficient version using a dynamic APSP datastructure.

Let $G=(V,E)$ be an initially empty graph on $n$ vertices. We maintain a $O(\log n)$-spanner $H\subseteq G$ as follows.

• $\mathrm{■}$

  When an edge $(u,v)$ is inserted to $G$, we check if $\mathrm{dist}(u,v)>2\log n$. If so, we add it to $H$.

• $\mathrm{■}$

  When an edge $(u,v)$ is deleted from $G$, we remove it from $H$ if it is present and re-insert all edges in $E(G)\setminus E(H)$ using the procedure described above. If $(u,v)$ is not in $H$, we do not need to update our spanner.

This algorithm still maintains that the girth of $H$ is at least $2\log n+1$, and therefore the graph $H$ contains at most $O(n)$ edges at any point. Edges only leave the spanner $H$ when they are deleted. If at most $D$ edges get deleted throughout, a total recourse bound of $O(n+D)$ follows directly since the total recourse is bounded by $(\text{maximum \# edges in }H)+(\text{\# edges leaving }H)$.

To turn the above framework into an efficient algorithm, we maintain an embedding ${\mathrm{\Pi }}_{G\to H}$ that maps each edge in $G$ to a short path in $H$ and thus certifies that such a path still exists. We then only have to re-insert all edges whose embedding paths use the deleted edge. To bound the number of re-insertions, we carefully manage the edge congestion of ${\mathrm{\Pi }}_{G\to H}$. Finally, we use an APSP data structure (See Definition 5) to obtain distances and paths. In the following, we assume there are at most $m$ insertions, $n$ deletions and that $|V|=n$.

Our algorithm internally maintains two graphs: The current spanner $H$ and a not yet congested sub-graph $\widehat{H}\subseteq H$. We maintain that the edge congestion is strictly less than $K$ for every edge in $\widehat{H}$, and maintain access to distances and paths in $\widehat{H}$ via a $\gamma$-approximate $\alpha$-update $\beta$-query APSP data structure ${𝒟}_{\widehat{H}}$.

• $\mathrm{■}$

  When an edge $e$ is inserted, we check if ${𝒟}_{\widehat{H}}$ returns distance at most $2\gamma \log n$ between the endpoints. If this is the case, we query it for a witness path $P$ and store $P$ as the embedding path of $e$. Then we check if any of the edges on the path now have $K$ embedding paths using them, and if so we remove them from $\widehat{H}$. Otherwise, we add the edge $e$ to $H$ and $\widehat{H}$.

• $\mathrm{■}$

  When an edge $e$ is deleted, we remove it from $\widehat{H}$ and $H$ and re-insert all edges that now have a broken embedding path using the procedure above.

Choosing the threshold $K=m/n$ allows us to tolerate up to $n$ deletions which yield $m$ additional calls to the insertion procedure. See Algorithm 1 for detailed pseudocode.

We first show that $H$ is a $(2\cdot \gamma \cdot \log n)$-approximate spanner.

We now show that we can allow for an arbitrary amount of deletions at the cost of a subpolynomial overhead in both stretch and update time.

Previously, we chose the density reduction parameter $K=m/n$, which corresponds to completely sparsifying the graph in one step. To handle more deletions, we choose $K$ much smaller, but then recursively compute spanners of spanners until we reach the desired sparsity. We call each such round of sparsification a layer.

Concretely, we let the density reduction $K$ be a tunable parameter and assume $m=K^{\mathrm{\Lambda }}\cdot n^{1+1/\kappa }$ for some integer number of layers $\mathrm{\Lambda }=O({\log }_K(m/n^{1+1/\kappa }))$. Reducing the density by $K$ for $\mathrm{\Lambda }$ layers will ensure that we reach the desired sparsity via the algorithm outlined below.

We initialize $H_0=G$, and recursively apply Algorithm 1 to obtain $H_i$ from $H_{i-1}$ for $i=1,\mathrm{\dots },\mathrm{\Lambda }$. We let $H_{\mathrm{\Lambda }}$ be the desired spanner. We then dynamically maintain this hierarchy throughout a sequence of up to $m$ insertions and $m/K$ deletions to $H_0=G$. Concretely, we go over the layers in ascending order and at layer $i$ feed all the changes caused to $H_{i-1}$ to the spanner data structure maintaining $H_i$. This may lead to updates of $H_i$, which then get passed to the next layer $i+1$ as long as .

Whenever the graph $G$ has experienced some multiple of $m/K^{i+1}$ deletions, we re-initialize layers $i,\mathrm{\dots },\mathrm{\Lambda }$. We call this a rebuild. The reason rebuilds are required is to maintain sparsity, as otherwise the number of congested edges would grow too much on layers with higher indices due to re-insertions. We stress that the timing of rebuilds only depends on the update sequence to the original graph $G$.

The key insight that enables this algorithm is that edge deletions in $H_i$ always correspond to edge deletions in $G$, i.e. deletions to $H_i$ might cause some extra insertions to $H_{i+1}$, but never more deletions. This is crucial since deletions cause a large amount of recourse, but recourse due to insertions is effectively sparsified.

We first show that the final spanner $H_{\mathrm{\Lambda }}$ has the desired sparsity.