On the other hand, since $u \in B_{j+1}(v)$ we also have $\tau(v) - \tau(u) \geq 2^j$. We can thus charge $n/(2 \epsilon \delta)$ units from $\mathcal{T}(\pi_{r,t}, \tau)$ for each additive error unit; we know from Equation <ref> that $\mathcal{T}(\pi_{r,t}, \tau) \leq n$, so the total additive error is at most
$\frac{n}{n/(2\epsilon \delta)} = 2\epsilon\delta$. Thus, for all distances $\approx \delta$ (say in $[\delta/2, \delta)$), we obtain a $(1+4\epsilon)$-multiplicative distance estimate[Technically, we run to depth $(1+4\epsilon)\delta$ to ensure that vertices' distance estimates are not set to $\infty$ too early.].

Working with Multiple Distance Scales. Observe that the data structure above has no running time dependency on $\delta$. Thus, to obtain a data structure that maintains a $(1+2\epsilon)$-approximate distance estimate from $r$ to any vertex $x$, we can simply use $\lg(nW)$ data structures in parallel where the $i^{th}$ data structure has $\delta = 2^i$. A query can then be answered by returning the smallest distance estimate from any data structure, using a min-heap data structure to obtain this smallest estimate in constant time[Here, we exploit that all distance estimates are overestimates, and at least one of them is $(1+2\epsilon)$-approximate.]. The running time for all data structures is then bounded by $\tilde{O}(n^2 \log W /\epsilon)$.

§.§ Extending the Result to General Graphs

We now encourage the reader to verify that in the data structure for DAGs, we used at no point that the graph was acyclic, but rather only used that $\mathcal{T}(\pi_{s,t}, \tau)$ is bounded by $n$ for any path $\pi_{s,t}$. In this light, it might be quite natural to ask whether such a function $\tau$ might exist for general decremental graphs. Surprisingly, it turns out that after carrying out some contractions in $G$ that only distort distances slightly, we can find such a function $\tau$ that comes close in terms of guarantees. We call such a function $\tau$ an approximate topological order (this function will no longer encode guarantees about reachability, but it helps for intuition to think of $\tau$ as being similar to a topological order).

The Approximate Topological Order We start with the formal definition:

Given a decremental weighted digraph $G = (V,E,w)$ and parameter $\eta_{diam} \geq 0$. We call a dynamic tuple $(\mathcal{V}, \tau)$ an approximate topological order of $G$ of quality $q > 1$ (abbreviated $\mathcal{ATO}(G, \eta_{diam})$ of quality $q$), if at any stage

* $\mathcal{V} = \{ X_1, X_2, .., X_k\}$ forms a partition of $V$ and a refinement of all earlier versions of $\mathcal{V}$,  and

* $\tau : \mathcal{V} \rightarrow [0, n)$ is a function that maps each $X \in \mathcal{V}$ to a value $\tau(X)$. If some set $X \in \mathcal{V}$ is split at some stage into disjoint subsets $X_1, X_2, .., X_k$, then we let $\tau(X_{\pi(1)}) = \tau(X)$ and $\tau(X_{\pi(j+1)}) = \tau(X_{\pi(j)}) + |X_{\pi(j)}|$ for each $j < k$ and some permutation $\pi$ of $[1, k]$, and

* each $X \in \mathcal{V}$ has weak diameter $\mathbf{diam}(X, G) \leq \frac{|X| \eta_{diam}}{n}$, and

*  for any two vertices $s, t \in V$, the shortest path $\pi_{s,t}$ in $G$ satisfies $\mathcal{T}(\pi_{s,t}, \tau) \leq q \cdot w(\pi_{s,t}) + n$ where we define $\mathcal{T}(\pi_{s,t}, \tau) \stackrel{\text{def}}{=} \sum_{(u,v) \in \pi_{s,t}} |\tau(X^u) - \tau(X^v)|$.

We say that $(\mathcal{V}, \tau)$ is an $\mathcal{ATO}(G, \eta_{diam})$ of expected quality $q$, if $(\mathcal{V}, \tau)$ satisfies properties <ref>-<ref>, and at any stage, for every $s,t \in V$, $\mathbb{E}[\mathcal{T}(\pi_{s,t}, \tau)] \leq q \cdot w(\pi_{s,t}) + n$.

Let us expound the ideas captured by this definition. We remind the reader that such a function $\tau$ is required by a data structure that only considers distances in $[\delta/2, \delta)$. Let us consider a tuple $(\mathcal{V}, \tau)$ that forms an $\mathcal{ATO}(G, \epsilon \delta)$ of quality $q$. Then, for any $s$-to-$t$ shortest path $\pi_{s,t} = \langle s = v_1, v_2, \dots v_{\ell} = t\rangle$ in $G$, let $s_i$ and $t_i$ be the first and last vertex on the path in $X_i \in \mathcal{V}$ (see property <ref>) if there are any. Observe that by property <ref>, the vertices $s_i$ and $t_i$ are at distance at most $\frac{|X_i|\epsilon \delta}{n}$ in $G$. It follows that if we contract the SCC $X_i$, the distance $\mathbf{dist}_{G / X_i}(s,t)$ is at least the distance from $s$ to $t$ in $G$ minus an additive error of at most $\frac{|X_i|\epsilon \delta}{n}$. It follows straight-forwardly, that after contracting all sets in $\mathcal{V}$, we have that distances in $G / \mathcal{V}$ correspond to distances in $G$ up to a negative additive error of at most $\sum_{X_i \in \mathcal{V}} \frac{|X_i| \epsilon\delta}{n} = \frac{n \cdot \delta\epsilon}{n} = \epsilon \delta$. Thus, maintaining the distances in $G / \mathcal{V}$ $(1+2\epsilon)$-approximately is still sufficient for getting a $(1 \pm 2\epsilon)$-approximate distance estimate.

Property <ref> simply ensures that the vertex sets forming the elements of $\mathcal{V}$ decompose over time. Property <ref> states that $\tau$ assigns each node in $G / \mathcal{V}$ a distinct number in $[0,n)$. It also ensures that if a set $X \in \mathcal{V}$ receives $\tau(X)$ that every later subset of $X$ will obtain a number in the interval $[\tau(X), \tau(X) + |X|)$. Moreover, $\tau$ effectively establishes a one-to-one correspondence between nodes in a version of $G / \mathcal{V}$ and intervals in $[0, n)$ of size equal to their underlying vertex set. Once a set $X\in\mathcal{V}$ decomposes into sets $X_1, X_2, \dots$, property <ref> stipulates that the intervals that $\tau$ maps $X_1, X_2, \dots$ to are disjoint subintervals of $[\tau(X), \tau(X) + |X|)$. We point out that once $\mathcal{V}$ consists of singletons, each vertex is essentially assigned a single number.

Finally, property <ref> gives an upper bound on the topological order difference. Observe that we redefine $\mathcal{T}(\pi_{s,t}, \tau)$ in a way that is consistent with Definition <ref>.
In our algorithm, for $\eta_{diam} \approx \epsilon\delta$, we obtain a quality of $\tilde{O}(n/\epsilon\delta)$. Thus, any path $\pi$ of weight $\approx \delta$ has $\mathcal{T}(\pi / \mathcal{V}, \tau) \leq \tilde{O}(n / \epsilon)$ which is very close to the upper bound obtained by the topological order function in DAGs. We summarize this result in the theorem below which is one of our main technical contributions.

theoremATOResultIntro[see <Ref> and <Ref>.]

For any $0 \leq i \leq \lg(Wn)$, given a decremental digraph $G=(V,E,w)$, we can maintain an $\mathcal{ATO}(G, 2^i)$ of expected quality $\tilde{O}(n/2^i)$. The algorithm runs in total expected update time $\tilde{O}(n^2)$ against a non-adaptive adversary with high probability.

Combining the theorem above and the theorem below which is obtained by generalizing the above decremental SSSP algorithm for DAGs, we obtain our main result <Ref>.

theoremssspSuperSimple[see <Ref>.]

Given $G=(V,E,w)$ and $(\mathcal{V}, \tau)$ an  $\mathcal{ATO}(G, \eta_{diam} \approx \epsilon\delta)$, for some depth parameter $\delta > 0$, of quality $q$, a dedicated source $r$ in $V$, and an approximation parameter $\epsilon > 0$. Then, there exists a deterministic data structure $\mathcal{E}_r$ that maintains a distance estimate $\widetilde{\mathbf{dist}}(r,v)$ for each $v \in V$, which is guaranteed to be $(1+\epsilon)$-approximate if ${\mathbf{dist}}(r,v) \in [\delta, 2\delta)$. Distance queries are answered in $O(1)$ time and a corresponding path $P$ can be returned in $O(|P|)$ time. The total update time is $\tilde{O}(n \delta q/\epsilon + n^2)$.

§.§ The Framework by Gutenberg and Wulff-Nilsen

Before we describe our new result, we review the framework in <cit.> to construct and maintain an $\mathcal{ATO}(G, \eta_{diam})$. We point out that while the abstraction of an approximate topological order is new to our paper, analyzing the technique in <cit.> through the $\mathcal{ATO}$-lens is straight-forward and gives a first non-trivial result. Throughout this review section, we assume that the graph $G$ is unweighted to simplify presentation. This allows us to make use of the following result which states that for vertex sets that are far apart, one can find deterministically a vertex separator that is small compared to the smaller side of the induced partition (to obtain an algorithm for weighted graphs a simple edge rounding trick is sufficient to generalize the ideas presented below).

Given graph $G = (V,E,w)$, then we say a partition of $V$ into sets $A, S_{Sep}, B$ is a one-way vertex separator if $A \not\leadsto_{G \setminus S_{Sep}} B$ and $A$ and $B$ are non-empty.

Given an unweighted graph $G$ of diameter $\mathbf{diam}(G)$. Then we can find sets $A, S_{Sep}, B$ that form a one-way vertex separator such that $|S_{Sep}| \leq \tilde{O}(\frac{\min\{|A|, |B|\}}{\mathbf{diam}(G)})$ in time $O(m)$.

High-level Framework. The main idea of <cit.> is to maintain a tuple $(\mathcal{V}, \tau)$ which is an $\mathcal{ATO}(G, \eta_{diam})$ by setting $(\mathcal{V}, \tau)$ to be $\textsc{GeneralizedTopOrder}(G')$ of some decremental graph $G' \subseteq G$ (over the same vertex set, i.e. $V(G') = V(G)$). It is straight-forward to see that $(\mathcal{V}, \tau)$ satisfies property <ref> in <Ref>, since SCCs in the decremental graph $G'$ decompose. Further, it is not hard to extend the existing algorithm for maintaining SCCs in a decremental graph $G'$ given in <cit.> to also maintain function $\tau$ that obeys property <ref> in <Ref>. The algorithm to maintain $(\mathcal{V}, \tau)$ given $G'$ runs in total update time $\tilde{O}(m)$ (same as in <cit.>).

So far, we have not given any reason why $G'$ needs to be a subgraph of $G$. To see why we cannot use the above strategy on $G$ directly, recall property <ref> in the $\mathcal{ATO}$-definition <ref>, which demands that each SCC $X$ has weak diameter at most $\frac{|X|\eta_{diam}}{n}$. This property might not hold in the main graph $G$. In order to resolve this issue, $G'$ is initialized to $G$ and then the diameter of SCCs in $G'$ is monitored. Whenever an SCC $X$ violates property <ref>, a vertex separator $S_{Sep}$ is found in the graph $G'[X]$ as described in <Ref> and all edges incident to $S_{Sep}$ are removed from $G'$. Letting $S$ denote the union of all such separators $S_{Sep}$, we can now write $G' = G \setminus E(S)$.

Establishing the Quality Guarantee. To establish a quality $q$ of the $\mathcal{ATO}$ as described in property <ref> in <Ref>, let us first partition the set $S$ into sets $S_0, S_1, \dots, S_{\lg n}$ where each $S_i$ contains all separator vertices found on a graph of size $[n/2^i, n/2^{i+1})$, thus it was found when the procedure from <Ref> was invoked on a graph with diameter at least $\frac{(n/2
^{i+1})\eta_{diam}}{n} =  \frac{\eta_{diam}}{2
^{i+1}}$. Since separators are further balanced, i.e. there size is controlled by the smaller side of the induced cut, we can further use induction and <Ref> to establish that there are at most $\tilde{O}(\frac{2^i n}{\eta_{diam}})$ vertices in $S_i$. Next, observe that since any separator that was added to $S_i$ was found in a graph $G'[X]$ with $|X| \in [n/2^i, n/2^{i+1})$, we have by property <ref> that nodes $X' \subseteq X$ that are in the current version of $\mathcal{V}$ are assigned a $\tau(X')$ from the interval $[\tau(X), \tau(X) + |X|)$. Thus, any edge $(x,s)$ or $(s,x)$ with $x \in X, s \in S_i \cap X$ has topological order difference $|\tau(X^x) - \tau(X^s)| \leq |X| \leq n/2^i$.

Finally, let us define

\begin{equation}
\label{eq:redefT}
\mathcal{T}'(\pi_{s,t}, \tau) \stackrel{\text{def}}{=} \sum_{(u,v) \in \pi_{s,t}} \min\{0, \tau(X^v) - \tau(X^u)\}
\end{equation}

the function similar to $\mathcal{T}(\pi_{s,t}, \tau)$ that only captures negative terms, i.e. sums only over edges that go "backwards" in $\tau$. Observe that $\mathcal{T}(\pi_{s,t}, \tau) \leq 2 \mathcal{T}'(\pi_{s,t}, \tau) + n$. Now, since $(\mathcal{V}, \tau)$ is a $\textsc{GeneralizedTopOrder}(G')$, we have that $(u,v)$ occurs in the sum of $\mathcal{T}'(\pi_{s,t}, \tau)$ if and only if $(u,v) \in G \setminus G'$, so one endpoint is in a set $S_i$ and therefore $\tau(X^v) -\tau(X^u) \leq n/2^i$. Since we only have two edges on any shortest path incident to the same vertex, we can establish that

\[
\mathcal{T}'(\pi_{s,t}, \tau) \leq \sum_{i} 2|S_i| n/2^i = \tilde{O}(n^2/\eta_{diam}).
\]

We obtain that $(\mathcal{V}, \tau)$ is a $\mathcal{ATO}(G, \eta_{diam})$ of quality $\tilde{O}(\frac{n^2}{2^i\eta_{diam}})$ for all paths of weight at least $2^i$. Thus, when the distance scale $\delta \geq \sqrt{n}/\epsilon$, <Ref> requires total update time $\approx n^{2.5}$ to maintain $(1+\epsilon)$-approximate SSSP. For distance scales where $\delta < \sqrt{n}/\epsilon$, a classic ES-tree has total update time $\approx m\sqrt{n} \leq n^{2.5}$.

Limitations of the Framework.
Say that the goal is to  maintain shortest paths of length around $\sqrt{n}$.
The first step in the framework of <cit.> is to find separator $S$ such that all SCCs of $G' = G \setminus E(S)$ have diameter at most $\epsilon \sqrt{n}$ and then maintain $(\mathcal{V},\tau) =$ GeneralizedTopOrder($G'$).  Every edge $(u,v) \notin E(S)$ will only go forward in $\tau$, but each edge $(u,s)$, for $s \in S$, can go “backwards" in $\tau$. By the nesting property of generalized topological orders, the amount that $(u,s)$ goes backwards – i.e. the quantity $|\tau(X^u) - \tau(X^s)|$ – is upper bounded by the size of the SCC in $G'$ from which $s$ was chosen: the original SCC has size $n$, but as we add vertices to $S$, the SCCs of $G' = G \setminus E(S)$ decompose and new vertices added to $S$ may belong to smaller SCCs. Define $S^* \subseteq S$ to contain all vertices $s \in S$ that were chosen in an SCC of size $\Omega(n)$. Intuitively, $S^*$ is the top-level separator chosen in $G$, before SCCs decompose into significantly smaller pieces. Every edge in $E(S^*)$ may go backwards by as much as $n$ in $\tau$, so for any path $\pi_{x,y}$ in $G$, the best we can guarantee is that $\mathcal{T}(\pi_{x,y}) \sim n \cdot |\pi_{x,y} \cap S^*|$.

The framework of <cit.> tries to find a small separator $S^*$ and then uses the trivial upper bound $|\pi_{x,y} \cap S^*| \leq |S^*|$. In fact, one can show that given any deterministic separator procedure, the adversary can pick a sequence of updates where $|\pi_{x,y} \cap S^*| \sim |S^*|$. But now, say that $G$ is a $\sqrt{n} \times \sqrt{n}$-grid graph with bidirectional edges. It is not hard to check that  $|S^*| = \Omega(\sqrt{n})$, because every balanced separator of a grid has $\Omega(\sqrt{n})$ vertices. The framework of <cit.> can thus at best guarantee  $\mathcal{T}(\pi_{x,y}) \sim n \cdot |\pi_{x,y} \cap S^*| \sim n|S^*| = \Omega(n^{1.5})$, which is a $\sqrt{n}$ factor higher than it would be in a DAG, and thus leads to running time $\tilde{O}(n^{2.5})$ instead of $\tilde{O}(n^2)$.

Our algorithm uses an entirely different random separator procedure. We allow $S^*$ to be arbitrarily large, but use randomness to ensure that $|\pi_{x,y} \cap S^*|$ is nonetheless small.

§.§ Our Improved Framework

We now introduce our new separator procedure and then show how it can be used in a recursive algorithm that uses ATOs of worse quality (large $q$) to compute ATOs of better quality (small $q$). (By contrast, the framework of <cit.> could not benefit from a multi-layered algorithm because it would still hit upon the fundamental limitation outlined above.)

A New Separator Procedure. Before we describe the separator procedure, let us formally define the guarantees that we obtain. In the lemma below, think of $\zeta = \Theta(\log(n))$.

There exists a procedure $\textsc{OutSeparator}(r, G, d, \zeta)$ where $G$ is a weighted graph, $r \in V$ a root vertex, and integers $d, \zeta > 0$. Then, with probability at least $1- e^{-\zeta}$, the procedure computes a tuple $(E_{Sep}, V_{Sep})$ where edges $E_{Sep} \subseteq E$, and vertices $V_{Sep} = \{ v \in V | r \leadsto_{G \setminus E_{Sep}} v\}$ such that

* for every vertex $v \in V_{Sep}$, $\mathbf{dist}_{G \setminus E_{Sep}}(r,v) \leq d$, and

* for every $e \in E$, we have $\mathbb{P}[e \in E_{Sep} | r \leadsto_{G \setminus E_{Sep}} \mathbf{tail}(e)] \leq \frac{\zeta}{d}w(e)$.

Otherwise, it reports $\mathbf{Fail}$. The running time of $\textsc{OutSeparator}(\cdot)$ can be bounded by $O(|E(V_{Sep})|\log n)$.

In fact, <Ref> gives a simple implementation of procedure $\textsc{OutSeparator}(\cdot)$. Here, we pick a ball $B = B^{out}(r, X)$ in the graph $G$ from $r$ to random depth $X$, and then simply return the tuple $(E_{Sep}, V_{Sep}) = (E(B, \overline{B}), B)$ where $E(B, \overline{B})$ are the edges $(u,v)$ with $u \in B$ but $v \not\in B$. The procedure thus only differs from a standard edge separator procedure in that we choose $X$ according to the exponential distribution $\textsc{Exp}(\frac{\zeta}{d})$.

$\textsc{OutSeparator}(r, G, d, \zeta)$

Choose $X \sim \textsc{Exp}(\frac{\zeta}{d})$.
$X \geq d$Fail
Compute the Ball $B = B^{out}(r, X) = \{ v \in V | \mathbf{dist}(r,v) \leq X\}$
$(E(B, \overline{B}), B)$

A proof of Lemma <ref> is now straightforward. We return Fail in <Ref> with probability $\mathbb{P}[X \geq d] = 1 - F_X(d) = 1 - (1 - e^{- \frac{\zeta}{d} \cdot d}) = e^{-\zeta}$ (recall from <ref> that $F_X(d)$ is shorthand for $F(x, \frac{\zeta}{d})$, the cumulative distribution function of an exponential distribution with parameter $ \frac{\zeta}{d}$). Assuming no failure, we have $E_{Sep} = E(B, \overline{B})$, and it is easy to see that $V_{Sep} = \{ v \in V | r \leadsto_{G \setminus E_{Sep}} v \} = B$, so Property 1 of Lemma <ref> holds by definition of $B$. Moreover, we can compute $B$ in the desired $O(|E(B)|\log n)$ time by using Dijkstra's algorithm by only extracting a vertex from the heap if it is at distance at most $X$. Finally, for property <ref>, note that $e \in E_{sep}$ iff $\dist(r, \mathbf{tail}(e)) \leq X < \dist(r, \mathbf{tail}(e)) + w(e)$. Thus,

\begin{align*}
\mathbb{P}[e \in E_{Sep} | r \leadsto_{G \setminus E_{Sep}} \mathbf{tail}(e)]
&= \mathbb{P}[X < \mathbf{dist}(r,\mathbf{tail}(e)) + w(e) | X \geq \mathbf{dist}(r,\mathbf{tail}(e))]\\
&= \mathbb{P}[X < w(e)] = F_X(w(e)) = 1 - e^{- \frac{\zeta}{d} w(e)} \\
&\leq 1 - \left(1 - \frac{\zeta}{d} w(e)\right) = \frac{\zeta}{d} w(e)
\end{align*}

where the second equality follows from the memory-less property of the exponential distribution, and the inequality holds because $1 + x \leq e^x$ for all $x \in \mathbb{R}$. We point out that the technique of random ball growing using the exponential distribution is not a novel contribution in itself and has be previously used in the context of low-diameter decompositions <cit.> which have recently also been adapted to dynamic algorithms <cit.>.

A New Framework. Let us now outline how to use <Ref> to derive
<Ref> which is stated below again. The full details and a rigorous proof are provided in <Ref>.

As in <cit.>, we maintain a graph $G' \subseteq G$ and its generalized topological order $(\mathcal{V}, \tau)$. Whenever the diameter of an SCC $X$ in $G'$ is larger than $\frac{|X|\eta_{diam}}{n}$, we now use the separator procedure described in <Ref> with $d = \frac{|X|\eta_{diam}}{2n}$ from some vertex $r$ in $X$ with $|B^{out}(r, d = \frac{|X|\eta_{diam}}{2n})| \leq |X|/2$. Such a vertex exists since by definition of diameter, as we can find two vertices with disjoint balls. We obtain an edge separator $E_{Sep}$ and update $G'$ by removing the edges in $E_{Sep}$. Let the union of all edge separators be denoted by $F$ and again observe that $G' = G \setminus F$. It is not hard to see that our scheme still ensures properties <ref>-<ref> in <Ref>. We now argue that the quality improved to $\tilde{O}(n/2^i)$.

Partition $F$ into sets $F_0, F_1, \dots, F_{\lg n}$ where each $F_j$ contains all separator edges found on a graph of size $[n/2^{j+1}, n/2^j)$. We again have that every edge $(u,v) \in F_j$ has $|\tau(X^u) - \tau(X^v)| \leq n/2^{j}$. Let us establish an upper bound on the number of edges in $F_j$ on any shortest path $\pi_{s,t}$. Consider therefore any edge $e \in \pi_{s,t}$, at a stage where both endpoints of $e$ are in a SCC $X$ of size $[n/2^{j+1}, n/2^j)$ and where we compute a tuple $(V_{Sep}, E_{Sep})$ from some $r \in X$. Now, observe that if $\mathbf{tail}(e) \not\in V_{Sep}$, then $e$ can not be in $E_{Sep}$. So assume that $\mathbf{tail}(e) \in V_{Sep}$. Then, we have $e$ joining $F_j$ with probability

\[
\mathbb{P}[e \in E_{Sep} | r \leadsto_{H \setminus E_{Sep}} \mathbf{tail}(e)] = \frac{\zeta}{2^i|X|/n} w(e) = \tilde{O}\left(\frac{2^j w(e)}{2^i}\right)
\]

according to <Ref>, where we set $\zeta = \tilde{O}(1)$ to obtain high success probability. But if $e$ did not join $F_j$ at that stage, then it is now in a SCC of size at most $n/2^{j+1}$ (recall we chose $|B^{out}(r, d)| \leq |X|/2$, and we have $V_{Sep} \subseteq B^{out}(r, d)$). Thus, $e$ cannot join $F_j$ at any later stage.

Now, it suffices to sum over edges on the path $\pi_{s,t}$ and indices $j$ to obtain that

\[
\mathcal{T}'(\pi_{s,t}, \tau) \leq \sum_{e \in \pi_{s,t}} \sum_{j} \mathbb{P}[e \in F_j] \cdot n/2^{j} = \sum_{e \in \pi_{s,t}} \sum_{j} \tilde{O}\left(\frac{2^j w(e)}{2^i}\right) \cdot n/2^{j} = \tilde{O}\left(\frac{ w(\pi_{s,t}) n}{2^i}\right)
\]

giving quality $\tilde{O}\left(\frac{n}{2^i}\right)$.

Efficiently Maintaining $G'$.

As shown above, maintaining an $\mathcal{ATO}(G,2^i)$ requires detecting when any SCC in $G' = G \setminus E(S)$ has diameter above $2^i$. We start by showing how to do this efficiently if we are given a black-box algorithm $\asssp$ that maintains distance estimates up to depth threshold $2^i$  (i.e. if a vertex is at distance less than $2^i$ from the source vertex, there is a distance estimate with good approximation ratio).

We use the random source scheme introduced in <cit.> along with some techniques developed in <cit.>: we choose for each SCC $X$ in $G'$ a center vertex $\textsc{Center}(X) \in X$ uniformly at random, and use $\asssp$ to maintain distances from $\textsc{Center}(X)$ to depth $2^i|X|/n \leq 2^i$. Since the largest distances between the vertex $\textsc{Center}(X)$ and any other vertex in $X$ is a $2$-approximation on the diameter of $G[X]$, this is sufficient to monitor the diameter and to trigger the separator procedure in good time.

Cast in terms of our new ATO-framework, the previous algorithm of <cit.> used a regular Even and Shiloach tree for the algorithm $\asssp$. We instead use a recursive structure, where $\mathcal{ATO}s$ of bad quality (large $q$) are used to build $\mathcal{ATO}s$ of better quality (small $q$). Recall that our goal is to build an $\mathcal{ATO}(G, 2^{i})$ of quality $\tilde{O}(n/2^i)$ and say that $X$ is some SCC of $G' = G \setminus E(S)$ whose diameter we are monitoring. Now, using the lower level of the recursion, we inductively assume that we can maintain an $\mathcal{ATO}(G'[X], 2^{i-1})$ of quality $\tilde{O}(n/2^{i-1})$ in time $\tilde{O}(|X|^2)$. Plugging this $\mathcal{ATO}$ into <Ref> gives us an algorithm for maintaining distances up to depth $2^i$ in $X$ with total update time $\tilde{O}(|X|^2)$, Summing over all components $X$ in $G'$, we get an $\tilde{O}(n^2)$ total update time to maintain $\mathcal{ATO}(G, 2^{i})$, as desired.

We actually cheated a bit in the last calculation, because the scheme above could incur an additional logarithmic factor for computing $\mathcal{ATO}(G, 2^i)$ from all the $\mathcal{ATO}(G'[X], 2^{i-1})$, so we can only afford a sublogarithmic number of levels, which leads to an extra $n^{o(1)}$ factor in the running time. However, a careful bootstrapping argument allows us to avoid this extra term.

§.§ Organization

We recommend the reader to carefully study <Ref> to gain necessary intuition for our approach. In <Ref>, we give an efficient reduction from maintaining an approximate topological order to depth-restricted SSSP. This section is the centerpiece of the article and its main result, <Ref>, is one of our main technical contributions. We then show how to use <Ref> to obtain a SSSP data structure for dense graphs in <Ref>.

§ REDUCING MAINTENANCE OF AN ATO TO SSSP

In this section, we show how to obtain an $\mathcal{ATO}$ given an $\alpha$-approximate $\delta$-restricted $\mathcal{SSSP}$ data structure. We start by defining such a data structure and then give a reduction.

Let $\mathcal{A}$ be a data structure that given any decremental directed weighted graph $G$, a dedicated source $r \in V$, an approximation parameter $\alpha > 1$, maintains for each vertex $v \in V$, distance estimates $\widetilde{\mathbf{dist}}(r,v)$ and $\widetilde{\mathbf{dist}}(v,r)$ such that at any stage of $G$, for every pair $(s,t) \in (\{r\} \times V) \cup (V \times \{r\})$

* we have $\mathbf{dist}(s,t) \leq \widetilde{\mathbf{dist}}(s,t)$, and

* if $\mathbf{dist}(s,t) \leq \delta$, then $\widetilde{\mathbf{dist}}(s,t) \leq \alpha \mathbf{dist}(s,t)$.

Then, we say $\mathcal{A}$ is an $\alpha$-approximate $\delta$-restricted $\mathcal{SSSP}$ data structure with running time $T_{SSSP}(m,n,\delta,\alpha)$. We require only that $\mathcal{A}$ runs against a non-adaptive adversary.

In the rest of the article, we implicitly assume that all $\mathcal{SSSP}$ data structures have $T_{SSSP}(m,n,\delta,\alpha)$ monotonically increasing in the first two parameters.

We also need another definition that makes it more convenient to work with $\mathcal{ATO}$s that only have expected quality (see <Ref>). However, we require high probability bounds in our constructions and it will further be easier to work with deterministic objects. This inspires the definition of an $\mathcal{ATO}$-bundle which is a collection of $\mathcal{ATO}$s such that for each path of interest, there is at least one $\mathcal{ATO}$ in the bundle that has good quality for the path at-hand.

Given a decremental weighted directed graph $G = (V,E,w)$ and parameter $\eta_{diam} \geq 0$. We call $\mathcal{S} = \{ (\mathcal{V}_i, \tau_i)\}_{i \in [1, \ell]}$ an $\mathcal{ATO}(G, \eta_{diam}, \ell)$-bundle of quality $q$ if every $(\mathcal{V}_i, \tau_i)$ is an $\mathcal{ATO}(G, \eta_{diam})$ and for any two vertices $s, t \in V$, there exists an $i \in [1, \ell]$, such that the shortest path $\pi_{s,t}$ in $G$ satisfies $\mathcal{T}(\pi_{s,t}, \tau_i) \leq q \cdot w(\pi_{s,t}) + n$.

Without further due, let us state and prove the main result of this section.

[$\mathcal{ATO}$-bundle from $\mathcal{SSSP}$]theorematoBundle

Given an algorithm $\mathcal{A}$ to solve $2$-approximate $\delta$-restricted $\mathcal{SSSP}$ on any graph $H$ in time $T_{SSSP}(m,n,\delta)$, and for any $c > 0$, we can maintain an $\mathcal{ATO}(G, 2\alpha\delta, 40 c \log n)$-bundle of quality $\frac{(c+2)40000 n \log^5 n}{\delta}$ in total expected update time

\begin{equation}\label{eq:totalRunningTime}
O\left(\sum_{j=0}^{\lceil\lg \delta \rceil} \; \sum_{k=0}^{2^{j+3} c \log^2 n} T_{SSSP}(m_{j,k}, n/2^{j}, \delta, 2) + m \log^3 n\right)
\end{equation}

where $\sum_j m_{j,k} \leq 16c \cdot m \log^2 n$ for all $k$. The algorithm runs correctly with probability $1 - n^{-c}$ for any $c > 0$.

The graphs that the data structure $\mathcal{A}$ runs upon during the algorithm are vertex-induced subgraphs of $G$. The data structure $\mathcal{A}$ is further allowed to maintain distances on a larger subgraph of $G$, i.e. when $\mathcal{A}$ is applied to a graph $G[X]$, it can run instead on $G[Y]$ for any set $X \subseteq Y \subseteq V$.

We point out that <Ref> is only of importance at a later point at which the reader will be reminded and can safely be ignored for the rest of this sections (the reader is however invited to verify its correctness which is easy to establish).

We now describe how to obtain an efficient algorithm that obtains an $\mathcal{ATO}(G,2\alpha \delta)$ henceforth denoted by $(\mathcal{V}, \tau)$. The next sections describe how to initialize $(\mathcal{V}, \tau)$, how to maintain useful data structures to maintain the diameter, give the main algorithm and then a rigorous analysis. Finally, we obtain a $\mathcal{ATO}(G, 2\alpha\delta, 40 c \log n)$-bundle by running $40 c \log n$ independent copies of the algorithm below.

§.§ Initializing the Algorithm

As described in <Ref>, our goal is to maintain a graph $G'$ that is a subgraph of $G$ and satisfies that no SCC $X$ in $G'$ has weak diameter $\mathbf{diam}(X,G)$ larger than $\frac{ \delta |X|}{n}$. Throughout, we maintain the generalized topological order $(\mathcal{V}, \tau)$ on $G'$ where $\tau$ has the nesting property as described in <Ref>.

To ensure the diameter constraint initially, we use the following partitioning procedure whose proof can be found in <cit.>.

[Partitioning Procedure]lemmapartition

Given an algorithm $\mathcal{A}$ to solve $2$-approximate $\delta$-restricted $\mathcal{SSSP}$. There exists a procedure $\textsc{Partition}(G, d, \zeta)$ that takes weighted digraph $G$, a depth threshold $d \leq \delta$ and a success parameter $\zeta > 0$, and returns a set $E_{Sep} \subseteq E$ such that

* for each SCC $X$ in $G \setminus E_{Sep}$, we have for any vertices $u,v \in X$ that $\mathbf{dist}_{G \setminus E_{Sep}}(u,v) \leq d$, and

for $e \in E$, we have
$\mathbb{P}[e \in E_{Sep}] \leq \frac{240 \zeta \log^2 n}{d}w(e).$

The algorithm runs in total expected time

\[
O\left(\sum_{j=0}^{\lceil\lg \delta \rceil} \; \sum_{k=0}^{2^{j+1}} T_{SSSP}(m_{j,k}, n/2^{j}, \delta, 2) + m \log^2 n\right)
\]

where we have that $\sum_{k=0} m_{j,k} \leq 2m$ for every $i$. The algorithm terminates correctly with probability $1-e^{-\zeta}$ for any $c > 0$.

During the execution, the graphs on which we use the $\mathcal{SSSP}$ structure upon have the properties as described in <Ref>.

Let $G'$ be initialized to $G$.
$i = 0$ to $\lceil\lg \delta \rceil$
Compute the SCCs $\mathcal{V}$ of $G'$
SCC $X$ in $\mathcal{V}$, $|X| \leq n/2^i$
$E_{Sep} \gets \textsc{Partition}(G[X], \delta/ 2^i, (c+2)\log n)$
$G' \gets G' \setminus E_{Sep}$

Using this procedure, it is straight-forward to initialize our algorithm. The pseudo-code of the initialization procedure is given in <Ref>. Here, we iteratively apply the partitioning procedure to SCCs of small size to decompose them further if their diameter is too large. It is not hard to establish that the graph $G'$ returned by the procedure, satisfies that every SCC $X$ in $G'$ has $\mathbf{diam}(X,G)\leq \frac{\delta |X|}{n}$.

§.§ Maintaining Information about SCC Diameters

Before we describe how to maintain $G'$ to satisfy the guarantees given above, we address the issue of maintaining information about the diameter of the current SCCs in $G'$.

Therefore, we maintain a set $S$ of random sources throughout the algorithm, and from each $s \in S$, we run an $\alpha$-approximate $\delta$-restricted $\mathcal{SSSP}$ data structure $\mathcal{A}_s$. Initially $S = \emptyset$, and whenever there is an SCC $X$ in $\mathcal{V}$ (which is maintained by the data structure on $G'$), and we find $S \cap X = \emptyset$, we pick a vertex $s$ uniformly at random from $X$ and add it to $S$. Once added, we initialize and maintain an $\alpha$-approximate $\delta$-restricted $\mathcal{SSSP}$ data structure $\mathcal{A}_s$ on the current version of $G[X]$. That is, even if $X$ does not form an SCC at later stages, the data structure is run until the rest of the algorithm on the graph $G[X]$. This ensures that once the algorithm is invoked, all edge updates are determined by the adversary formulating updates to $G$. Since we assume that the adversary is non-adaptive, we have that the $\mathcal{SSSP}$ data structure only has do deal with updates from a non-adaptive adversary[If we would instead remove vertices from the data structure, we would do so based on the information gathered from the data structure. Thus, the data structure would be required to work against an adaptive adversary. A similar problem arises when running on $G'$.].

We point out that since we maintain $G'$ to be a decremental graph, we have that $\mathcal{V}$ forms a refinement of previous versions at any stage i.e. the SCC sets only decompose over time in $G'$. Therefore, we can never have multiple center vertices in the same SCC $X \in \mathcal{V}$. For convenience, we let for each $X \in \mathcal{V}$, the vertex $\{s\} = X \cap S$ be denoted by $\textsc{Center}(X)$. By the above argument, this function is well-defined.

§.§ Maintaining G'

Let us now describe the main procedure of our algorithm: the part that efficiently handles violations of the diameter constraint by finding new separators. The implementation of this procedure is given by <Ref>. Let us now provide some intuition and detail as to how the algorithm works.

()there exists an $X \in \mathcal{V}$, where $\mathcal{A}_{\textsc{Center}(X)}$ has a distance estimate $\widetilde{\mathbf{dist}}(\textsc{Center}(X), t)$ or $\widetilde{\mathbf{dist}}(t, \textsc{Center}(X))$ exceeding $\frac{\delta|X|}{n}$ for some vertex $t \in X$
Find separator sets that decompose $X$.
()$\widetilde{\mathbf{dist}}(t,\textsc{Center}(X)) > \frac{|X|\delta}{n}$
$(E_{Sep}, C) \gets \textsc{OutSeparator}(t, G'[X], \frac{|X|\delta}{2n}, (c+2)\log n)$

$(E_{Sep}, C) \gets \textsc{OutSeparator}(t, \overleftarrow{G'[X]}, \frac{|X|\delta}{2n}, (c+2)\log n)$

$E'_{Sep} \gets \textsc{Partition}(G'[C], \frac{|X|\delta}{4n}, (c+2)\log n))$
Update $G'$, $\mathcal{V}$ and $\tau$ to reflect the changes.
$G' \gets G' \setminus (E_{Sep} \cup E'_{Sep})$
Wait Until the generalized topological order $(\mathcal{V}, \tau)$ of $G'$ was updated, each SCC $Z$ in $G'$ has a center $\textsc{Center}(Z)$, and all data structures $\mathcal{A}_{s}$ are updated.

The algorithm runs a while-loop starting in <Ref> that checks whether there exists a SCC $X \in \mathcal{V}$, such that the $\alpha$-approximate $\delta$-restricted SSSP data structure $\mathcal{A}_{\textsc{Center}(X)}$ has one of its distance estimates $\widetilde{\mathbf{dist}}(\textsc{Center}(X), t)$ (or $\widetilde{\mathbf{dist}}(t, \textsc{Center}(X))$) exceeding $\frac{\delta|X|}{n}$ for some vertex $t$ in the same SCC $X$ in $G'$. The goal of the while-loop iteration, is then to find a separator $E_{Sep}$ between $\textsc{Center}(X)$ and $t$ and to delete the edges from $G'$.

Let us describe a loop-iteration where some distance estimate $\widetilde{\mathbf{dist}}(\textsc{Center}(X), t)$ was found that exceeded $\frac{\delta|X|}{n}$ and where $t \in X$ (the case where we have a distance estimate $\widetilde{\mathbf{dist}}(\textsc{Center}(X), t)$ exceed the threshold value is analogous and therefore omitted). In this case, we find a separator $E_{Sep}$ that separates vertices in $C$ (where $t \in C$) from vertices in $X \setminus C$ (where $\textsc{Center}(X) \in X \setminus C$) in $G'$. Further, we invoke the procedure $\textsc{Partition}(G'[C], \frac{\delta|X|}{4n}, \zeta)$ on $C$ and obtain a separator $E'_{Sep}$ in $G'$ such that each SCC in $G'[C] \setminus E'_{Sep}$ has small diameter. We point out that while the first separator procedure is necessary to separate the vertices $\textsc{Center}(X)$ and $t$ in $G'$, the partitioning procedure is run for technical reasons only since we cannot ensure an efficient implementation without this step.

Finally, we wait until the data structures that maintain the generalized topological order and the distance estimates from random sources are updated before we continue with the next iteration. On termination of the while-loop, we have that all distance estimates between centers and vertices in their SCC (with regard to $G'$) are small (with regard to $G$).

§.§ Analysis

We establish <Ref> by establishing four lemmas establishing for $(\mathcal{V}, \tau)$ correctness (<Ref>), running time (<Ref>) and success probability (<Ref>) and finally establishing that $c \log n$ independent copies of $(\mathcal{V}, \tau)$ form an $\mathcal{ATO}(G,2\alpha\delta)$-bundle with the guarantees given in <Ref>, as required.

Given that no procedure returns $\textbf{Fail}$, we have that the algorithm maintains $(\mathcal{V}, \tau)$ to be an $\mathcal{ATO}(G,2\alpha \delta)$ of expected quality $\frac{(c+2)20000 n \log^5 n}{\delta}$.

Let us first prove that the diameter of SCCs in $G'$ remains small.

After invoking <Ref>, we have that each set $X \in \mathcal{V}$ satisfies

\[
\mathbf{diam}(X, G) \leq \frac{2\alpha\delta|X|}{n}
\]

First, recall that when the while-loop in <Ref> terminates, we have that every $X \in \mathcal{V}$ has that no distance estimate $\widetilde{\mathbf{dist}}(\textsc{Center}(X), t)$ or $\widetilde{\mathbf{dist}}(t, \textsc{Center}(X))$ exceeds $\frac{\delta|X|}{n}$ for any $t \in X$.

Next, observe that the algorithm maintains the following invariant on the while-loop in <Ref>: every $X \in \mathcal{V}$ contains exactly one center is only marked in the data structure $\mathcal{E}_{\textsc{Center}(X)}$. This follows by resampling centers in SCCs $X$ that do not have a center yet and the by <Ref> which ensures that at the end of each while-loop iteration, there is time to resample.

Combined, this implies that on termination of the while-loop, for every $x, y \in X$, in any $X \in \mathcal{V}$, we have

\begin{align}
\begin{split}
\label{eq:upperBound}
\mathbf{dist}_G(x,y) &\leq \mathbf{dist}_G(x,\textsc{Center}(X)) + \mathbf{dist}_G(\textsc{Center}(X),y) \\
&\leq \widetilde{\mathbf{dist}}(x,\textsc{Center}(X)) + \widetilde{\mathbf{dist}}(\textsc{Center}(X),y) \\
& \leq \frac{2\alpha\delta|X|}{n}
\end{split}
\end{align}

where we used the triangle inequality, <Ref> and the fact that $\mathcal{A}_{\textsc{Center}}$ maintains distances with regard to a vertex-induced subgraph of $G$ (adding edges can only decrease distances, thus distances in $G$ are smaller than in $G[Y] \subseteq G$ for any $Y$).

Let us now bound the quality of the approximate topological order $(\mathcal{V}, \tau)$, i.e. upper bound for any $s$-to-$t$ path $\pi_{s,t}$ the amount $\mathcal{T}(\pi_{s,t}, \tau)$. As in the overview section, we focus on the "negative" terms in $\mathcal{T}(\pi_{s,t}, \tau)$, which are captured by

\begin{equation}
\mathcal{T}'(\pi_{s,t}, \tau) \stackrel{\text{def}}{=} \sum_{(u,v) \in \pi_{s,t}} \min\{0, \tau(X^v) - \tau(X^u)\}
\end{equation}

which is the definition of $\mathcal{T}'$ already given in equation <ref>. It is not hard to see that $\mathcal{T}(\pi_{s,t} , \tau) = 2\mathcal{T}'(\pi_{s,t} , \tau) + |\tau(X^s) - \tau(X^t)| \leq 2\mathcal{T}'(\pi_{s,t} , \tau) + n$. It, thus, only remains to establish the following lemma.

At any stage of $G$, for any path $\pi_{s,t}$ in $G$, we have

\[
\mathbb{E}[\mathcal{T}'(\pi_{s,t}, \tau)] \leq \frac{(c+2)10000 n \log^5 n}{\delta} w_G(\pi)
\]

throughout the course of the algorithm.

Before, we provide a proof, let us state the following lemma which has been shown in the last chapter.

We proof this lemma for edges $(u,v) \in E$. Then, the result follows straight-forwardly by summing over the path edges. Let us start by observing that we have $\mathcal{T}'((u,v), \tau) \neq 0$ if and only if $X^v$ strictly precedes $X^u$ in $\tau$ (where $X^z$ denotes the set in $\mathcal{V}$ that contains vertex $z \in V$). But since $(\mathcal{V}, \tau)$ forms a generalized topological order of $G'$, we have that $(u,v)$ cannot be contained in $E(G')$.

However, we only remove edges from $E(G')$ in  <Ref> of our algorithm, after being added to $E_{Sep}$ in  <Ref> or <ref>, or to $E'_{Sep}$ in  <Ref>. Having $(u,v) \in E_{Sep}$ occurs by <Ref> only if $(u,v)$ is contained in $G'[X]$ and if at least one of the endpoints is in $C$ (depending on whether the separator is computed on $G'[X]$ or $\overleftarrow{G'[X]}$ it is $u$ or $v$). In this case, the probability that $(u,v)$ is added to $E_{Sep}$ is at most $\frac{(c+2)\log n 2n}{|X|\delta} w_G(u,v)$, again by <Ref>.

However, if $(u,v)$ is not added to $E_{Sep}$ (and not already removed from $G'$) then it is completely contained in $G'[C]$. Thus, by <Ref> it is sampled into $E'_{Sep}$ with probability at most
$\frac{(c+2)240 \log^4(n) \cdot 4n}{|X|\delta}w_G(u,v) \leq \frac{(c+2)960 n \log^4 n}{|X|\delta}w_G(u,v)$.

Observe that if $(u,v)$ is sampled into either $E_{Sep}$ or $E'_{Sep}$, then since it was contained in $X$ and by the nesting property of $\tau$ which is guaranteed by <Ref>, we have that during the rest of the algorithm, we have $|\tau(X^u) - (X^v)| < |X|$ where $X^u$ (resp. $X^v$) denotes the set in $\mathcal{V}$ that contains $u$ (resp. $v$).

Thus, a while-loop iteration where $u$ or $v$ participate in $C$ adds to $\mathbb{E}[\mathcal{T}'(\pi_{s,t}, \tau)]$ at most

\[
|X| \cdot \frac{(c+2)1000 n \log^4 n}{|X|\delta}w_G(u,v) = \frac{(c+2)1000 n \log^4 n}{\delta}w_G(u,v).
\]

Since by <Ref> each vertex only occurs during $2 \lg n$ while-loop iterations in $C$, we can establish the final bound.

Combining the fact that $(\mathcal{V}, \tau)$ is a $\textsc{GeneralizedTopologicalOrder}(G')$ at all stages and $G' \subseteq G$ where $\tau$ has the nesting property, combined with <Ref> and <ref>, we derive <Ref>.

The algorithm to maintain $(\mathcal{V}, \tau)$ requires at most expected time

\[
O\left(\sum_{j=0}^{\lceil\lg \delta \rceil} \; \sum_{k=0}^{2^{j+3} \lceil \lg \delta\rceil} T_{SSSP}(m_{j,k}, n/2^{j}, \delta, 2) + m \log^2 n\right)
\]

where $\sum_j m_{j,k} \leq 16m \lceil \lg \delta\rceil$.

Again, our proof crucially relies on the following lemma.

We first observe that the initialization procedure described in <Ref> initializes $G'$ in $O(m)$ time and then runs $O(\log n)$ iterations where in each iteration it invokes the procedure $\textsc{Partition}(\cdot)$ on a set of disjoint subgraphs of $G$ to update $G'$. By <Ref>, we can implement all of these calls in time

\[
O\left(\log n \left(\sum_{j=0}^{\lceil\lg \delta \rceil} \; \sum_{k=0}^{2^{j+1}} T_{SSSP}(m_{j,k}, n/2^{j}, \delta, 2) + m \log n\right)\right).
\]

The latter term in this expression subsumes the time spend on updating $G'$ once a separator is returned.

Next, let us bound the time spend on maintaining the $\mathcal{SSSP}$ data structures as described in <Ref>. It is here that we use <Ref>: we have that initially each vertex (and edges) is in exactly one data structure. Further, every second time a vertex $v$ participates in $C$ as computed in <Ref> or <Ref>, the SCC it is contained in in $G'$ is halved in size (i.e. in the number of vertices). Since new $\mathcal{SSSP}$ data structures are initialized on the new SCCs that are contained in the $C$ set, we have that each vertex $v$, in expectation, only participates $2$ times in an $\mathcal{SSSP}$ structure with running time $T_{SSSP}(m_{j,k}, n/2^{j}, \delta, 2) + m \log n$ for any $j$. Since each edge is incident to only two vertices, we have a similar argument on edges and can therefore bound the total amount of time spend on $\mathcal{SSSP}$ data structures by

\[
O\left(\sum_{j=0}^{\lceil\lg \delta \rceil} \; \sum_{k=0}^{2^{j+1}} T_{SSSP}(m_{j,k}, n/2^{j}, \delta, 2)\right).
\]

where $\sum_j m_{j,k} \leq 4m$.

Finally, let us bound the time spend in calls to <Ref>. We observe that each while-loop iteration takes time

\[
O\left(\sum_{j=0}^{\lceil\lg \delta \rceil} \; \sum_{k=0}^{2^{j+1}} T_{SSSP}(m'_{j,k}, n'/2^{j}, \delta, 2) + m' \log n\right)
\]

where $\sum_j m'_{j,k} \leq 4m'$ for $m' = |E_G(C)|$ and $n' = |V_G(C)|$. This follows since the $\textsc{OutSeparator}(\cdot)$ procedure runs in time almost-linear in the number of edges incident to $C$ and afterwards the call of the procedure $\textsc{Partition}(\cdot)$ which dominates the costs of the procedure is only on the graph $G'$ induced by the vertices in $C$. Thus, this insight follows straight-forwardly from <Ref> and <Ref> and the insight that the cost of the remaining operations is subsumed in the bounds.

Finally, we again use <Ref> which gives that summing over all while-loop iterations is at cost at most

\[
O\left(\sum_{j=0}^{\lceil\lg \delta \rceil} \; \sum_{k=0}^{2^{j+2} \lceil \lg \delta\rceil} T_{SSSP}(m_{j,k}, n/2^{j}, \delta, 2) + m \log^2 n\right)
\]

where $\sum_j m_{j,k} \leq 8m \lceil \lg \delta\rceil$. Combining the parts of the algorithm, we thus get the total bound.

The algorithm reports $\textbf{Fail}$ with probability at most $2n^{-c-1}$.

We point out that we can only get a $\textbf{Fail}$ due to procedures $\textsc{OutSeparator}(\cdot)$ and $\textsc{Partition}(\cdot)$.

Since each separator found in the while-loop in <Ref> refines $\mathcal{V}$, we can bound the number of while-loop iterations in the course of the algorithm by $n-1$. Thus, we make at most $n-1$ calls to procedures $\textsc{OutSeparator}(\cdot)$ and $\textsc{Partition}(\cdot)$. Each of the former calls returns $\textbf{Fail}$ with probability at most $n^{-(c+2)}$ and each of the latter with probability at most $n^{-(c+2)}$.

Taking a union bound over all events, the lemma follows.

Finally, let us put everything together and prove our main theorem.

We maintain a collection of $40 c \log n$ independent $\mathcal{ATO}(G, 2\alpha\delta)$ instances

\[
(\mathcal{V}_1, \tau_1), (\mathcal{V}_2, \tau_2), \dots ,(\mathcal{V}_{40c \log n}, \tau_{40c \log n})
\]

as described earlier in this section and let $\mathcal{S}$ denote the collection of these instances.

The total running time to maintain these $\mathcal{ATO}(G, 2\alpha\delta)$'s is clearly bounded by the term given in equation <ref> by <Ref>.

Now, since by <Ref>, each $\mathcal{ATO}(G, 2\alpha\delta)$ has expected quality $q = \frac{(c+2)20000 n \log^5 n}{\delta}$, we have by Markov's inequality and a simple Chernoff bound, that for each shortest path $\pi_{s,t}$ in $G$ at some stage $t$, we have that there exists an $i$, such that $\mathcal{T}(\pi_{s,t}, \tau_i) \leq 2q$ with probability at least $1 - e^{- 40 c \log n/8} = 1 - n^{-5 c}$. Since $c > 1$, we have that the probability that any shortest-path at any stage fails, is at most $1-n^{-c}/2$ by union bounding over at most $n^2$ stages and at most $n^2$ shortest-paths, for $n$ large enough. Moreover, the total probability that any instance returns $\textbf{Fail}$ is at most $n^{-c}/2$ by <Ref> and a union bound over the instances. Thus, we have established that with probability at least $1-n^{-c}$, $\mathcal{S}$ forms an $\mathcal{ATO}(G,2\alpha \delta)$-bundle of quality $2q$ as defined in <Ref>.

§ THE SSSP ALGORITHM

We now give a proof of  <Ref> which implies our main result,  <Ref>, as a corollary. Our proof is in two steps: we first show how to implement an $\alpha$-approximate $\delta$-restricted $\mathcal{SSSP}$ as described in <Ref> given access to approximate topological orders. We then show how to bootstrap the reductions to maintains different $\mathcal{SSSP}$ data structures to cover all depths.

§.§ SSSP via an ATO

The main objective of this section is to prove the following theorem which gives a reduction from $(1+\epsilon)$-approximate $\delta$-restricted $\mathcal{SSSP}$ to approximate topological orders. In this theorem, we only assume access to an $\mathcal{ATO}(G, \eta_{diam})$ denoted by $(\mathcal{V}, \tau)$ where we assess the quality individually for each path. If the quality for a certain tuple is below a threshold $q$, we show how to exploit the approximate topological order to maintain the distance estimate for the tuple efficiently, otherwise we provide no guarantees.

Given $G=(V,E,w)$, a decremental weighted digraph, a source $r \in V$, a depth threshold $\delta > 0$, a quality parameter $q$, an approximation parameter $\epsilon > 0$, and access to $(\mathcal{V}, \tau)$ an $\mathcal{ATO}(G, \eta_{diam})$.

Then, there exists a deterministic data structure that maintains a distance estimate $\widetilde{\mathbf{dist}}(r,v)$ for every vertex $v \in V$ such that at each stage of $G$, $\mathbf{dist}_G(r,v) \leq \widetilde{\mathbf{dist}}(r,v)$ and if $\mathbf{dist}_G(r,v) \leq \delta$ and $\mathcal{T}(\pi_{r,v},\tau) \leq q \cdot \delta + n$, then

\[
\widetilde{\mathbf{dist}}(r,v) \leq \mathbf{dist}_G(r,v) + \eta_{diam} + \epsilon\delta.
\]

The total time required by this structure is

\[
O(n\delta q \log n/\epsilon + n^2 \log n)
\]

Technically, we require the approximate topological order $(\mathcal{V}, \tau)$ to encode changes efficiently and pass them the SSSP data structure. Since the SSSP data structure is updated only through delete operations, we require, that with each edge update, the data structure receives changes to $(\mathcal{V}, \tau)$ since the last stage. More precisely, we require that the user passes a set of pointers to each set $Y$ that occurred in $\mathcal{V}$ at the previous stage (denoted $\mathcal{V}^{OLD}$), but did not occur in $\mathcal{V}$ at the current stage (denoted $\mathcal{V}^{NEW}$), i.e. each $Y \in \mathcal{V}^{OLD} \setminus \mathcal{V}^{NEW}$. Additionally, we require with each such $Y$ that was split into subsets $Y_1, Y_2, \dots, Y_k \in \mathcal{V}^{NEW}$ that form a partition of $Y$, pointers to each new element $Y_i$. We further require worst-case constant query time of $\tau$, and each element $Y \in \mathcal{V}$ (for any version) can be queried for its size in constant time and returns its vertex set in time $O(|Y|)$. For the rest of the paper, this detail will be concealed in order to improve readability.

Before we show how to implement such a data structure, let us emphasize that the above theorem directly implies <Ref> that we introduced in the overview. It can further also be used to derive the following corollary which is at the heart of our proof in the next section. Its proof is rather straight-forward and we therefore refer the reader to <cit.>.

Given $G=(V,E,w)$, a decremental weighted digraph, a source $r \in V$, a depth threshold $\delta > 0$, an approximation parameter $\epsilon > 0$, and access to a collection $\mathcal{S} = \{ S_i \}_{1 \leq i \leq \mu}$ for $\mu = \lfloor\lg \delta\rfloor-1$ where each $\mathcal{S}_i$ forms an $\mathcal{ATO}(G, 2^i, 40 c\log n)$-bundle of quality $q_i$. Then, there exists an implementation for $(1+\epsilon)$-approximate $\delta$-restricted $\mathcal{SSSP}$ where $T_{SSSP}(n,m,\delta, \epsilon) = O(n
(\max_{1 \leq i \leq \mu} \{\frac{\delta q_i}{2^i}\} + n) \log^3 n / \epsilon

Let us now describe the implementation of a data structure $\mathcal{E}_r$ that stipulates the guarantees given in <Ref>.
Since the proof that this is indeed a valid implementation of <Ref> is quite similar to the proof sketch we give in <Ref>, we refer the reader to the full version of the article <cit.>.

Initialization. Throughout the algorithm, we define $\delta_{max} = \lceil (1+\epsilon)\delta + \epsilon n/q \rceil$ and define the complete graph $\mathcal{H} = (\mathcal{V}, \mathcal{V}^2, w)$[Here, we are again slightly abusing notation by referring to $\mathcal{V}$ as partition and node set, however, context and the fact that this implicitly refers to a one-to-one correspondence between partition sets and nodes ensures that no ambiguity arises.] with weight function

\[
w(X,Y) = \inf\{ w(x,y) | (x,y) \in E(X,Y)\}
\]

for $X, Y \in \mathcal{V}$. We use the convention that the infimum of the empty set is $\infty$. We use $\mathcal{H}$ to avoid dealing explicitly with $G/ \mathcal{V}$ which is a multi-graph, instead in $\mathcal{H}$ we use the same node set with simple edges as the infimum over weights of the multi-edges (even if there is no such edge).

We use a standard min-heap data structure[See for example <cit.>.] $Q_{X,Y}$ over the set $E(X,Y)$ for each ordered pair $(X,Y)$ to maintain the weight $w(X,Y)$. We henceforth denote by $Q_{X,Y}.\textsc{MinValue}$ the value $w(X,Y)$ and by $Q_{X,Y}.\textsc{MinElem}$ a corresponding edge $(x,y)$ with $x \in X, y \in Y$, and use the convention of denoting the node in $\mathcal{V}$ that contains vertex $x \in V$ by $X^x$. We initialize the data structure $\mathcal{E}_r$ by constructing $\mathcal{H}$ and by running Dijkstra's algorithm[See <cit.> for an efficient implementation.] from $X^r$ on $\mathcal{H}$. We then initialize a distance estimate $\widetilde{\mathbf{dist}}(X^r, Y)$ for each $Y \in \mathcal{V}$ to $\mathbf{dist}_{\mathcal{H}}(X^r,Y)$. If we have $\widetilde{\mathbf{dist}}(X^r,Y) > \delta_{max}$ at any point in the algorithm, we set it to $\infty$. Further, we also maintain the distance estimates $\widetilde{\mathbf{dist}}(r, u)$ for each $u \in V$ equal to $\widetilde{\mathbf{dist}}(X^r, X^u) + \eta_{diam}$, i.e. every time we increase $\widetilde{\mathbf{dist}}(X^r, X^u)$, we also increase $u$'s distance estimate[We will show that $\widetilde{\mathbf{dist}}(X^r, X^u)$ is a monotonically increasing value over time.]. This allows us to henceforth focus on the distance estimates of nodes which is easier to describe. We also store the corresponding shortest-path tree $T$ truncated at distance $\delta_{max}$ that serves as a certificate of the distance estimates.

Finally, we partition for each node $X \in \mathcal{V}$, the in-neighbors set in $\mathcal{H}$ of $X$ into different buckets based on their $\tau$-distance: for each $X$, we initialize bucket $B_{-1}(X) = \{X\}$ and for $0 \leq j \leq \lg n$ we initialize the bucket $B_j(X)$ to

\[
\{ 2^{j} \leq \chi(X,Y, \tau) < 2^{j+1} | Y \in N_{\mathcal{H}}^{in}(X), X \neq Y\}
\]

where we define

\begin{equation} \label{eq:chi}
\chi(X ,Y, \tau) \stackrel{\text{def}}{=}          \begin{cases}
\tau(Y) - (\tau(X) + |X| - 1) & \text{if } \tau(X) < \tau(Y) \\
\chi(Y, X, \tau) & \text{otherwise}
\end{cases}
\end{equation}

that is $\chi(\cdot)$ is similar to $\mathcal{T}(\cdot)$ (in fact $ \chi(X ,Y, \tau) \leq \mathcal{T}(X, Y, \tau)$), however, as $\tau$ maps nodes $X$ and $Y$ to disjoint intervals, $\mathcal{T}(\cdot)$ measures the distance between the starting points of the intervals, while $\chi(\cdot)$ measures the distance between the intervals (i.e. the closest endpoints of the intervals).

At any stage, we let $B_{\leq j}(X) = \bigcup_{j' \leq j} B_{j'}(X)$. We store each set $B_j(X)$ explicitly as a linked list, store for each $Y \in B_j(X)$ a pointer to the bucket, and maintain the buckets to partition the in-neighbors of each $X$.

Handling Edge Deletions. The edge deletion procedure takes two parameters: the edge to be deleted $(u,v)$ and a collection of tuples $U$ that encode refinements of $\mathcal{V}$ during this stage. To handle the update, we initialize a min-heap $Q = \emptyset$ that keeps track of the nodes in $\mathcal{H}$, that cannot be reached from $X^r$ in the truncated shortest-path tree $T$ (i.e. whose certificate for the current distance estimate was compromised).

We start our update procedure by processing updates to $(\mathcal{V}, \tau)$ (check the remark of <Ref> for a description of these updates encoded by $U$). For any node $X \in \mathcal{V}^{OLD} \setminus \mathcal{V}^{NEW}$, that was split into subsets $X_1, X_2, \dots, X_k \in V^{NEW}$ (i.e. for every tuple $(X, X_1, X_2, \dots, X_k) \in U$), we query for each $X_i$, its size. Then, we let the largest node $X_i$ inherit the original node $X$ (that is the nodes are equal in our data structure at this stage although the partition sets are not), and create a new node $X_{i'}$ in $\mathcal{H}$ for other $i' \neq i$, and new heap structures $Q_{X_{i'}, Y}$ for every $Y \in \mathcal{V}$. Then for each $X_{i'}$, $i' \neq i$, we scan each edge $(x,y)$ in $E(X_{i'}, V \setminus X_{i'})$, remove it from the heap $Q_{X_i, X^y}$ and add it to the new heap $Q_{X_{i'}, X^y}$. We also initialize the distance estimates for each $X_{i'}$, $\widetilde{\mathbf{dist}}(X^r, X_{i'})$ to take the value $\widetilde{\mathbf{dist}}(X^r, X)$, also for $X_i$. We then find the edge $(w,x)$ in $T$ where $X = X^x$. Clearly, we now have that $X_{i'} = X^x$ for some ${i'}$ and we connect $X_{i'}$ in the tree $T$ since this edge is now a certificate for $X_{i'}$'s distance estimate. The rest of the nodes, i.e. the nodes $X_1, X_2, \dots, X_{{i'}-1}, X_{{i'}+1}, \dots, X_k$, we add to $Q$ since we do not have a certificate for them yet.

Finally, when all the node splits for the current stage where processed, we update the buckets $B_j(Y)$ for all $j$ and $Y$ to almost stipulate the initialization rules. We point out that all edges that have to be assigned to a different bucket have to be incident to $X_1, X_2, \dots, X_k$ by property <ref>. Then, for each $X_{i'}$ (also $X_i$), we compute $j$ to be the largest integer such that some number in $|X_{i'}|, |X_{i'}|+1, \dots, |X| - 1$ is divisible by $2^j$. Then, we update all nodes in $B_{\leq j+1}(X_{i'})$ by scanning and reassigning them, and similarly reassign $X_{i'}$ to a new bucket for each $Y$ where $X_{i'} \in B_{\leq j}(Y)$.

Finally, when all node splits are processed, the node set of $\mathcal{H}$ reflects the current $\mathcal{V}$, and we can delete the edge $(u,v)$ from $\mathcal{H}$ by deleting it from the heap it is contained in. If $(u,v)$ was equal to $Q_{X^u, X^v}.\textsc{MinElem}$, and $(X^u, X^v) \in T$, we delete it from $T$ and insert $X^v$ into $Q$.

We then rebuild our certificate $T$: we take the node $Y$ from $Q$ with the smallest distance estimate $\widetilde{\mathbf{dist}}(X^r, Y)$ until $Q$ is empty or the smallest distance estimate $\infty$. Now, let $j$ be the largest integer such that $ \widetilde{\mathbf{dist}}(X^r, Y)$ is divisible by $\lceil 2^{j} \cdot \frac{\epsilon}{q} \rceil$. We then check if there exists a node $X \in B_{\leq j}(Y)$ such that

\[
\widetilde{\mathbf{dist}}(X^r, X) + Q_{X,Y}.\textsc{MinValue} \leq \widetilde{\mathbf{dist}}(X^r, Y).
\]

In this case, the edge $(x,y) = Q_{X,Y}.\textsc{MinElem}$ serves as a certificate that the distance from $X^r$ to $Y$ is at most $\widetilde{\mathbf{dist}}(X^r, Y)$ and therefore we add $(x,y)$ to $T$. If there exists no such vertex $X$, then we increase the value $\widetilde{\mathbf{dist}}(X^r, Y)$ by one or to $\infty$ if it is currently at least $\delta_{max}$ and reinsert $Y$ and children $Z_1, Z_2, \dots, Z_k$ of $Y$ in $T$ into $Q$ (after deleting the edges $(Y, Z_i)$ from $T$). This completes the description of the algorithm. Again, we refer the reader interested in the proof of <Ref> to <cit.>.

§.§ Bootstrapping an Algorithm for Unrestricted Depth

Next, let us prove the following theorem which show is a detailed version of <Ref>. Combined with <Ref> (where we set the depth threshold parameter $\delta$ to $Wn$), this immediately implies our main result, <Ref>.

For any $0 \leq i \leq \lg(Wn)$, given a decremental digraph $G=(V,E,w)$, we can maintain a hierarchy $\mathcal{S} =\{\mathcal{S}_i\}_i$ where each $\mathcal{S}_i$ is a $\mathcal{ATO}(G, 2^i, 40 c \log n)$-bundle of expected quality $\tilde{O}(n/2^i)$. The algorithm runs in total expected update time $O(c^5 n^2 \log^{17} n \lg^{5}(Wn))$ against a non-adaptive adversary and is correct with probability at least $1-n
^{-c+2}$ for any failure probability parameter $c \geq 2$.

In order to prove our theorem formally, we need to fix the constants hidden by the big-$O$ notation in some of our statements. We therefore henceforth denote the constant hidden by <Ref> to maintain the SSSP data structure by $c_{SSSP}$, the constant hidden in <Ref> to obtain an $\mathcal{ATO}$-bundle from an SSSP data structure by $c_{SSSP \to ATO}$ and finally, we denote the constant hidden in the theorem that we want to prove by $c_{Total}$ where we require that $c_{Total} \geq (c_{SSSP \to ATO} \cdot c_{SSSP})^2 \cdot 2^{49}$.

Without further due, let us prove the theorem by induction on $n$, the number of vertices in graph $G$. The base case with $n \leq 1$ is easily established since there are no paths in a graph of only one vertex thus we obtain arbitrarily good quality and the running time is a small constant (at least smaller than $c_{Total}$).

Let us now give the inductive step $n \mapsto n+1$: for each $i$, we iteratively construct an $\mathcal{ATO}(G, 2^i, 40 c \log n)$-bundle $\mathcal{S}_i$ as described in <Ref>. Thus, we have to show how to implement a $2$-approximate $2^{i-2}$-restricted $\mathcal{SSSP}$ data structure required in the reduction (note that for $i \leq 2$ this task is trivial, so we omit handling it as special levels).

Note that each data structure $\mathcal{SSSP}$ that we are asked to implement for an $\mathcal{ATO}$-bundle $\mathcal{S}_i$ at level $i$ is run on a different graph $H \subseteq G$. To obtain an efficent algorithm, we will implement the data structure differently depending on the size of such $H$. If $H$ has at least $n/2^\gamma$ vertices for some $\gamma = \Theta( \lg \log Wn)$ that we fix later, we call $H$ a large graph. Otherwise, we say $H$ is small. Now, we implement $\mathcal{SSSP}$ as follows:

* if $H$ is small, then we use the induction hypothesis, find a $\mathcal{ATO}$-bundle $\mathcal{S}'$ for $H$ and and invoke <Ref> on $\mathcal{S}'$. We note that we need to set the parameter that controls the failure probability for $\mathcal{S}'$ to $c \cdot 4 \log n$ to ensure that it succeeds with high probability (this is since $\mathcal{S}'$ only succeeds with probability polynomial in $|V(H)|$ which might be very small).

* if $H$ is large, we exploit <Ref> which states that when the reduction asks to maintain approximate distances on some graph $H \subseteq G$, it is sufficient to maintain distance estimates on any graph $F$ such that $H \subseteq F \subseteq G$ and in particular, it is ok to simply run on the entire graph $G$. Therefore, we simply use $\mathcal{S}_{i-1}$ in combination with <Ref> and maintain distances in $G$.

Let us now analyze the total running time. We start by calculating the running time required by each level $i$ separately. For some fixed $i$, we have that by <Ref> we have running time

\begin{equation} \label{eq:totalCostBoundATO}
c_{SSSP \to ATO} \left(\sum_{j=0}^{\lceil\lg 2^{i-2} \rceil} \; \sum_{k=0}^{2^{j+3} c \log^2 n} T_{SSSP}(m_{j,k}, n/2^{j}, 2^{i-2}, 2) + n^2 \log^3 n\right)
\end{equation}

where $\sum_j m_{j,k} \leq 16c \cdot m \log^2 n$ for all $k$, to maintain $\mathcal{S}_i$.

Let us analyze the terms $T_{SSSP}(m_{j,k}, n/2^{j}, 2^{i-2}, 2)$ based on whether $j < \gamma$ or not (i.e. depending on how the SSSP data structure was implemented):

* if $j < \gamma$: then, by the induction hypothesis, we require time at most

\begin{align*}
\begin{split}
& c_{Total} (c 4 \log n)^5 \cdot \left(\frac{n}{2^j}\right)^2 \log^{17}(n) \lg^{5}(Wn) 2^{-2j} \\
& < c_{Total} \cdot 2^8 \cdot c^5 n^2 \log^{22}(n) \lg^{5}(Wn)  2^{-j}2^{-\gamma}
\end{split}
\end{align*}

to maintain the new $\mathcal{ATO}$-bundle $\mathcal{S}'$ on the graph $H$ and again by the induction hypothesis we have that the bundle has quality $\frac{(4\log n c +2)40000n \log^5 n 2^{-j}}{2^{i-3}} \log^3 n$.

Thus, maintaining SSSP on $H$ using $\mathcal{S}'$ as described in <Ref> can be done in time

\[
c_{SSSP}((c \cdot 4\log n+2)40000 \cdot 2^3)(n^2 \log^8 n 2^{-2j}) < c_{SSSP} \cdot c \cdot 2^{22} (n^2 \log^9 n 2^{-j} 2^{-\gamma}).
\]

Combined, we obtain that we can implement the entire SSSP data structure with total running time at most

\begin{align*}
\begin{split}
&c_{Total} \cdot 2^8 \cdot c^5 n^2 \log^{22}(n) \lg^{5}(Wn) 2^{-j}2^{-\gamma} + c_{SSSP} \cdot c \cdot 2^{22} (n^2 \log^9 n 2^{-j}2^{-\gamma})\\
&\leq c_{Total} \cdot c_{SSSP} \cdot c^5 \cdot 2^{-j}2^{-\gamma} \cdot 2^{22} \cdot n^2 \log^{22}(n) \lg^{5}(Wn).
\end{split}
\end{align*}

Combining these bounds and summing over all small graph terms in equation <ref>, we obtain that the total contribution is at most

\begin{align*}
\begin{split}
& c_{SSSP \to ATO} \cdot \lg(nW) \cdot (2^3 c\log^2 n) \left(c_{Total} \cdot c_{SSSP} \cdot c^5 \cdot 2^{-\gamma} \cdot 2^{22} \cdot n^2 \log^{22}(n) \lg^{5}(Wn)\right) \\
&\leq c^6 \cdot c_{SSSP \to ATO} \cdot c_{Total} \cdot c_{SSSP} \left(2^{22} \cdot n^2 \log^{24}(n) \lg^{6}(Wn) 2^{-\gamma}\right).
\end{split}
\end{align*}

This completes the analysis of the small graph data structures.

* otherwise ($j \geq \gamma$): then, we run the SSSP structure from <Ref> on $\mathcal{S}_{i-1}$ which gives running time at most

\[
c_{SSSP}\left(n 2^i \cdot \frac{(c+2)40000n \log^5 n}{2^{i-3}} \log^3 n\right) \leq c_{SSSP} \cdot c ( 2^{20} \cdot n^2 \log^8 n)
\]

where we used $c \geq 2$. Since there are at most $c_{SSSP \to ATO} \cdot c \cdot (2^3 \lg(nW)\log^2 n 2^{\gamma})$ terms for large graphs, where $j \geq \gamma$, we have that the total cost of all $\mathcal{SSSP}$ data structures on large graphs is at most

\begin{align*}
\begin{split}
&c_{SSSP \to ATO} \cdot c \cdot (2^3 \lg(nW)\log^2 (n) 2^{\gamma}) \cdot \left(c_{SSSP} \cdot c ( 2^{20} \cdot n^2 \log^8 n) \right)\\
&= c_{SSSP \to ATO} \cdot c^2 \cdot c_{SSSP} \cdot \left(2^{23} \cdot n^2 \log^{10} (n)  \lg(nW) 2^{\gamma}\right)
\end{split}
\end{align*}

It now only remains to choose $\gamma$ and combine the two bounds. We set $\gamma = 24 \lceil\lg (c^2 \cdot c_{SSSP \to ATO} \cdot c_{SSSP} \cdot \lg^{3}(Wn) \log^{7}(n)) \rceil$, and obtain that the total running time summed over large and small graphs is at most

\begin{align*}
\begin{split}
& c_{SSSP \to ATO}^2 \cdot c_{SSSP}^2 \cdot c^4 \cdot 2^{48}(n^2 \log^{17} n \lg^{4}(Wn))) \\ &+ \frac{c^4 c_{Total} (n^2 \log^{17} n \lg^{3}(Wn))}{2}
\\ &\leq  c^4 c_{Total} (n^2 \log^{17} n \lg^{4}(Wn))
\end{split}
\end{align*}

where we used our initial assumption on the size of $c_{Total}$.

Finally, we point out that there are at most $\lg(nW)$ levels $i$ and therefore, the total update time is at most

\[
c_{Total} (c^4 n^2 \log^{17} n \lg^{5}(Wn))
\]

as required.

Further, we point out that every $\mathcal{ATO}$-bundle $\mathcal{S}_i$ that was constructed runs correctly with high probability at least $1-n^{-c}$, while every $\mathcal{ATO}$-bundle $\mathcal{S}'$ is maintained correctly with probability at least $1-n^{-4c}$ (recall that we set the failure parameter of these data structures to $c \cdot 4 \log n$). Noting that we only have $\lg(nW)$ instances of the former bundles, and at most $n^3$ of the latter, taking a simple union bound over the events that any bundle instance fails gives a total failure probability of at most $n^{-c+2}$.

CHAPTER: DETERMINISTIC ALGORITHMS FOR DECREMENTAL SSR, SCC AND SSSP

In this chapter, we are concerned with obtaining the first deterministic data structures that improve upon the classic ES-trees in decremental graphs.

While we will touch on the expander techniques developed in the article that this section is based on, we emphasize the above theorems as the main results in the context of this thesis and refer readers that are mostly interested in the expander tools to <cit.>.

§ OVERVIEW

We now give an overview of the data structures. We first focus on the problem of obtaining a data structure for the decremental SCC problem and only in the latter part of this overview show how to obtain a decremental SSSP data structure.

Directed Expanders. We start with the definition of directed expanders.

A directed graph $G$ is a $\phi$-vertex expander
if it has no $\phi$-vertex-sparse vertex-cut. Similarly, $G$ is
$\phi$-(edge) expander if it has no $\phi$-sparse cut.[Note that an isolated vertex is an expander (in both edge and vertex

Intuitively, expanders are graphs that are “robustly connected”
and, in particular, they are strongly connected. It is well-known
that many problems become much easier on expanders. So, given a problem
on general graph, we would like to reduce the problem to expanders.

It is further well-known that every undirected graph admits the following
expander decomposition: for any $\phi>0$, a $\tilde{O}(\phi$)-fraction
of vertices/edges can be removed so that the remaining is a set of
vertex-disjoint $\phi$-vertex/edge expander. Unfortunately, this
is impossible in directed graphs. Consider, for example, a DAG. However,
a DAG is the only obstacle; for any $\phi>0$, we can remove a $\Otil(\phi)$-fraction
of vertices/edges, so that the remaining part can be partitioned into a DAG and a set of vertex-disjoint $\phi$-vertex/edge
expanders. This observation can be made precise as follows.

[Directed $\phi$-Expander Decomposition]Let $G=(V,E)$
be any directed $n$-vertex graph and $\phi>0$ be a parameter. There
is a partition $\{R,X_{1},\dots,X_{k}\}$ of $V$ such that

* $|R|\le O(\phi n\log n)$;

* $G[X_{i}]$ is a $\phi$-vertex expander for each $i$;

* Let $D$ be obtained from $G$ by deleting $R$ and contracting each
$X_{i}$. Then, $D$ is a DAG.

The edge version of <Ref> can be stated as follows:
for any unweighted $m$-edge graph $G=(V,E)$, there is a partition
$\{X_{1},\dots,X_{k}\}$ of $V$ and $R\subset E$ where $|R|\le O(\phi m\log m)$,
each $G[X_{i}]$ is a $\phi$-expander, and $D$ is a DAG (where $D$
is defined as above). It can be generalized to weighted graphs as

High-level Framework. This decomposition motivates the framework of our algorithm, although for the sake of efficiency we only maintain an approximate version. The decomposition suggests that we need four main ingredients:

* a dynamic expander decomposition in directed graphs,

* a fast algorithm on vertex-expanders,

* a fast algorithm on DAGs, and

* a way to deal with the small remaining part $R$.

We point out however that component 3. will only be required by the SSSP data structure.

The High-Level Algorithm for decremental SCC. In order to develop some intuition for the above framework, let us derive our data structure for decremental SCC.

First, let us state the following Theorem which is an idealized version of our main technical result. We will pretend for the first part of the overview that we can indeed prove this Theorem but we stress that we obtain a considerably weaker guarantees in our algorithm.

[Idealized Expander Decomposition]thmExpanderDecompTheorem

There is a deterministic algorithm $\mathcal{A}$ that given an unweighted, directed, decremental graph $G$ and a parameter $\phi \in (0,1)$, maintains a directed $\phi$-expander decomposition, such that $R$ is an incremental set of final size $\Ohat(\phi^{-1})$. The algorithm to maintain the expander decomposition runs in time $\Ohat(m\phi^{-2})$.

Observe that every set $X$ in $G$, that forms a $\phi$-expander (for any $\phi$) is part of an SCC in $G$. Thus, given the above Theorem, the graph $G$ where expanders $X_1, X_2, \dots, X_k$ are contracted, forms a condensation of $G \setminus R$.

To this end, we note that in <cit.> (which we explained in some detail in <Ref>), a data structure by Lacki was used to deal with separator vertices set $S$ to restore SCCs in $G$ given the set $R$ and the condensation of $G \setminus S$. We state his result below (here the result is stated as a reduction which is straight-forward to obtain and is proven in <cit.>).

[see <cit.>]theoremLackiProp

Let $G=(V,E)$ be a decremental graph. Let $\mathcal{A}$ be a data structure that 1) maintains a monotonically growing set $S \subseteq V$ and after every adversarial update reports any additions made to $S$ and 2) maintains the SCCs in $G \setminus S$ explicitly in total update time $T(m,n)$ and supports SCC path queries in $G \setminus S$ in almost-path-length query time.

Then, there exists a data structure $\mathcal{B}$ that maintains the SCCs of $G$ explicitly and supports SCC path-queries in $G$ (in almost-path-length query time). The total update time is $O(T(m,n) + m|S|\log n)$, where $|S|$ refers to the final size of the set $S$.

Using these two Theorems in conjunction, it is not hard to see that setting $\phi=n^{-1/3}$, we can obtain a data structure that maintains SCCs in a decremental graph in total update time $\Ohat(mn^{2/3})$.

Certifying Directed Expanders. In order to maintain an expander decomposition as described in <Ref> (which we cannot do! We obtain a considerable weaker guarantee), a basic procedure that is required to even compute an expander decomposition is an algorithm to efficiently certify that $G$ is a $\phi$-expander or outputs a $\phi$-vertex-sparse vertex-cut.

We introduce the notion of embeddings which has been used heavily in the static setting to certify expanders <cit.>:

Let $G=(V,E)$ be a directed graph.
An embedding $\pset$ in $G$ is a collection of simple directed
paths in $G$ where each path $P\in\pset$ has associated value
$\val(P)>0$. We say that $\pset$ has length $\len$ if every
path $P\in\pset$ contains at most $\len$ edges. We say that $\pset$
has vertex-congestion $\congest$ if, for every vertex $v\in V$,
$\sum_{P\in\pset_{v}}\val(P)\le\congest$ where $\pset_{v}$ is the
set of paths in $\pset$ containing $v$. We say that $\pset$ has
edge-congestion $\congest$ if, for every edge $e\in E$, $\sum_{P\in\pset_{e}}\val(P)\le\congest$
where $\pset_{e}$ is the set of paths in $\pset$ containing $e$.

Given an embedding $\pset$, there is a corresponding weighted directed
graph $W$ where, for each path $P\in\pset$ from $u$ to $v$, there
is a directed edge $(u,v)$ with weight $\val(P)$. We call $W$ an
embedded graph corresponding to $\pset$ and say that $\pset$
embeds $W$ into $G$.

The following fact shows that, to certify that $G$ is a vertex expander,
it is enough to embed an (edge)-expander $W$ into $G$ with small

Let $G=(V,E)$ be a graph. Let
$W=(V,E',w)$ be a $\phi$-expander with minimum weighted degree $1$.
If $W$ can be embedded into $G$ with vertex congestion $\congest$,
then $G$ is a $(\phi/\congest)$-vertex expander.

Consider a vertex cut $(L,S,R)$ in $G$ where $|L| \le |R|$.
Suppose that $E(L,R) = \emptyset$, otherwise $E(R,L) = \emptyset$ and the proof is symmetric.
Observe that each edge $e\in E_{W}(L,V\setminus L)$ in $W$ corresponds to a path in $G$ that goes
out of $L$ and, hence, must contain some vertex from $S$.
So the total weight of these edges in $W$ can be at most $\delta_{W}^{out}(L)\le|S|\cdot\congest$.
At the same time, $\delta_{W}^{out}(L)\ge\phi\vol_{W}(L)\ge\phi|L|$
as $W$ is a $\phi$-expander with minimum weighted degree 1. So $|S|\ge\frac{\phi}{\congest}|L|$
as desired.

In our actual algorithm, instead of certifying that $G$ is a vertex
expander (i.e. $G$ has no sparse vertex-cut), we relax to the task
to only certifying that $G$ has no balanced sparse vertex-cut. This, in turn,
motivates the definition of $\phi$-witness:
We say that $W$ is a $\phi$-witness
of $G$ if $V(W)\subseteq V(G)$, $W$ is a $\Omegahat(1)$-(edge)-expander
where $9/10$-fraction of vertices have weighted degree at least $1/2$,
and there is an embedding of $W$ into $G$ with vertex-congestion
$1/\phi$. (Note that $E(W)$ does not have to be a subset of $E(G)$.)
We say that $W$ is a $\phi$-short-witness if it is a $\phi$-witness
and the embedding has length $\Ohat(1/\phi)$. We say that $W$ is
a large witness if $|V(W)|\ge9|V(G)|/10$.[The constant $9/10$ is somewhat arbitrary.]

We sometimes informally refer to a graph that contains a large witness
as an almost vertex-expander. This is because of the below
fact whose proof is similar to <Ref>.

Let $G=(V,E)$ be a graph that contains a large $\phi$-witness $W$.
Then $G$ has no $1/3$-vertex-balanced $(\phi/n^{o(1)})$-vertex-sparse
vertex cut.

We can now finally state the result we obtain for certifying an expander.

There is a deterministic algorithm $\certifywitness(G,\phi,\eps)$ that takes as input a directed $n$-vertex graph $G=(V,E)$, $\phi\in(0,1/\log^2(n)]$, and $\eps \in (0,1)$ in $\Ohat(m/\phi)$ time, either

* finds a $\Otil(\phi)$-vertex-sparse $\Omega(\epsilon/n^{o(1)})$-vertex-balanced
cut $S$, or

* certifies that there exists a $\phi$-witness $W$ of $G$ such that $|V(W)|\ge(1-\epsilon)n$ and every edge in $W$ has weight at least $1$. Let $\alphaex = 1/n^{o(1)}$ be the precise expansion factor of $W$ guaranteed by this lemma (we will use this parameter in other lemmas).

(Almost) Expander Decomposition using Certification. Note that finding large $\phi$-vertex-sparse vertex-cuts in expander certification allows us not only to add these cuts to the set $R$ and then recurse on the remaining strongly-connected subgraph but also to do so efficiently (since both sides of the cut are roughly of equal size so each vertex only participates a polylogarithmic number of times in such a recursion). It is straight-forward to show that adding sparse cuts and recursing leads to the bound on $R$ as described in <Ref> and certainly has $R$ as an incremental set.

However, certifying $\phi$-expanders is a static procedure. Therefore a second procedure is required: essentially, once a $\phi$-expander $X$ with induced graph $G' = G[X]$ is certified, we have that for $\Omegatil(|X| \phi)$ updates, a subset $X'$ of $X$ still forms a $\phi$-expander and that $X'$ is of size $|X|/2$ during this period. In fact, we can maintain efficiently a set $\overline{P}$ that comes fairly close to $X'$:

[Directed Expander Pruning]thmexpanderPruning
There is a deterministic algorithm that given a directed unweighted decremental multi-graph $G'$ with $n$ vertices and $m$ edges that is initially a $\phi$-expander and a parameter $L \ge 1$. The algorithm maintains an incremental set $P\subseteq V$ using $\tilde{O}\left(\frac{m n^{1/L}}{\gamma_{_L}(\phi)}\right)$ total update time such that for $\overline{P} = V(G') \setminus P$, we have that $G'[\overline{P}]$ is a $\gamma_{_L}(\phi)$-expander and $\vol_{G'}(P)\le O\left(\frac{t n^{1/L}}{\gamma_{_L}(\phi)}\right)$ after $t$ updates, where $\gamma_{_L}(\phi) = \phi^{3^{O(L)}}$.

Now, observe that the $\phi$ dependency of the above algorithm is fairly bad. However for very large $\phi$ (say $\sim 1/n^{\sqrt{\log n}} = 1/n^{o(1)}$), and using $L = \Theta(\log \log n)$, the above guarantees are only off from the optimal case by a subpolynomial factor.

Luckily, given a graph $G'$ that is a $\phi$-expander, we can use the witness graph $W$ that we used to certify that $G'$ is a $\phi$-expander in-place of $G'$ at the expense that whenever we remove an edge from $W$, we have to remove up to $\Ohat(\phi^{-1})$ vertices from the expander. Using that $W$ is a $\phi'$-expander for $\phi'$ very large, it follows that we can maintain a set that comes close to $X'$ for $\Omegahat(|X| \phi)$ updates even for $G'$ in total time $\Ohat(m \phi^{-1})$ (we note that while the running time for <Ref> is only $\Ohat(m)$, with every update it might cause us to remove $\Ohat(\phi^{-1})$ vertices from $X'$ explicitly).

Expander Set Maintenance. Let us now address the problem of the last paragraph: we might have some vertices in $X \setminus X'$, i.e. vertices that were removed in <Ref> from our graph $G'$ that was a $\phi$-expander at the first stage and was slightly decomposed during the last updates. We next have to determine what to do with vertices in $X \setminus X'$. We resort again to an idea from Chechik et al. <cit.>: We maintain an ES-tree in the graph $G' / X'$ from $X'$ to depth $\delta = \phi^{-1}$ in the graph $G$ where $X'$ is a single node obtained from contraction. Technically, $X'$ is a decremental set and thus not remain the same over time, we can use the augmented ES-tree from <Ref> to deal with this technicality.

Then, we implement the following procedure: whenever a vertex $v \in X \setminus X'$ is a distance larger than $\phi^{-1}$, we find a balanced separator from $v$ (see for example <Ref>), add separator vertices to $R$ as well, and recurse on the SCCs that do not contain $X'$ by trying to certify that they are expanders again. By basic balanced separator arguments we can bound the number of vertices we add to $R$ in this way again by $\Otil(\phi^{-1})$. Instead of refering to the set $X'$ however, we will henceforth simply refer to the (pruned) witness $W$. We summarize this in the somehow technical Theorem below which also bounds the running (which we need in all of its explicity to derive our SSSP data structure).

There is a data structure $\pathtowitness(G,W,\phi)$ that takes as input an $n$-vertex $m$-edge graph $G = (V,E)$, a set $W \subseteq V$ with $|W| \geq |V|/2$ and a parameter $\phi > 0$. The algorithm must process two kinds of updates. The first deletes any edge $e$ from $E$; the second removes a vertex from $W$ (but the vertex remains in $V$), while always obeying the promise that $|W| \geq |V|/2$. The data structure must maintain a forest of trees $\fout$ such that every tree $T \in \fout$ has the following properties: all edges of $T$ are in $E(G)$; $T$ is rooted at a vertex of $W$; every edge in $T$ is directed away from the root; and $T$ has depth $\Ohat(1/\phi)$. The data structure also maintains a forest $\fin$ with the same properties, except each edge in $T$ is directed towards the root.

At any time, the data structure may perform the following operation:  it finds a $\Ohat(\phi)$-sparse vertex cut $(L,S,R)$ with $W \cap (L \cup S) = \emptyset$ and replace $G$ with $G[R]$. (This operation is NOT an adversarial update, but is rather the responsibility of the data structure.) The data structure maintains the invariant that every $v \in V$ is present in exactly one tree from $\fout$ and exactly one from $\fin$; given any $v$, the data structure can report the roots of these trees in $O(\log(n))$ time. (Note that as $V$ may shrink over time, this property only needs to hold for vertex $v$ in the current set $V$.) The total time spent processing updates and performing sparse-cut operations is $\Ohat(m/\phi)$.

Although the data structure works for any set $W$, $W$ will always correspond to a $\phi$-witness in the higher-level algorithm. The adversarial update that removes a vertex from $W$ corresponds to the event that the witness shrinks in the higher-level algorithm.
The forests $\fin$ and $\fout$ allow the algorithm to return paths of length $\Ohat(1/\phi)$ from any $v \in V(G)$ to/from $W$: find the tree that contains $v$ and follow the path to the root, which is always in $W$. The requirement that each tree has low-depth will be necessary to reduce the update time. But once we add this requirement, we encounter the issue that some vertices may be very far from $W$, so we need to give the data structure a way to remove them from $V(G)$. This is the role of the sparse-cut operation: we will show in the proof that if $v$ is far from $W$, it is always possible to find a sparse vertex cut $(L,S,R)$ such that $v$ is in $L$ and hence removed from $G$. (The higher-level algorithm will process this operation by adding $S$ to $\Shat$, so that $L$ becomes part of a different SCC in $\gstar[\vstar \setminus \Shat]$.)

To summarize this paragraph, while we do not get the guarantees of an idealized expander decomposition, we can ensure that the expander sets computed at some stage are maintained such that their diameter is bound by $\Ohat(\phi^{-1})$ quite efficiently. This turns out to be enough for our applications.

Maintaining Shortest Paths in Expander Sets. We also point out that since we would like to return the shortest paths in our SSSP data structure, <Ref> is not sufficient since it only allows us to find shortest paths that do not cross the witness graph $G$. However, we also require a second data structure that explicitly maintains approximate shortest paths between all pairs of vertices in an expander (here the approximation factor will be subpolynomial, that is quite huge). The input $W$ will always correspond to a large $\phi$-witness, and will thus have expansion $1/n^{o(1)}$. This data structure is not new to our paper, as it is essentially identical to an analogous structure for undirected graphs in <cit.>. The only major difference is that we need to plug in our new expander pruning algorithm for directed graphs (Theorem <ref>). Note that the theorem below will only allow us to find paths in $E(W)$, not $E(G')$, the graph of interest. However it is possible to use the embedding of $W$ to recover the correspond short paths in $E(G)$.

There is a deterministic data structure $\shortoracle(W)$ that takes as input an $n$-vertex $m$-edge $1/n^{o(1)}$-expander $W$ subject to decremental updates. Each update can delete an arbitrary batch of vertices and edges from $W$, but must obey the promise that the resulting graph remains a $\phi$-expander. Given any query $u,v \in V(W)$, the algorithm returns in $n^{o(1)}$ time a directed simple path $P_{uv}$ from $u$ to $v$ and a directed simple path $P_{vu}$
of $v$ to $u$, both of length at most $n^{o(1)}$. The total update time of the data structure is $\Ohat(m)$.

This completes our overview of components on witness graphs that certify that some graph $G'$ is a $\phi$-expander. It remains to address a central problem.

Sparse Witnesses in Dense Graphs. In the previous paragraphs, we have reduced the problem of certifying an almost vertex-expander to maintaining a large witness (and then maintaining the witness using pruning) and sketched the ideas to maintain low-diameter components and a small set $R$ of removed vertices. However, although finding a low congestion embeddings in vertex expanders can be done very efficiently in the static setting (using the well known cut-matching game), there is
one crucial obstacle in the dynamic setting:

Consider the following simple scenario. We start with a complete graph
$G$ and parameter $\phi=\Omegahat(1)$. A standard (static) construction
of a large $\phi$-witness runs in $\Ohat(m)$ time and gives an unweighted $\Omegahat(1)$-expander $W$ where all vertex degrees are $\Theta(\log n)$.
Let $\pset$ be the embedding of $W$. Observe that each path from $\pset$ has
value $1$ and $|\pset|=O(n\log n)$.

Unfortunately, once the adversary knows $\pset$, he can destroy each embedding path $P\in\pset$ by deleting any edge in $P$. In total,
he can delete only $O(n\log n)$ edges in $G$ to destroy the whole
embedding of $W$. The algorithm would then have to construct a new
witness, which the adversary could again destroy with $O(n\log n)$
deletions. This process continues until $G$ has a balanced, sparse
vertex-cut, which might not happen until $\Omega(n^{2})$ deletions.
That is, this standard approach requires the algorithm to re-embed
a new witness $\tilde{\Omega}(n)$ times, which is not only slow,
but requires too many changes to the witness.

Congestion Balancing. To overcome this obstacle, we introduce a technique that we call congestion balancing to maintain a witness $W$ that only needs to be re-embedded $\Ohat(1/\phi)$ times.

[Robust Witness Maintenance]thmRobustWitnessTheorem
There is a
deterministic algorithm $\rwitness(G,\phi)$ that takes as input  a directed decremental $n$-vertex
graph $G$ and a parameter $\phi \in (0,1/\log^2(n)]$. The algorithm maintains a large (weighted) $\phi$-short-witness $W$ of $G$ using $\Ohat(m/\phi^{2})$
total update time such that every edge weight in $W$ is a positive multiple of $1/d$, for some number $d \leq 2\davg$, where $\davg$ is the initial average degree of $G$. The total edge weight in $W$ is $O(n\log n)$. After every edge deletion,
the algorithm either updates $W$ or outputs a $(\phi n^{o(1)})$-vertex-sparse
$(1/n^{o(1)})$-vertex-balanced vertex-cut and terminates.

Let $W^{(i)}$ be $W$ after the $i$-th update. There exists a set
$R$ of reset indices where $|R|=\Ohat(\phi^{-1})$, such that
for each $i\notin R$, $W^{(i)}\supseteq W^{(i+1)}$. That is, the
algorithm has $\Ohat(\phi^{-1})$ phases such that, within each phase,
$W$ is a decremental graph. The algorithm reports when each phase begins. It explicitly maintains the embedding $\pset$ of $W$ into $G$ and reports all changes made to $W$ and $\pset$.

To obtain the above result, we observe that an arbitrary embedding $\pset$ might not be robust to adversarial deletions, because a small number of edges might have most of the flow. To balance the edge-congestion, we introduce a capacity $\kappa(e)$ on each edge. Initially we set $\kappa(e) = 1/d$, where $d$ is the average degree in the input graph. At each step, the algorithms uses approximate flows and the cut-matching game to try to find a witness with vertex congestion $\Otil(1/\phi)$ and edge-congestions $\kappa(e)$. If it fails, the subroutine finds a low-capacity cut $C$; it then doubles capacities in $C$ and tries again. Since we assume a witness does exist, the algorithm will eventually find a witness once the edge-capacities are high enough.

Once we have a witness $W$ with embedding $\pset$, we use the lazy approach. Say the adversary deletes an edge $(u,v)$. Because our embedding obeyed capacity constraints, this can remove at most edges from $W$ of total weight at most $\kappa(u,v)$. To maintain expansion, we feed these deletions into our expander pruning algorithm (Theorem <ref>) to yield a pruned set $P$, and shrink our witness to $W[V(W) - P]$. To guarantee that $W$ remains a large witness, we end the phase once the pruned set $P$ it too large. We will show that we end a phase only after the adversary deletes $\Omegahat(n)$ edge-capacity from the graph.

As with $\rmatching$, the crux of our analysis will be to show that the total of number of doubling steps is $\Ohat(1/\phi)$. To do so, we again use costs $c(e) = \log(d\kappa(e))$ and use a potential function $\Pi(G,\kappa)$ which measures the min-cost embedding in $G$ among all very large $\phi$-witness. As the vertex congestion is $1/\phi$, this potential $\Pi(G,\kappa)$ is at most $n/\phi$. Also, we are able to show that each doubling step increases the potential by $\Omegahat(n)$ using an argument that is more involved than the one for matching. Therefore, there are at most $\Ohat(1/\phi)$ doubling steps as desired.

Given this bound, we can bound the total number of phases: each doubling step adds at most $n$ to the total capacity $\kappa$, and the initial capacity is at most $1/d \cdot m = n$. So the final total capacity is at most $\Ohat(n/\phi)$. As each phase must delete $\Omegahat(n)$ capacity, there are at most $\Ohat(1/\phi)$ phases.

Again, to highlight the strength of this result, the above theorem shows we only need to re-embed a witness $\Ohat(\phi^{-1})$ times throughout the entire sequence of deletions, whereas we showed that the standard technique might require $\Omegatil(n)$ re-embeddings in the worst case.

A Deterministic Data Structure for decremental SSSP. Finally, we note that much like in <Ref>, we can actually use a low-diameter decomposition to find an approximate generalized topological order (ATO) which we can then use in conjunction with the ES-tree to obtain a fast implementation of decremental SSSP. The main difference between our data structure in the deterministic setting apart from the way that the low-diameter decomposition is maintained, is that we can also not allow a randomized separator but have to use deterministic separator vertices when constructing the ATO. We use the rest of this article to prove that it is indeed possible to obtain a non-trivial ATO even under these restrictions.

§ DETERMINISTIC SSSP IN DECREMENTAL GRAPHS

In this section, we prove our main results: <Ref>. Recall that our decremental SSR/SCC result combines our new expander-based framework with earlier techniques for decremental SCC in <cit.>. Our decremental SSSP results uses the new framework in a similar way, but now combines it with earlier tools for decremental SSSP in <cit.>. In particular, we start with the following proposition, which essentially combined Proposition <ref> and Theorem <ref>.

Let $G=(V,E,w)$ be a weighted decremental graph, and $s \in V$ a fixed source. Let $\mathcal{A}$ be a data structure given some integer $d >0$, that processes edge deletions to $E$ and after every edge deletion ensures that 1) $G$ is strongly-connected and has diameter at most $d$ and 2) supports path queries between any two vertices in $G$ that returns a path of length $\Ohat(d)$ in almost-path-length query time and runs in total update time $T(m,n,d)$ (here we assume $T(m_1, n_1, d_1) + T(m_2, n_2, d_2) \leq T(m,n,d)$ for all choices $m,n,d$ and $m_1, m_2, n_1, n_2, d_1, d_2$ such that $m = m_1 + m_2$, $n = n_1 + n_2$ and $d = d_1 + d_2$). At any time the data structure may perform the following operation: it finds and outputs a $\Ohat(1/d)$-sparse cut $(L,S,R)$ where $|L| \leq |R|$ and replaces $G$ with $G[R]$; here we only require the algorithm to output $L$ and $S$ explicitly. (This sparse-cut operation is not an adversarial update, but is rather something the data structure can do of its own accord at ay time.)

Then, there exists a deterministic data structure $\mathcal{B}$ that can report $(1+\epsilon)$-approximate distance estimates and corresponding paths from $s$ to any vertex $v \in V$ in the graph $G$ in almost-path-length query time and has total update time $\Ohat((T(m,n,\delta) + n^3/\delta + n^2 \delta + mn^{2/3})\log W/\epsilon)$ for any choice of $\delta, \epsilon > 0$. (Note that the data structure can cause $V(G)$ to shrink over time via sparse-cut operations, so it only has to answer queries for vertices $u,v$ in the current graph.)

It is straight-forward to obtain <Ref> from the proposition, and <Ref>.

We now show how to implement the data structure $\mathcal{A}$ required by the setup of <Ref>, with $T(m,n,\delta) = \Ohat(m\delta^2)$ as follows. Given the graph $G$, we can invoke the algorithm described in <Ref> with parameter $\phi = \hat{\Theta}(1/\delta)$, such that the algorithm  maintains a $\phi$-short-witness $W$ that restarts up to $\Ohat(1/\phi) = \Ohat(\delta)$ times. Whenever $W$ starts a new phase, we use the data structures from <Ref> and 	<Ref> on $G$ and $W$ until the phase ends. We forward the sparse cuts $(L,S,R)$ found in the algorithm from <Ref> and  <Ref> and update $G$ accordingly. Thus after the algorithm from <Ref> terminates, the graph $G$ contains only a constant fraction of the vertices that the algorithm in <Ref> was initialized upon. We then repeat the above construction and note that after at most $O(\log n)$ times, the graph $G$ is the empty graph.

We note that to obtain a path between any two vertices in the current graph $G$, we can query the data structures from <Ref> and <Ref> to obtain such a path of length $\Ohat(\delta)$ in almost-path-length time. We further observe that if we set $\phi$ to $\frac{1}{\delta n^{o(1)}}$, for a large enough subpolynomial factor $n^{o(1)}$, then we can ensure that vertices in $G \setminus W$ are at all times at most $\delta/3$ away from some vertex in $W$ by <Ref>, have that any two vertices in $W$ are at distance at most $\delta/3$ to each other in $G$ by <Ref> and <Ref>, and again, that there exists a path to every vertex in $G \setminus W$ to a vertex in $W$ of length at most $\delta/3$. But this implies that any two vertices in $G$ are at all times at distance at most $\delta$ and therefore the diameter of $G$ is upper bounded by $\delta$, as required.

The total update time of the data structure $\mathcal{A}$ is at most $\Ohat(m/\phi^2) = \Ohat(m\delta^2)$ by adding the running time of <Ref> with the running time induced by the algorithms in <Ref> and 	<Ref> which are restarted in $\Ohat(\delta)$ phases.

We thus derive an algorithm $\mathcal{B}$ as specified in <Ref>, where we use the above data structure $\mathcal{A}$ and where we set $\delta = n^{1/3}$ which gives total update time

\begin{align*}
&\Ohat((T(m,n,\delta) + n^3/\delta + n^2 \delta + mn^{2/3})\log W/\epsilon)= n^{2+2/3 + o(1)} \log W/\epsilon.
\end{align*}

The rest of this section is dedicated to prove <Ref>. We refer the reader to the additional preliminaries from last chapter in <Ref> for notation used in the next section.  We then again use the abstraction of approximate topological orders which we reduce the problem to and finally prove that an approximate topological order can be maintained efficiently.

§.§ SSSP via Approximate Topological Orders

Let us briefly restate the concept of an approximate topological order which we define slightly different but still quite similar to <Ref> and which we implement similar to <cit.>. Recall that the main idea of an approximate topological order is as follow: consider the generalized topological order $(\mathcal{V}, \tau)$ of a graph $G$. Then $G / \mathcal{V}$ is a directed acyclic graph by definition. But this implies that for any (shortest) $s$-to-$t$ path $\pi_{s,t}$ in $G$ we have that  every edge $(X,Y)$ on $\pi_{s,t} / \mathcal{V}$ in $G / \mathcal{V}$ has $\tau(X) < \tau(Y)$. Since further $\tau$ maps to numbers between $1$ and $n$, we have thus that summing along the topological difference of the edges of  $\pi_{s,t} / \mathcal{V}$, we that $\mathcal{T}(\pi_{s,t}, (\mathcal{V}, \tau))$ is at most $n$.

Next, let us assume that the sum of diameters of all SCCs in $\mathcal{V}$ is at most $\epsilon \delta$, then for any shortest path $\pi_{s,t}$, we can upper bound the difference in weight between $\pi_{s,t}/\mathcal{G}$ path in $G / \mathcal{V}$ as opposed to $\pi_{s,t}$ in $G$ by an additive term of $\epsilon \delta$. So, if $\pi_{s,t}$ is of weight at least $\delta$, the additive term can be subsumed in a multiplicative error of $(1\pm\epsilon)$.

Now, the gist of this set-up is that given this upper bound on $\mathcal{T}(\pi_{s,t}, (\mathcal{V}, \tau))$, we can implement a fast SSSP data structure as follows. We know that on a path of length $\delta$ in $G / \mathcal{V}$ there are at most $\delta / 2^i$ edges that have topological order difference more than $2^i n/\delta$ by the pigeonhole principle for any $i$. But this implies that adding an additive error of $\epsilon 2^i$ on each such edge would only amount to an $(1+\epsilon)$ multiplicative error of a shortest path of length $\delta$. But this allowance for a significant additive error can be exploited to speed-up the SSSP data structure significantly because it allows for vertices to consider the neighbors that are close in topological order difference more closely while being more lenient when passing updates to vertices that are far in terms of topological order difference.

Before we state a data structure from <Ref> that exploits this very efficiently, let us now state more formally the construct of an approximate topological order. Here, we point out one last issue: we cannot assume that SCCs in $G$ have small diameter in general. Therefore we maintain the generalized topological order on a graph $G'$ initialized to $G$ where we, additionally to adversarial edge updates to $G$, also take vertex separators $S$ such that edges incident to $S$ are deleted from $G'$. This ensures that all SCCs in $G'$ have small diameter. Relating back to $G$ (where no separator was deleted) we have that $\mathcal{T}(\pi_{s,t}, (\mathcal{V}, \tau))$ might be increased by this operation since some edge $(X,Y)$ on $\pi_{s,t} /\mathcal{V}$ with $X$ or $Y$ containing a separator vertex $S$, such that $(X,Y)$ might now go "backwards" in the topological order, i.e. have $\tau(X) > \tau(Y)$. This increases $\mathcal{T}(\pi_{s,t}, (\mathcal{V}, \tau))$ by up to $2n-2$ for every separator vertex since we might move along $(X,Y)$ all the way back in the topological order and then forward again. However, by choosing small separators, we can still bound $\mathcal{T}(P, (\mathcal{V}, \tau))$ by a non-trivial upper bound.

Without further due, let us give the formal definition of an approximate topological order.

Given a decremental weighted digraph $G=(V,E,w)$ and parameter $\eta \leq n$ and $\nu \leq W$, we say a dynamic tuple $(\mathcal{V}, \tau)$ where $\mathcal{V}$ partitions $V$, and $\tau : \mathcal{V} \rightarrow [1,n]$, is an $\mathcal{ATO}(G, \eta, \nu)$ if at each stage

* $\mathcal{V}$ forms a refinement of all earlier versions of $\mathcal{V}$ and $\tau$ is a nesting function, i.e. $\tau$ initially assigns each set in $X$ in the initial version of $\mathcal{V}$ a number $\tau(X)$, such that no other set $Y$ in $\mathcal{V}$ has $\tau(Y)$ in the interval $[\tau(X), \tau(X) + |X| - 1]$. If some set $Y \in \mathcal{V}$ is split at some stage into disjoint subsets $Y_1, Y_2, .., Y_l$, then we let $\tau(Y_1) = \tau(Y)$ and $\tau(Y_{i+1}) = \tau(Y_i) + |Y_i|$. We then return a pointer to each new subset $Y_i$ such that all vertices in $Y_i$ can be accessed in time $O(|Y_i|)$. The value $\tau(X)$ for each $X \in \mathcal{V}$ can be read in constant time.

* each set $X$ in $\mathcal{V}$ has weak diameter $\mathbf{diam}(X, G) \leq \frac{|X| \eta \nu}{n}$, and

* At each stage, for any vertices $s, t \in V$, the shortest-path $\pi_{s,t}$ in $G$ satisfies $\mathcal{T}(\pi_{s,t}, (\mathcal{V}, \tau)) = \Ohat
\left(\frac{n^2}{\eta} + n\cdot \frac{\mathbf{dist}_G(s,t)}{\nu}\right)$.

Here, we captured in Property <ref>, that the vertex sets in $\mathcal{V}$ decompose over time, that $\tau$ is nesting and that all sets are easily accessible. In Property <ref>, we capture that the sum of diameters of the vertex sets in $\mathcal{V}$ is small. It is not hard to see that by summing the upper bound on the diameter of all such sets $X$ in $\mathcal{V}$, we get that the sum of diameters is bounded by $\eta \nu$. Finally, we give an upper bound for the topological order difference for any shortest-path in $G$.

The main result of the next section, shows that we can maintain an $\mathcal{ATO}$ using data structure $\mathcal{A}$ from <Ref>.

Given a decremental weighted digraph $G=(V,E,w)$, parameters $\eta \leq n, \nu \leq W$, and a data structure $\mathcal{A}$ as described in <Ref> that can for each SCC $X$ in $\mathcal{V}$ at any point return a path between any two vertices $u,v \in X$ of length $\Ohat(\frac{|X|\eta \nu}{n})$ in near-linear time. Then, we can deterministically maintain a $\mathcal{ATO}(G, \eta, \nu)$ in total update time $\Ohat(T(m,n,\eta) + mn^{2/3})$.

We now restate <Ref> from <Ref> although we present it in a slightly modified form to adapt it to the modified definition of an $\mathcal{ATO}$ that we use for this paper. However, the adaption is obtained straight-forwardly and we refer the reader to <Ref> to verify.

[see <Ref>]theoremssspSimple2

Given $G=(V,E,w)$, a decremental weighted digraph, a source $r \in V$, an approximation parameter $\epsilon > 0$, and access to $(\mathcal{V}, \tau)$ an $\mathcal{ATO}(G, \eta, \nu)$.

Then, there exists a deterministic data structure that maintains a distance estimate $\widetilde{\mathbf{dist}}(r,v)$ for every vertex $v \in V$ such that at each stage of $G$, $\mathbf{dist}_G(r,v) \leq \widetilde{\mathbf{dist}}(r,v)$ and if $\mathbf{dist}_G(r,v) \in [\eta \nu/\epsilon, 2\eta \nu/\epsilon)$, then

\[
\widetilde{\mathbf{dist}}(r,v) \leq (1+\epsilon)\mathbf{dist}_G(r,v)
\]

and the algorithm can for each such vertex $v$, report a path of length $(1+\epsilon)\mathbf{dist}_G(r,v)$ in the graph $G / \mathcal{V}$ in almost-path-length time. The total time required by this structure is

\[
\Ohat\left(\frac{n^3}{\eta\epsilon} + \cdot \frac{n^2 \eta}{\epsilon}\right).
\]

We can now prove <Ref>.

For every $0 \leq i \leq \lg W$, where $W$ is the aspect ration of $G=(V,E,w)$, we maintain at level $i$, an $\mathcal{ATO}(G, \delta, 2^i)$ using <Ref>, and then running <Ref> on $G$ and the $\mathcal{ATO}(G, \delta, 2^i)$ from our source vertex $s$ to depth $\delta \cdot 2^i$. Thus, each such data structure maintains for every vertex $v$ at distance $[\delta \cdot 2^i/\epsilon', \delta \cdot 2^{i+1}/\epsilon')$ from $s$ an $(1+\epsilon')$-approximate distance estimate. We can therefore find for every vertex $v$ at distances larger than $\delta/\epsilon'$ from $s$ a distance estimate in some of these data structures that gives the right approximation, and since all data structures overestimate the distance, we can find the right distance estimate by comparing all distance estimates $\widetilde{\mathbf{dist}}(s,v)$. Finally, we can maintain a simple ES-tree in time $O(m \delta/\epsilon')$ to obtain exact distances from $s$ to every vertex at distance at most $\delta$.

It is not hard to verify that the total update time of all data structures is

\begin{align*}
&\sum_{0 \leq i \leq \lg W} \left( \Ohat\left(\frac{n^3}{\delta\epsilon'} + \cdot \frac{n^2 \delta}{\epsilon'}\right) + \Ohat(T(m,n,\delta) + mn^{2/3})\right) \\
&= \Ohat((T(m,n,\delta) + n^3/\delta + n^2 \delta + mn^{2/3})\log W/\epsilon').
\end{align*}

for $\epsilon'$ to be set $\epsilon' = \epsilon/n^{o(1)}$ which is again subsumed in the $\Ohat$-notation.

To answer path queries for a $s$-to-$v$ path $\pi_{s,v}$, we query the corresponding shortest path data structure where we found a $(1+\epsilon')$-approximation. This gives us the path $\widetilde{\pi_{s,v}}$ in $G / \mathcal{V}$ for some $\mathcal{ATO}$ $(\mathcal{V}, \tau)$. We then identify for every vertex $x$ on $\widetilde{\pi_{s,v}}$ the corresponding SCC in $\mathcal{V}$ and the two endpoints in $G$ of the incident edges on $\widetilde{\pi_{s,v}}$. We can then query for a path between these two vertices in the $\mathcal{ATO}$ data structure. Summing over all exposed paths, by <Ref>, we can extend the path $\widetilde{\pi_{s,v}}$ to a path in $G$ of length $(1+\epsilon')\mathbf{dist}_G(s,v) + \Ohat(\eta \nu)$. But we have that $\mathbf{dist}_G(s,v) \geq \delta/\epsilon'$. Thus, setting $\epsilon'$ to $\epsilon/2$ divided by the subpolynomial factor hidden in $\Ohat(\eta \nu)$, we obtain a path of length $(1+\epsilon)\mathbf{dist}_G(s,v)$. Since each piece on the path can be obtained in almost-path-length time, we can also construct the extension of path $\widetilde{\pi_{s,v}}$ to a path in $G$ in almost-path-length time. This completes the proof.

§.§ A Deterministic Algorithm to Maintain an Approximate Topological Order

Finally, let us prove the main ingredient to achieve our result.

We start the proof by partitioning the edge set $E$ of the initial graph $G$ into edge set $E^{heavy}$ and $E^{light}$. We assign every edge $e \in E$ to $E^{heavy}$ if its weight $w(e)$ is larger than $\nu$, and to $E^{light}$ if $w(e) \leq \nu$.

We now describe our algorithm where we focus on the graph $G$ where the edge set $E^{heavy}$ is removed. As we will see later, there can only be few edges from $E^{heavy}$ on any shortest path. Let us start the proof by giving an overview and then a precise implementation. We finally analyze correctness and running time.

Algorithm. Our goal is subsequently to maintain an incremental set $\hat{S} \subseteq V$ such that every SCC $X$ in $G' = G \setminus E(\hat{S}) \setminus E^{heavy}$ has unweighted diameter at most $\frac{|X|\eta}{n}$. Since each edge weight is at most $\nu$ this will imply that every SCC $X$ in the weighted version of $G'$ has diameter at most $\frac{|X|\eta\nu}{n}$.

We then maintain $(\mathcal{V}, \tau)$ as the generalized topological order of $G'$ using the data structure described in <Ref> which is a straight-forward extension of <Ref> using internally the algorithm by Tarjan <cit.> as described in <cit.>.

To maintain $G'$, we initialize a data structure $\mathcal{A}$ on every SCC $X$ in the initial set $\mathcal{V}$ on the graph $G'[X]$ with parameter $d = \frac{|X|\eta}{2n}$. Then, whenever such a data structure $\mathcal{A}$ that currently operates on some graph $G'[Y]$, announces a sparse cut $(L, S, R)$ and sets its graph to $G'[R]$, we add $S$ to $\hat{S}$ and then initialize a new data structure $\mathcal{A}'$ on $G'[L]$ with parameter $d = \frac{|L|\eta}{2n}$. Further, if the data structure $\mathcal{A}$ was initialized on a graph with vertex set at least twice as large as $R$, we delete $\mathcal{A}$, and initialize a new data structure $\mathcal{A}''$ on $G'[R]$ with $d = \frac{|R|\eta}{2n}$. This completes the description of the algorithm.

Correctness of the Algorithm. We prove each property of the theorem individually:

* Property <ref>: It is straight-forward to see that since $(\mathcal{V}, \tau)$ is the generalized topological order of $G' \subseteq G$ and since it is maintained to satisfy the nesting property, that Property <ref> follows immediately.

* Property <ref>: Observe that $\mathcal{V}$ is the set of SCCs in $G'$. Further, observe that we maintain the data structures $\mathcal{A}_1, \mathcal{A}_2, \dots$ such that vertex set of all graphs that they run on spans all vertices in $V \setminus S$. For the vertices in $S$ we have that each $s \in \hat{S}$ forms a trivial SCC and therefore certainly satisfies the constraint. For each set $X$ that some data structure $\mathcal{A}$ runs upon, we have that the unweighted diameter is at most the $d$ that $\mathcal{A}$ was initialized with. Observe that we delete data structures if the size of the initial vertex set $Y$ is decreased by factor $2$. Thus, we have that the data structure $\mathcal{A}$ was initialized for some $d = \frac{|Y|\eta}{2n} \leq \frac{|X|\eta}{n}$. Since the largest edge weight in $G'$ is $\nu$, we thus have that for each SCC $X$ in $\mathcal{V}$, we have $\mathbf{diam}(X,G') \leq \frac{|X|\eta \nu}{n}$. Adding edges in $E(\hat{S})$ and $E^{heavy}$ can further only decrease the weak diameter and therefore we finally obtain that,

\[
\mathbf{diam}(X,G) \leq \frac{|X|\eta \nu}{n}.
\]

* Property <ref>: In order to establish the last property, let us partition the set $\hat{S}$ into sets $S_1, S_2, \dots, S_{\lg n}$ where a vertex $s$ is in $S_i$ if it joined $\hat{S}$ after a data structure $\mathcal{A}$ announced it that was initialized on a graph $G'[Y]$ where $Y$ was of size $[n/2^{i+1},n/2^i)$. Since we delete data structures after their initial vertex set has halved in size, we have that are such data structure that added vertices to a set $S_i$ ran with $d \geq \frac{(n/2^{i+1}) \eta}{2n} = \frac{n \eta}{2^{i+2}}$. Since each such set of vertices $S$ that was added to $S_i$ is $\Ohat(1/d)$-sparse and we then only compute sparse cuts on the induced subgraphs of the cut, we further have that there are at most $\Ohat(n/d) = \Ohat(2^i/\eta)$ vertices in $S_i$ at the end of the algorithm. Further, we observe that every edge $(u,v)$ that was contained in the subgraph $G'[Y]$ when $\mathcal{A}$ was initialized has both endpoints in $Y$ and therefore by property <ref>, we have $|\tau(u) - \tau(v)| < |Y| \leq n/2^{i-1}$.

Now, let us fix any shortest path $\pi_{s,t}$ in $G$ (in the current version). Instead of analyzing $\mathcal{T}(\pi_{s,t}, (\mathcal{V}, \tau))$, let us analyze

\[
\mathcal{T}'(\pi_{s,t}, (\mathcal{V}, \tau)) \stackrel{\text{def}}{=} \sum_{(u,v) \in \pi_{s,t}} \max\{ 0 , \tau(u) - \tau(v)\}.
\]

which only considers the edges on the path that go "backwards" in the topological order. However, it can be seen that for every path $\mathcal{T}(\pi_{s,t}, (\mathcal{V}, \tau)) \leq 2\mathcal{T}'(\pi_{s,t}, (\mathcal{V}, \tau)) + n$.

For edges on $\pi_{s,t}$ in $E^{heavy}$, we observe that each such edge $(u,v)$ can contribute to $\mathcal{T}'(\pi_{s,t}, (\mathcal{V}, \tau))$ at most $n$ since $\tau(u) - \tau(v) \leq n$ (trivially since both numbers are taken from the interval $[1,n]$). Further, since each such edge adds weight at least $\nu$ to the shortest path, there are at most $\frac{\mathbf{dist}(s,t)}{\nu}$ such edges. Thus, the total contribution by all these edges is at most $n \frac{\mathbf{dist}(s,t)}{\nu}$.

For the edges on $\pi_{s,t}$ in $E^{light}$, we observe that each edge $(u,v)$ that contributes to $\mathcal{T}'(\pi_{s,t}, (\mathcal{V}, \tau))$ is not in $G'$ since $(\mathcal{V}, \tau)$ is a generalized topological order of $G'$ and therefore directed "forwards" (recall the definition in <ref>). Thus, each such edge is in $E(\hat{S})$ and therefore incident to some vertex $s$ in some $S_i$. But then it adds at most $n/2^{i-1}$ to $\mathcal{T}'(\pi_{s,t}, (\mathcal{V}, \tau))$ by our previous discussion. Since a path only visits each vertex once, and by our bound on the size of $S_i$, we can now bound the total contribution by

\[
\mathcal{T}'(\pi_{s,t}, (\mathcal{V}, \tau)) \leq \sum_{i} |S_i| n/2^{i-1} = \Ohat(n^2/\eta + n \frac{\mathbf{dist}(s,t)}{\nu})
\]

Bounding the Running Time. Observe that for any vertex $x \in V$, that between any two times that it part of a graph $G'[Y]$ that a data structure $\mathcal{A}$ is invoked upon and of graph $G'[X] \subseteq G'[Y]$, the set $X$ is of at most half the size of $Y$. This follows by the definition of data structure $\mathcal{A}$ which whenever a sparse cut $(L,S,R)$ is output, continues on the graph $G'[R]$ where $R$ is larger than $L$ while no data structure is thereafter initialized on a graph containing any vertex in $S$.

But if the SCC that some vertex $x$ is contained in halves in size every time between two data structures $\mathcal{A}$ are initialized upon $x$, then we have that $x$ participates in at most $\lg n$ data structures over the entire course of the algorithm. Since each edge $(x,y)$ or $(y,x)$ for any $y \in V$ is only present in the induced graph containing $x$, we have that no data structure that is not initialized on a graph with vertex set contain $x$ has $(x,y)$ or $(y,x)$ in its graph. Thus, every edge only participates in $\lg n$ graphs.

Finally, we observe that the distance parameter $d$ that each data structure $\mathcal{A}$ is upper bounded by $\eta/2$. Thus, by the (super-)linear behavior of the function $T(m,n,d)$, we have that the total update time for all data structures in $\Ohat(T(m,n,\eta))$. Further, we have by <Ref> that the data structure maintaining $(\mathcal{V}, \tau)$ can be implemented in time $\Ohat(mn^{2/3})$. The time required for all remaining operations is subsumed in both bounds.

Returning the Paths. For any SCC $X$ in $\mathcal{V}$, we have that there is a data structure $\mathcal{A}$ on $G'[X]$ that allows for SCC queries. Since by our previous discussion each such data structure runs with $d$ at most $\frac{|X|\eta}{n}$ and each edge on the path has weight at most $\nu$ (recall that $G'$ only contains edges of small weight), we can return the path from data structure $\mathcal{A}$ on query.

CHAPTER: A DETERMINISTIC ALGORITHM FOR INCREMENTAL SSSP

In this chapter, we prove the second part of <Ref>. We state the precise Theorem.

Given a decremental input graph $G=(V,E,w)$ with $n = |V|, m=|E|$ and aspect ratio $W$, a dedicated source $r \in V$ and $\epsilon > 0$, there is a deterministic algorithm that maintains a distance estimate $\widetilde{\mathbf{dist}}(r,x)$, for every $x \in V$, such that

\[
{\mathbf{dist}}_G(r,x) \leq \widetilde{\mathbf{dist}}(r,x) \leq (1+\epsilon) {\mathbf{dist}}_G(r,x)
\]

at any stage of $G$. The algorithm has total update time $\tilde{O}(n^2 \log W/\poly(\epsilon))$. Distance queries are answered in $O(1)$ time, and a corresponding path $P$ can be returned in $O(|P|)$ time.

As opposed to previous sections, we do not start this chapter with an overview, but instead present a first $O(n^{2+2/3}/\epsilon)$ total update time algorithm that is simple and captures our main ideas. We then give an overview that explains how to extend the ideas to obtain the running time stated in <Ref>. The rest of the chapter is then concerned with proving <Ref> (however, we only sketch some of the more technical proofs). We point out that in order to avoid clutter, we first prove <Ref> for unweighted graphs, and only in the last section show that in a weighted graph the dependency on the weight ratio becomes only polylogarithmic, and therefore we can use the reduction stated in <Ref> to reduce the dependency on $W$ to $\log W$ as claimed.

§ WARM-UP: AN $O(N^{2+2/3}/\EPSILON)$ TIME ALGORITHM

In this section we describe an algorithm for incremental SSSP on unweighted directed graphs with total update time  $O(n^{2+2/3}/\epsilon)$. This algorithm illustrates the main ideas used in our $\tilde{O}(n^2 \log W/\epsilon)$ algorithm.

There is a deterministic algorithm that given an unweighted directed graph $G=(V,E)$ subject to edge insertions, a vertex $r \in V$, and $\epsilon>0$, maintains for every vertex $v$ an estimate $\widetilde{\mathbf{dist}}(r,v)$ such that after every update $\mathbf{dist}(r,v)\leq \widetilde{\mathbf{dist}}(r,v)\leq (1+\epsilon)\mathbf{dist}(r,v)$, in total time $O(n^{2+2/3}/\epsilon)$.

To obtain this result, we take inspiration from a simple property of undirected graphs: Any two vertices at distance at least $3$ have disjoint neighborhoods. This observation is crucial in several spanner/hopset constructions as well as other graph algorithms (for example <cit.>), as well as partially dynamic SSSP on undirected graphs <cit.>. In <cit.>, Bernstein and Chechik exploit this property for partially dynamic undirected SSSP in the following way. The property implies that for any vertex $v$ on a given shortest path from $r$ to some $t$, the neighborhood of $v$ is disjoint from almost all of the other vertices on this shortest path. Thus there cannot be too many high-degree vertices on any given shortest path, and therefore high-degree vertices are allowed to induce large additive error which can be exploited to increase the efficiency of the algorithm (much like in <Ref>).

Whilst we would like to argue along the same lines, this property is unfortunately not given in directed graphs: there could be two vertices $u$ and $v$ at distance $3$, and a third vertex $z$ that only has in-coming edges from $u$ and $v$. Clearly, $u$ and $v$ can now still be at distance $3$ whilst their out-neighborhoods overlap. We overcome this issue by introducing forward neighborhoods $\mathcal{FN}(u)$ that only include vertices from the out-neighborhood $\mathcal{N}^{out}(u)$ that are estimated to be further away from the source vertex $r$ than $u$. Now, suppose there are two vertices $u$ and $v$ both appear on some shortest path from $r$ to some $t$ and whose forward neighborhoods overlap. Let $w$ be a vertex in $\mathcal{FN}(u) \cap \mathcal{FN}(v)$. Since $w$ has a larger distance estimate than $u$ and the edge $(u,w)$ is in the graph, the distance estimates of $u$ and $w$ must be close, assuming that each distance estimate does not incur much error.

Similarly, the distance estimates of $v$ and $w$ must be close. But then the distance estimates of $u$ and $v$ must also be close. Therefore, the forward neighborhood of each vertex on a long shortest path must only overlap with the forward neighborhoods of few other vertices on the path. In summary, our extension of the property to directed graphs is that if the distance estimates of $u$ and $v$ differ by a lot, then $u$ and $v$ have disjoint forward neighborhoods.

The data structure

In order to illustrate our approach, we present a data structure that only maintains approximate distances for vertices $u$ that are at distance $\mathbf{dist}(r,u) > n^{2/3}$. This already improves the state of the art since  we can maintain the exact distance $\mathbf{dist}(r,u)$ if $\mathbf{dist}(r,u)\leq n^{2/3}$ simply by using a classic ES-tree to depth $n^{2/3}$ which runs in time $O(mn^{2/3})$.

To understand the motivation behind our main idea, let us first consider a slightly modified version of the classic ES-trees that achieves the same running time: We maintain for each vertex $u\in V$ an array $A_u$ with $n$ elements where $A_u[i]$ is the set of all vertices $v \in \mathcal{N}^{out}(u)$ with $\mathbf{dist}(r,v)=i$. Then, when $\mathbf{dist}(r,u)$ decreases, the set of vertices in $\mathcal{N}^{out}(u)$ whose estimated distance from $r$ decreases is exactly the set of vertices stored in $A_u[\mathbf{dist}^{NEW}(r,u) + 2, n]$ which we call the forward neighborhood $\mathcal{FN}(u)$ of $u$. (Recall that $A_u[i,j]$ is  the subarray of $A$ from index $i$ to index $j$, inclusive.) That is since each such vertex $v$ has at estimated distance more than $\mathbf{dist}(r,u) + 1$ thus relaxing the edge $(u,v)$ is ensured to decrease $v$'s distance. Thus, we only need to scan edges with tail $u$ and head $v \in \mathcal{FN}(u)$, however, we also need to update $A_u$ whenever an in-neighbor of $u$ decreases its distance estimate.

For our data structure which we call a “lazy” ES-tree, we relax several constraints and use a lazy update rule. Instead of maintaining the exact value of $\mathbf{dist}(r,v)$ for all $v \in \mathcal{N}^{out}(u)$, we only maintain an approximate distance estimate $\widetilde{\mathbf{dist}}(r,v)$. Whilst we still maintain an array for each vertex $u \in V$, we now only update the position of $v$ only after $\widetilde{\mathbf{dist}}(r,v)$ has decreased by at least $n^{1/3}$ or if $(u,v)$ was scanned by $u$. To emphasize that this array is only updated occasionally, instead of using the notation $A_u$, we use the notation $\texttt{Cache}_u$. Again, we define $\texttt{Cache}_u[\widetilde{\mathbf{dist}}(r,u) + 2, n]$ to be the forward neighborhood of $u$ denoted $\mathcal{FN}(u) \subseteq \mathcal{N}^{out}(u)$. Further, if $\mathcal{FN}(u)$ is small (say of size $O(n^{2/3})$), we say $u$ is light. Otherwise, we say that $u$ is heavy.

Now, we distinguish two scenarios for our update rule: if $u$ is light, then we can afford to update the distance estimates of the vertices in $\mathcal{FN}(u)$ after every decrease of $\widetilde{\mathbf{dist}}(r,u)$. However, if $u$ is heavy, then we only update the vertices in $\mathcal{FN}(u)$ after the distance estimate $\widetilde{\mathbf{dist}}(r,u)$ has been decreased by at least $n^{1/3}$ since the last scan of $\mathcal{FN}(u)$.

Additionally, for each edge $(u,v)$, every time $\widetilde{\mathbf{dist}}(r,v)$ decreases by at least $n^{1/3}$, we update $v$'s position in $\texttt{Cache}_u$.

Finally, we note that $|\mathcal{FN}(u)|$ changes over time and so we need to define the rules for when a vertex changes from light to heavy and vice versa more precisely. Initially, the graph is empty and we define every vertex to be light. Once the size of $\mathcal{FN}(u)$ is increased to $\gamma = 6n^{2/3}/\epsilon$, we set $u$ to be heavy. On the other hand, when $|\mathcal{FN}(u)|$ decreases to $\gamma/2$, we set $u$ to be light. Whenever $u$ becomes light, we immediately scan all $v\in \mathcal{FN}(u)$ and decrease each $\widetilde{\mathbf{dist}}(r,v)$ accordingly. This completes the description of our algorithm.

Running time analysis

Let us now analyze the running time of the lazy ES-tree. For each vertex $u$, every time $\widetilde{\mathbf{dist}}(r,u)$ decreases by $n^{1/3}$, we might scan $u$'s entire in- and out-neighborhoods. Since $\widetilde{\mathbf{dist}}(r,u)$ can only decrease at most $n$ times, the total running time for this part of the algorithm is $O(nm /n^{1/3}) = O(mn^{2/3})$.

For every light vertex $u$, we scan $\mathcal{FN}(u)$ every time $\widetilde{\mathbf{dist}}(r,u)$ decreases. Since $\widetilde{\mathbf{dist}}(r,u)$ can only decrease at most $n$ times and since $u$ is light, the total running time for all vertices spent for this part of the algorithm is $O(\sum_{v \in V} n\gamma )=O(n^{2+2/3}/\epsilon)$.

Whenever a vertex $u$ changes from heavy to light, we scan $\mathcal{FN}(u)$. If $u$ only changes from heavy to light once per value of $\widetilde{\mathbf{dist}}(r,u)$, then the running time is $O(n^{2+2/3}/\epsilon)$ by the same argument as the previous paragraph. So, we only consider the times in which $u$ toggles between being light and heavy whilst having the same value of $\widetilde{\mathbf{dist}}(r,u)$. Since the position of vertices in $\texttt{Cache}_u$ can only decrease, the only way for $u$ to become heavy while keeping the same value of $\widetilde{\mathbf{dist}}(r,u)$ is if an edge is inserted. Since $\gamma/2$ edges must be inserted before $u$ becomes heavy since it last became light, there were $\gamma/2$ edge insertions with tail $u$. Since each inserted edge is only added to a single $\mathcal{FN}(u)$ (namely to the forward neighborhood of its tail), we can amortize the cost of scanning the $\gamma/2$ vertices in $\mathcal{FN}(u)$ over the $\gamma/2$ insertions.

Combining everything, and since the classic ES-tree to depth $n^{2/3}$ takes at most $O(mn^{2/3})$ update time when run to depth $n^{2/3}$, we establish the desired running time.

Analysis of correctness
Let us now argue that our distance estimates are maintained with multiplicative error $(1+\epsilon)$. The idea of the argument can be roughly summarized by the following points:

* the light vertices do not contribute any error,

* we can bound the error contributed by pairs of heavy vertices whose forward neighborhoods overlap, and

* the number of heavy vertices on any shortest path with pairwise disjoint forward neighborhoods is small.

We point out that while the main idea of allowing large error in heavy parts of the graphs is similar to <cit.>, we rely on an entirely new method to prove that this incurs only small total error. We start our proof by proving the following useful invariant.

After every edge update, if $v\in \mathcal{FN}(u)$ then $|\widetilde{\mathbf{dist}}(r,v) - \widetilde{\mathbf{dist}}(r,u)| \leq n^{1/3}$.

First suppose that $\widetilde{\mathbf{dist}}(r,u) \leq \widetilde{\mathbf{dist}}(r,v)$. Since $\widetilde{\mathbf{dist}}(r,u)$ and $\widetilde{\mathbf{dist}}(r,v)$ can only decrease, we wish to show that $\widetilde{\mathbf{dist}}(r,u)$ cannot decrease by too much without $\widetilde{\mathbf{dist}}(r,v)$ also decreasing. This is true simply because every time $\widetilde{\mathbf{dist}}(r,u)$ decreases by at least $n^{1/3}$, $\widetilde{\mathbf{dist}}(r,v)$ is set to at most $\widetilde{\mathbf{dist}}(r,u)+1$.

Now suppose that $\widetilde{\mathbf{dist}}(r,u) > \widetilde{\mathbf{dist}}(r,v)$. Since $\widetilde{\mathbf{dist}}(r,u)$ and $\widetilde{\mathbf{dist}}(r,v)$ can only decrease, we wish to show that $\widetilde{\mathbf{dist}}(r,v)$ cannot decrease by too much while remaining in $\mathcal{FN}(u)$. This is true simply because every time $\widetilde{\mathbf{dist}}(r,v)$ decreases by at least $n^{1/3}$, we update $v$'s position in $\texttt{Cache}_u$. If $\widetilde{\mathbf{dist}}(r,v)< \widetilde{\mathbf{dist}}(r,u)+2$ and $v$'s position in $\texttt{Cache}_u$ is updated, then $v$ leaves $\mathcal{FN}(u)$.

Consider a shortest path $\pi_{r,t}$ for any $t \in V$, at any stage of the incremental graph $G$. Let $t_0=s$. Then, for all $i$, let $r_{i+1}$ be the first heavy vertex after $t_{i}$ on $\pi_{r,t}$ and let $t_{i+1}$ be the last vertex on $\pi_{r,t}$ whose forward neighborhood intersects with the forward neighborhood of $r_{i+1}$ (possibly $t_{i+1} = r_{i+1}$). Thus, we get pairs $(r_1, t_1), (r_2, t_2), \dots, (r_k, t_k)$. Additionally, let $r_{k+1} = t$. Since the forward neighborhoods of all $r_i$'s are disjoint and of size at least $\gamma/2$ (recall that $r_i$ is heavy), we have that there are at most $k\leq 2n/\gamma$ pairs $(r_i, t_i)$.

For each $i$, let $v_i$ be some vertex in $\mathcal{FN}(r_i)\cap \mathcal{FN}(t_i)$. Note that $v_i$ exists by definition of $t_i$. By Invariant <ref>, $|\widetilde{\mathbf{dist}}(r, r_i) - \widetilde{\mathbf{dist}}(r, v_i)| \leq n^{1/3}$ and $|\widetilde{\mathbf{dist}}(r, t_i) - \widetilde{\mathbf{dist}}(r, v_i)| \leq n^{1/3}$. Thus, $\widetilde{\mathbf{dist}}(r, t_i) - \widetilde{\mathbf{dist}}(r, r_i) \leq 2n^{1/3}$.

Let $t'_i$ be the vertex on $\pi_{r,t}$ succeeding $t_i$ (except $t'_0 = r$). If $t'_i\in \mathcal{FN}(t_i)$ then by Invariant <ref>, $\widetilde{\mathbf{dist}}(r, t'_i) - \widetilde{\mathbf{dist}}(r, t_i) \leq n^{1/3}$. Otherwise, $t'_i\not\in \mathcal{FN}(t_i)$ so $\widetilde{\mathbf{dist}}(r, t'_i)\leq \widetilde{\mathbf{dist}}(r, t_i)+1$. So regardless, we have $\widetilde{\mathbf{dist}}(r, t'_i) - \widetilde{\mathbf{dist}}(r, t_i) \leq n^{1/3}$ and therefore, since $\widetilde{\mathbf{dist}}(r, t_i) - \widetilde{\mathbf{dist}}(r, r_i) \leq 2n^{1/3}$, we have $\widetilde{\mathbf{dist}}(r, t'_i) - \widetilde{\mathbf{dist}}(r, r_i) \leq 3 n^{1/3}$.