Bootstrapping Dynamic APSP via Sparsification

We first define the necessary preliminaries in Section 2. Then, we present a simplified version of our algorithm as a warm-up in Section 3. Afterwards, we present our bootstrapped algorithm based on the KMG-vertex sparsifier [16] and a dynamic spanner in Section 4.

We use $G=(V,E,𝒍)$ to refer to a graph $G$ with vertex set $V$, edge set $E$ and length vector $𝒍\in {ℝ}_{\ge 1}^E$. We will restrict our attention to polynomially bounded integral lengths, and will denote their upper bound by $L$.

For two vertices $u,v$, we let ${\pi }_{u,v}^G$ denote the shortest path from $u$ to $v$ in $G$ (lowest sum of edge lengths). Furthermore, we let ${\mathrm{dist}}_G(u,v)$ be the length of said path.

We let and ${\overline{B}}_G(u,v)\stackrel{\mathrm{def}}{=}\{w:\mathrm{dist}(u,w)\le \mathrm{dist}(u,v)\}$. Then, for a set $A\subseteq V$ we let $B_G(u,A)\stackrel{\mathrm{def}}{=}{\bigcup }_{a\in A}{B}_G(u,a)$ and ${\overline{B}}_G(u,A)\stackrel{\mathrm{def}}{=}{\bigcup }_{a\in A}{\overline{B}}_G(u,a)$ respectively.

Finally, we define the neighborhood of a vertex $u$ as $𝒩(u)\stackrel{\mathrm{def}}{=}\{v:(u,v)\in E\}\cup \{u\}$ and of a set $A\subseteq V$ as $𝒩(A)\stackrel{\mathrm{def}}{=}{\bigcup }_{a\in A}𝒩(a)$. For a vertex $v$, we let $E_G(v)\stackrel{\mathrm{def}}{=}\{(v,u):u\in 𝒩(v)\}\subseteq E(G)$.

When it is clear from the context, we sometimes omit the subscript/superscript $G$.

Vertex splits are a crucial operation in our algorithms. They arise since we contract graph components and represent them as vertices. When such a component needs to be divided, this naturally corresponds to a vertex split defined as follows.

We can also define our notion of fully-dynamic graphs, which includes vertex splits as an operation.

Whenever we disallow vertex splits, we refer to edge-dynamic graphs instead.

For a dynamic object ${(F(t))}_{t\in [T]}$ defined on an index set $[T]=\{1,\mathrm{\dots },T\}$, we refer to $F^{(T^{\prime })}\stackrel{\mathrm{def}}{=}{(F(t))}_{t\in [T^{\prime }]}$ as the full sequence up to time $T^{\prime }$. We can then apply functions $g(\cdot )$ that operate on sequences to $F^{(T^{\prime })}$, e.g. $g(F^{(T^{\prime })})$. This is for example very useful to keep track of how an object changes over time. By providing a difference function $\mathrm{△}(F(t),F(t-1))$ for a dynamic object $F$, one may define the recourse as the sum of differences ${\Vert F^{(t)}\Vert }_{\to }\stackrel{\mathrm{def}}{=}{\sum }_{i=0}^{t-1}\mathrm{△}(F(i+1),F(i))$.

For functions $f$ that operate on a static object $G$ instead of on a sequence, we overload the notation by saying $f(G^{(t)})$ is simply $f$ applied to the last object in the sequence, that is, $f(G^{(t)})=f(G(t))$. For example, ${\mathrm{deg}}_{\max }(G^{(t)})$ is defined to be the maximum degree of the graph $G$ at time $t$.

Whenever we make a statements about a dynamic object $F$ without making reference to a specific time $t$, we implicitly mean that the statement holds at all times. For example, ${\Vert H\Vert }_{\to }\le {\Vert G\Vert }_{\to }$ formally means $\text{ for all }t:{\Vert H^{(t)}\Vert }_{\to }\le {\Vert G^{(t)}\Vert }_{\to }$. Meanwhile, $|E(H)|\le |E(G)|$ formally means $\text{ for all }t:|E(H^{(t)})|\le |E(G^{(t)})|$, and by our convention for applying functions of static objects to a dynamic object, we have that $|E(H^{(t)})|\le |E(G^{(t)})|$ means $|E(H(t))|\le |E(G(t))|$.

The time scales we use are fine-grained as we will consider multiple dynamic objects that change more frequently than the input graph $G$ does. We will choose an index set for the dynamic sequence which is fine-grained enough to capture changes to all the objects relevant to a given proof.

A dynamic object $H$ might not change in a time span in which another object $F$ changes multiple times. In this case, to have sequences that are indexed by the same set, we simply pad the sequence of $H$ with the same object, so that both dynamic objects would share the same index set $T$.

For fully-dynamic graphs $G$, we let $\mathrm{△}(G(t),G(t-1))$ denote the number of edge insertions, edge deletions, vertex splits and isolated vertex insertions that happened between $G(t)$ and $G(t-1)$. Note that generally, vertex splits cannot be implemented in constant time, and thus recourse bounds are not directly relevant to bounding running time. Nevertheless, this convention for measuring recourse is useful, as it is tailored precisely to the type of recourse bounds we prove.

We can store anything that occurs at various times throughout our algorithm in a dynamic object and define what recourse means for it. For example, we will repeatedly call a procedure $\text{ReduceDegree}(X)$. If at time $t$ we call the function with input $X(t)$, we might want to track the quantity ${\sum }_{t^{\prime }\le t}|X(t^{\prime })|$, so we simply let $R_X$ be the dynamic object such that $R_X(t)={\sum }_{t^{\prime }\le t}|X(t^{\prime })|$. By defining the difference $\mathrm{△}(R_X(t),R_X(t-1))=R_X(t)-R_X(t-1)$, we can find out how much the value changed during two points in time. A statement such as ${\Vert H\Vert }_{\to }\le {\Vert G\Vert }_{\to }+{\Vert R_X\Vert }_{\to }$ then means that at any time $t$ (suitably fine-grained), the total amount of changes that $H$ underwent are not more than the amount of $G$, plus some extra number of updates determined by the calls to $\text{ReduceDegree}(\cdot )$ made up to that time.

By viewing the run-time of dynamic algorithm as evolving over a sequence of updates and thinking of it as a dynamic object, we also give meaning to the statement, say, that an algorithm runs in time $n+\gamma {\Vert G\Vert }_{\to }$.

We introduce APSP data structures for edge-dynamic graphs.

Given an edge-dynamic graph $G$, we can maintain in time $\tilde{O}(1)\cdot {\Vert G\Vert }_{\to }$ another edge-dynamic graph $G^{\prime }$ in which we replace vertices by Binary Search Trees with one leaf node per edge of the vertex in the original graph. It is immediate that if we can find shortest paths in $G^{\prime }$, we can translate them into shortest paths in $G$. The advantage of this technique is that while $|E(G^{\prime })|=O(|E(G)|)$, $|V(G^{\prime })|=O(|E(G)|)$ and ${\Vert G^{\prime }\Vert }_{\to }=\tilde{O}({\Vert G\Vert }_{\to })$, we have ${\mathrm{deg}}_{\max }(G^{\prime })\le 3$.

We first introduce pivot hierarchies.

Pivot maps should be thought of as mapping vertices to smaller and smaller sets of representatives, and the cluster maps should be thought of as small neighborhoods of pivots for which (approximate) distances are stored. In classical Thorup-Zwick, the cluster $C_i(v)$ consists of all vertices in $A_i$ that are closer to $v$ than $p_i(v)$. In our algorithms, these balls become somewhat distorted due to sparsification. We then define the approximate distances maintained by the hierarchy.

We note that efficient distance queries can be implemented as long as the distances within clusters and the distances to pivots are efficiently maintained. In this warm up, we only focus on maintaining the collection $𝒞$ with low recourse. However, our full algorithm will maintain this additional information.

Formally, the goal of this warm-up section is to prove the following theorem.

We emphasize that this theorem is not particularly useful, as it comes without meaningful guarantees on the update time, and one could just use Dijkstras algorithm to obtain exact distances in this regime. Even the recourse guarantee is also of limited use, as we do not control the recourse of the pivot maps or the cluster maps of the pivot hierarchy. Nevertheless, our algorithm for proving this theorem is instructive and closely mirrors our final dynamic APSP algorithm.

The illustrative algorithm for maintaining pivot hierarchies repeatedly decreases the vertex count via low-recourse core graphs, and the edge count via a low-recourse spanner. We present these two pieces separately.

In this section, we state a theorem about maintaining a KMG-vertex sparsifier with low recourse [16]. Although their algorithm only works for edge-dynamic graphs, it can be extended to fully-dynamic graphs rather straightforwardly in the recourse setting. Recall that we count a vertex split as a single operation when defining the recourse of a fully-dynamic graph.

In this section, we describe a simple algorithm for maintaining a spanner $H$ of a fully-dynamic graph $G$ with remarkably low recourse. The construction is based on the greedy spanner of [1]. The low-recourse property of a variant of this algorithm has been observed in [3].

Given the low-recourse vertex and edge sparsification routines described above, we are ready to give the algorithm for Theorem 10.

Our algorithm consists of layers $0,\mathrm{\dots },\mathrm{\Lambda }-1$ where $\mathrm{\Lambda }=\sqrt{\log n}$.²²2We remark that our full algorithm uses a much more drastic size reduction to enable bootstrapping, which results in only $O({\log }^{ϵ}\log n)$ layers for some small constant . This is necessary because the stretch is powered every time we recurse. Each layer consists of two graphs $G_i$ and $H_i$, where $H_i\subseteq G_i$. We let $G_0=G$. Then we obtain $H_i$ from $G_i$ and $G_i$ from $H_{i-1}$ as follows:

1. 1.

   $G_i$ is the output of the vertex sparsifier from Theorem 13 on the graph $H_{i-1}$ for size reduction parameter $k\stackrel{\mathrm{def}}{=}{2}^{\sqrt{\log n}}$. For simplicity, we assume that $k$ is an integer without loss of generality.

2. 2.

   $H_i$ is the dynamic spanner from Theorem 14 on the graph $G_i$.

Whenever an update to $G$ occurs, we pass the updates up the hierarchy until we reach the first layer $j$ that has recieved more than ${\gamma }_{\text{DS}}^j{\gamma }_{\text{VS}}^j{2}^{\mathrm{\Lambda }-j}$ since it was initialized. Then, we re-initialize all the layers $j,\mathrm{\dots },\mathrm{\Lambda }$ via the steps described above. Notice in particular that the recourse of each layer is much smaller than the size reduction, leading to manageable recourse over all.

We let the sets $A_i$ be the vertex sets of the graphs $G_i$ mapped back to $G$, and we let $A_{\mathrm{\Lambda }}$ contain an arbitrary vertex $r$ in $A_{\mathrm{\Lambda }-1}$ (also mapped back to $G$). Furthermore, we let the pivot map $p_i(\cdot )$ be the pivot function maintained by the data structure from Theorem 13 at layer $i+1$ for $i=0,\mathrm{\dots },\mathrm{\Lambda }-1$, and the cluster map $C_i$ is the cluster map from vertex sparsifier data structure at layer $i+1$. Finally, we define the cluster map $C_{\mathrm{\Lambda }}(v)\stackrel{\mathrm{def}}{=}{A}_{\mathrm{\Lambda }}$ and pivot map $p_{\mathrm{\Lambda }}(v)$ for every vertex $v\in A_{\mathrm{\Lambda }}$.

First, our algorithm reduces the APSP problem to a graph $\tilde{G}$ with significantly fewer vertices using the KMG-vertex sparsifier (See Section 4.3). When compared to the low-recourse version presented in Section 3, our vertex sparsifier has an additional routine called $\text{ReduceDegree}(\cdot )$ which forces some of the vertices in the vertex sparsifier to be split and therefore have smaller degree. We further elaborate this point in the section below.

The vertex sparsification algorithm is presented in Section 4.3.

Although $\tilde{G}$ is supported on a much smaller vertex set, it may still contain most of the edges from $G$. To achieve a proper size reduction, we additionally employ edge sparsification on top of the vertex sparsifier $\tilde{G}$.

There are two key differences between the warm up and the efficient spanner algorithm.

• $\mathrm{■}$

  To quickly check for detours in the spanner, the efficient algorithm recursively uses APSP datastructures on small instances (See Section 4.4).

• $\mathrm{■}$

  To efficiently maintain the dynamic spanners, it is crucial that the degree of the graph remains bounded. Although we can assume that the degree of the initial graph $G$ is bounded by a constant, repeatedly sparsifying the graph could seriously increase its maximum degree. Fortunately, our dynamic spanner guarantees that the average degree after edge sparsification is low. However, the same cannot be achieved for the maximum degree, which becomes apparent when trying to sparsify a star graph.

  To remedy this issue, we use that the underlying graph has bounded degree and call the $\text{ReduceDegree}(\cdot )$ routine of the KMG-vertex sparsifier to reduce the degree of high-degree vertices in the spanner. This operation can lead to changes in $\tilde{G}$ and its spanner, but we show that repeatedly splitting vertices with high degree in the spanner quickly converges because the progress of splits is larger than the recourse they cause to the spanner.

The edge sparsification algorithm is presented in Section 4.4.

We use the KMG-vertex sparsifier algorithm [16], which is based on dynamic core graphs, which in turn are based on static low-stretch spanning trees.

We first introduce certified pivots. These are mapping vertices that get sparsified away to vertices in $\tilde{G}$, and certify the distance for vertices that are closer to each other than to their respective pivots.

To motivate Definition 15, we show that pivots can be used to approximate the distance between sparsified vertices whenever their exact distance isn’t stored already.

We state our main dynamic spanner theorem whose proof is deferred to the full version of our article. The theorem assumes access to a ${\gamma }_{apxAPSP}$-approximate, $\tilde{O}(1)$-query APSP data structure (See Definition 7.)

We are given an edge-dynamic graph $G$ on initially $n$ vertices and $m$ edges, that at all times has maximum degree at most $\mathrm{\Delta }$. Applying Theorem 17 to $G$ reduces the problem to finding short paths in $\tilde{G}$, a graph of $\tilde{O}(m/k)$ vertices. Although the number of vertices significantly decreases, the graph still contains up to $\tilde{O}(m)$ edges, preventing efficient recursion. To address this, we apply Theorem 18 on $\tilde{G}$ to produce a graph $H$ on $\gamma \cdot m/k$ vertices and edges, where $\gamma$ crucially depends only on the parameter $K$ of Theorem 18.

Note that the APSP data structure that Theorem 18 requires also only needs to run on a graph of at most $\gamma \cdot m/k$ vertices and edges, so by choosing a large enough size reduction factor $k$, the problem size reduces by a factor of $\gamma /k$, while the approximation factor increases from to .⁴⁴4We only have a valid size reduction if also . We will see that this is indeed the case as we can assume that initially $m=O(n)$. Balancing both parameters $k$ and $K$ allows us to bootstrap an APSP data structure with the guarantees from Theorem 1.

While $H$ is sparse, it might still have high maximum degree, preventing efficient recursion. The sparsity still implies, however, that there cannot be too many high degree vertices. Hence, we carefully perform a few vertex splits in $\tilde{G}$ by leveraging the $\text{ReduceDegree}(\cdot )$ functionality from Theorem 17 to enforce that $H$ also has small maximum degree.

The recursive APSP instance that is running on $H$ expects an edge-dynamic graph, while the spanner from Theorem 18 is fully-dynamic. To circumvent this issue, we simulate the vertex splits by suitable edge insertions/removals and vertex insertions. As the maximum degree of $H$ gets controlled during the while loops, this simulation can lead to at most an extra factor of $O({\gamma }_{degConstr}\cdot \mathrm{\Delta })$ in the number of updates.

When queried for the distance between two vertices $u$ and $v$, our algorithm checks if the certified pivot function stores the distance, and if this is not the case it recursively asks the smaller instance ${\text{DynamicAPSP}}_H$ for the distance between $p(u)$ and $p(v)$ in $H$.

We first show that the while loops in Algorithm 1 and Algorithm 2 terminate sufficiently fast. This is the most crucial claim for the analysis.