]}

# Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update
Time

Xiao Mao
Stanford University
<EMAIL_ADDRESS>

###### Abstract

The All-Pairs Shortest Paths (APSP) problem is one of the fundamental problems
in theoretical computer science. It asks to compute the distance matrix of a
given $n$-vertex graph. We revisit the classical problem of maintaining the
distance matrix under a _fully-dynamic_ setting undergoing vertex insertions
and deletions with a fast _worst-case_ running time and efficient space usage.

Although amortized algorithm with $\widetilde{O}(n^{2})$111Throughout this
paper, we use $\widetilde{O}(f)$ to denote $O(f\cdot\text{poly}\log(f))$.
update-time has been known for nearly two decades [Demetrescu and Italiano,
STOC 2003], the current best algorithm for worst-case running time with
efficient space usage runs is due to [Gutenberg and Wulff-Nilsen, SODA 2020],
which improves the space usage of the previous algorithm due to [Abraham,
Chechik, and Krinninger, SODA 2017] to $\widetilde{O}(n^{2})$ but fails to
improve their running time of $\widetilde{O}(n^{2+2/3})$. It has been
conjectured that no algorithm in $O(n^{2.5-\varepsilon})$ worst-case update
time exists. For graphs without negative cycles, we meet this conjectured
lower bound by introducing a Monte Carlo algorithm running in randomized
$\widetilde{O}(n^{2.5})$ time while keeping the $\widetilde{O}(n^{2})$ space
bound from the previous algorithm. Our improvement is made possible using a
novel multi-layer approach that exploits the gaps between hops (number of
vertices traversed) of paths.

##  1 Introduction

The All-Pairs Shortest Paths (APSP) problem asks to compute the shortest
distance between each pair of vertices on an $n$-vertex graph, called the
_distance matrix_. Despite being one of the most widely studied problems in
theoretical computer science, on graphs with general weights the fastest
algorithm still runs in $n^{3}/2^{\Omega(\sqrt{\log{n}})}$ time [Wil14], and
thus it has been conjectured that an algorithm running in
$O(n^{3-\varepsilon})$ time is impossible for any $\varepsilon>0$. However,
under many _dynamic_ settings of the APSP problem where the graph undergoes
modifications such as vertex/edge insertion/deletions, the distance matrix can
be updated in a faster time than a cubic re-computation from scratch.

##### The Problem.

In this paper, we study the fully dynamic setting under vertex
insertion/deletions with a faster worst-case time. Formally, we are given a
graph $G=\langle\mathrm{V},\mathrm{E}\rangle$ with
$\left\lvert\mathrm{V}\right\rvert=n$ that undergoes vertex insertions and
deletions where each vertex is inserted/deleted together with its incident
edges. Our goal is to minimize the _update time_ , which is the time needed to
refresh the distance matrix. We measure the worst-case update time which is
opposed to amortized update time. In the randomized setting, the worst-case
update time is a time bound under which _every_ update can finish with the
correct answer with a probability of $1-n^{-c}$ for some constant $c>0$.

We point out that in the fully-dynamic setting, vertex updates are always more
general than edge updates since any edge update can be easily simulated by a
deletion and a re-insertion of one of the two incident vertices.

##### Previous Work.

Algorithms for dynamic All-Pairs Shortest Path Problem have been known since
the 1960s, the earliest partially dynamic algorithm was the well-known Floyd-
Warshall Algorithm [Flo62, War62] from as early as 1962222The algorithm is
essentially the same as earlier algorithms from 1959 by Bernard Roy [Roy59].
that can be easily extended to handle vertex insertion for $O(n^{2})$ time per
update given the distance matrix of the current $n$-vertex graph. It was not
until the end of that century that the first fully dynamic algorithm was given
by King [Kin99], with $\widetilde{O}(n^{2.5}\sqrt{W\log n})$ amortized update
time per _edge_ insertion/deletion where $W$ is the largest edge weight. Their
algorithm was based on a classic data structure for decremental Single-Source
Shortest Paths by Even and Shiloach [ES81]. Later, King and Thorup [KT01]
improved the space bound from $\widetilde{O}(n^{3})$ to
$\widetilde{O}(n^{2.5}\sqrt{W})$. The follow-up work by Demetrescu and
Italiano [DI02, DI06] generalized the result to real edge weights from a set
of size $S$. In 2004, a breakthrough by Demetrescu and Italiano [DI04] gave an
algorithm with $\widetilde{O}(n^{2})$ amortized update time per _vertex_
insertion/deletion using $\widetilde{O}(n^{3})$ space. Thorup [Tho04]
simplified their approach, shaved some logarithmic factors, and extended it to
handle negative cycles. Based on his approach, he developed the first fully
dynamic algorithm with a better _worst-case_ update time for vertex
insertion/deletions than recomputation from scratch with
$\widetilde{O}(n^{2+3/4})$ time per update, using a space super-cubic in $n$.
In 2017, Abraham, Chechik and Krinninger [ACK17] improved the space to
$O(n^{3})$ and designed a randomized algorithm with $\widetilde{O}(n^{2+2/3})$
worst-case update time per vertex update against an adaptive adversary. They
introduced a framework that has been used in all subsequent algorithms, which
itself uses some ideas from [Tho05]. The current state-of-the-art algorithms
are by Gutenberg and Wulff-Nilsen in 2020 [GWN20b]. They achieved
$\widetilde{O}(n^{2+4/7})$ deterministic update time but failed to improve the
randomized update time and instead only managed to improve space usage to
$\widetilde{O}(n^{2})$. Interestingly, their algorithm is a Las Vegas
algorithm while both our algorithm and Abraham, Chechik and Krinninger’s
algorithm are Monte Carlo algorithms333The difference between Monte Carlo
algorithms and Las Vegas algorithms is that although both types of algorithms
may have randomized running times, the former may be incorrect with a small
probability while the latter are always correct.. For deterministic
algorithms, Chechik and Zhang recently proposed a deterministic algorithm that
runs in $\widetilde{O}(n^{2+41/61})$ time [CZ]. The history of the fully
dynamic APSP problem is further summarized in Table 1.

Time | Space | VU | WC | Type | $\textrm{C}^{-}$ | Authors | Year
---|---|---|---|---|---|---|---
$\widetilde{O}(n^{2.5}\sqrt{W})$ | $\widetilde{O}(n^{3})$ | N | N | Det | N | King [Kin99] | 1999
$\widetilde{O}(n^{2.5}\sqrt{W})$ | $\widetilde{O}(n\sqrt{W})$ | N | N | Det | N | King and Thorup [KT01] | 2001
$\widetilde{O}(n^{2.5}\sqrt{S})$ | $\widetilde{O}(n\sqrt{S})$ | N | N | Det | Y | Demetrescu and Italiano [DI02] | 2002
$\widetilde{O}(n^{2})$ | $\widetilde{O}(n^{3})$ | Y | N | Det | N | Demetrescu and Italiano [DI04] | 2004
$\widetilde{O}(n^{2})$ | $\widetilde{O}(n^{3})$ | Y | N | Det | Y | Thorup [Tho04] | 2004
$\widetilde{O}(n^{2+3/4})$ | $\omega(n^{3})$ | Y | Y | Det | N | Thorup [Tho05] | 2005
$\widetilde{O}(n^{2+3/4})$ | $O(n^{3})$ | Y | Y | Det | N | Abraham, Chechik and Krinninger [ACK17] | 2017
$\widetilde{O}(n^{2+2/3})$ | $O(n^{3})$ | Y | Y | MC | N | Abraham, Chechik and Krinninger [ACK17] | 2017
$\widetilde{O}(n^{2+5/7})$ | $\widetilde{O}(n^{3})$ | Y | Y | Det | Y | Gutenberg and Wulff-Nilsen [GWN20b] | 2020
$\widetilde{O}(n^{2+2/3})$ | $\widetilde{O}(n^{2})$ | Y | Y | LV | Y | Gutenberg and Wulff-Nilsen [GWN20b] | 2020
$\widetilde{O}(n^{2+41/61})$ | $\widetilde{O}(n^{3+5/61})$ | Y | Y | Det | Y | Chechik and Zhang [CZ] | 2023
$\widetilde{O}(n^{2.5})$ | $O(n^{2})$ | Y | Y | MC | N | This paper |
Table 1: Fully dynamic APSP algorithms, where “VU” stands for “vertex updates”
(as opposed to edge updates), “WC” stands for “worst-case” (as opposed to
amortized), “Det/MC/LV” stands for “deterministic/Las Vegas/Monte Carlo,” and
“$\textrm{C}^{-}$” stands for “(allow) negative cycles.”

Since Gutenberg and Wulff-Nilsen pointed out that the existence of such an
improvement has remained a fundamental open problem [GWN20b]. Moreover, it has
been observed by Abraham, Chechik and Krinninger that $\widetilde{O}(n^{2.5})$
seems to be a natural barrier for the worst-case update time [ACK17], and it
is a natural question whether there is an algorithm that meets this natural
barrier or there are impossibility results. Our result gives an algorithm that
meets this natural barrier while preserving the quadratic space usage.

##### Our Result.

Suppose that the graph does not contain a negative cycle at any time. Our main
result is a randomized algorithm with a running time that meets the natural
barrier of $\widetilde{O}(n^{2.5})$.

######  Theorem 1.1.

Let $G$ be an $n$-vertex edge-weighted directed graph undergoing vertex
insertions and deletions with no negative cycles at any time. There exists a
Monte-Carlo data structure that can maintain distances in $G$ between all
pairs of vertices in randomized worst-case update time
$\widetilde{O}(n^{2.5})$ with high probability444In this paper, the term “high
probability” implies a probability of at least $1-n^{-c}$ for any constant
$c>0$., using $\widetilde{O}(n^{2})$ space, against an adaptive adversary.

### Related Results

##### Partially Dynamic Algorithms.

In the partially dynamic model only one type of update is allowed. The
_incremental_ model is restricted to insertions and the _decremental_ model is
restricted to deletions. The amortized update time bounds for partially
dynamic algorithms often depend on the size of the graph rather than the
number of updates. Thus it is often convenient to report the _total update
time_ , which is the sum of the individual update times. In the incremental
setting, the earliest partially dynamic algorithm was the well-known Floyd-
Warshall Algorithm [Flo62, War62] from as early as 1962 that can be easily
extended to handle vertex insertion for $O(n^{2})$ time per update, which
means $O(n^{3})$ total update time for $n$-node graphs. Apart from this, there
is an algorithm by Ausiello, Italiano, Spaccamela and Nanni [AISN90] for edge
insertions that has a total update time of $O(n^{3}W\log{(nW)})$ where $W$ is
the largest edge weight. In the decremental setting, the fastest algorithm for
vertex deletions runs in $O(n^{3}\log n)$ total update time [DI04], while the
fastest algorithm for edge deletions run in randomized $O(n^{3}\log^{2}n)$
total update time for unweighted graphs [BHS03], and $O(n^{3}S\log^{3}n)$
total update time for weighted graphs [DI06] if edge weights are chosen from a
set of size $S$.

##### Approximation Algorithms.

The problem of dynamic All-Pairs Shortest Paths in the approximate setting has
been studied in various dynamic graph settings [BHS02, DI04, RZ04b, Ber09,
RZ04a, AC13, Ber16, HKN16, Che18, vdBN19, KL19, GWN20a, KL, Chu21, EFHGWN21,
BGS22]. In the setting of $(1+\varepsilon)$-approximate shortest paths on an
$n$-vertex, $m$-edge graph, although many algorithms achieve amortized update
time $\widetilde{O}(m/\varepsilon)$, for the worst-case running time, the only
of these algorithms that give a better guarantee than the trivial
$\widetilde{O}(mn/\varepsilon)$ bound is the one in [vdBN19] with a running
time of $\widetilde{O}(n^{2.045}/\varepsilon^{2})$ on digraphs with positive
edge weights based on fast matrix multiplication. There is also a work
studying the related problem of fully dynamic minimum weight cycle under
vertex updates in the approximate settings [Kar21].

##### Special Graphs.

There are also many results on fully dynamic algorithms for planar [KS98,
HKRS97, FR06, ACG12] and undirected graphs [RZ04a, Ber09, Ber16, ACT14, HKN16,
Chu21].

##  2 Techniques Overview

##### Hop-Dominant Paths.

The bottleneck in both Abraha, Chechik and Krinninger’s data structure and
Gutenberg and Wilff-Nilsen’s data structure is the following _hop-restricted
shortest path_ problem: given a source vertex $s$ in the graph and a _hop
limit_ $h$, we want to know for each other vertex $t$ the shortest $s$-$t$
path that visits at most $h$ edges (called $h$-hop shortest paths). Their idea
is that by concatenating a small amount of these hop-restricted paths, we can
recover all-pairs shortest paths subject to vertex deletions. However, for the
problem of obtaining these paths, we still fail to do better than the classic
solution using the Bellman-Ford algorithm in $O(n^{2}h)$ time. In our
approach, we go around this inefficiency by only computing _hop-dominant
paths_ , which are $h$-hop shortest paths that are also $2h$-hop shortest. Our
core idea is that we only need to concatenate a small amount of hop-dominant
paths to recover all-pairs shortest paths. Fortunately, it turns out that hop-
dominant paths can be computed in $O(n^{2})$ time, which speeds up our
computation.

However, simply replacing the hop-restricted shortest paths with hop-dominant
paths does not readily give us an improvement. Firstly, such replacement will
break an important sequential sub-routine. Secondly, although we can show that
there is a way to only concatenate a small amount of hop-dominant paths to
recover all-pairs shortest paths, it is not obvious how such a way can be
found efficiently.

##### Randomization on a Sequential Sub-Routine.

The most crucial ingredient that enabled Gutenberg and Wilff-Nilsen’s
improvement over Abraha, Chechik and Krinninger’s is a new way of designing
the sequential sub-routine mentioned above. This sub-routine computes hop-
restricted paths from each vertex in some order and modifies the graph on the
fly based on these paths. Although with their innovation, Gutenberg and Wilff-
Nilsen managed to make the sub-routine more robust and space efficient, they
failed to improve its running time. It turns out that simply replacing hop-
restricted paths with hop-dominant paths in this sub-routine will not work.
The technique we employ to speed up this sub-routine is by applying
randomization. Instead of going through the vertices one by one, we randomly
select some vertices, compute only the single source hop-restricted paths from
these vertices, and magnify the modification on the graph so that it
approximates the deterministic procedure. Our argument here is that even if we
skip the majority of the vertices, our randomized sub-routine is still a good
approximation of the original deterministic sub-routine.

##### Construction for Efficient Concatenations.

We prove that there is a protocol to concatenate a small amount of hop-
dominant paths to recover all-pairs shortest paths by constructing it from
Gutenberg and Wilff-Nilsen’s protocol to concatenate a small amount of hop-
restricted paths to recover all-pairs shortest paths. This means that we can
concatenate hop-dominant paths efficiently by using hop-restricted paths as an
oracle. However, since hop-restricted paths are not as easily computed as hop-
dominant paths, we can not afford to obtain this oracle. In order to get rid
of the requirement on this oracle, we categorize the recovered paths into two
types. The first type is those that are concatenations of exactly two hop-
dominant paths, and the second type is those that are concatenations of more
than two hop-dominant paths. We deal with the first type using a copy of
Gutenberg and Wiff-Nilsen’s data structure with some modification, and the
second type with a Dijkstra-like sub-routine.

##  3 Preliminaries

In this paper, we will largely inherit the notations used in [GWN20b]. We
denote by $G=\langle\mathrm{V},E\rangle$ the input digraph where the edges are
associated with a weight function $w:\mathrm{E}\rightarrow\mathbb{R}$. For the
input graph $G$, we use $n$ to denote $\left\lvert\mathrm{V}\right\rvert$ and
$m$ to denote $\left\lvert\mathrm{E}\right\rvert$. For a subset
$\mathrm{V}^{\prime}\subset\mathrm{V}$, we denote by $G[\mathrm{V}^{\prime}]$
the induced subgraph of $\mathrm{V}^{\prime}$. For $D\subset\mathrm{V}$ we
write $G\backslash D$ as a shorthand for $G[\mathrm{V}\backslash D]$. We let
$\overleftarrow{G}$ be the digraph identical to $G$ but with all edge
directions reversed. For two vertices $(u,v)\in\mathrm{V}^{2}$, let $\langle
u,v\rangle$ denote the edge from $u$ to $v$, and let $w(u,v)$ denote the
weight of $\langle u,v\rangle$.

For a path $p$ from $s$ to $t$ containing $h$ edges and $h+1$ vertices, we let
$p[i]$ be the $i$-th vertex on $p$ (0-based) where $p[0]=s$ and $p[h]=t$. We
can describe $p$ by $\langle p[0],p[1],\cdots,p[h]\rangle$. For $0\leq l\leq
r\leq h$ we write $p[l,r]$ to denote the segment of $p$ from the $l$-th to the
$r$-th vertex. $h$ is called the _hop_ of $p$ and is denoted by $\left\lvert
p\right\rvert$. The _weight_ or _length_ of $p$, $w(p)$, is defined as the sum
of the weights of the edges on the $p$. We say a path is shorter or longer
than another by comparing the lengths (not the hops) between the two paths. We
use $\perp$ to denote an empty path, whose weight is defined to be $\infty$.
Given two paths $p_{1}$ and $p_{2}$ such that $p_{1}[\left\lvert
p_{1}\right\rvert]=p_{2}[0]$, we denote by $p_{1}\circ p_{2}$ the
_concatenated path_ $\langle p_{1}[0],p_{1}[1],\cdots,p_{1}[\left\lvert
p_{1}\right\rvert]=p_{2}[0],p_{2}[1],\cdots,p_{2}[\left\lvert
p_{2}\right\rvert]\rangle$. Specifically, for any path $p$ we define $p\
\circ\perp=\perp\circ\ p=\perp$. We use $v\in p$ to denote when a vertex $v$
is on the path, or equivalently, $v=p[k]$ for some $k\in[0,h]$, and we let
$p[<v]$ be the segment of the path before $v$, or equivalently the path
$p[0,k]$, and $p[>v]$ be the segment after $v$, or equivalently $p[k,h]$. We
let $\overleftarrow{p}$ be the reversed path $\langle
p[h],p[h-1],\cdots,p[0]\rangle$ in $\overleftarrow{G}$.

For a path $p$ from $s$ to $t$. We say $p$ is the _shortest path_ in $G$ if
the weight of $p$ is minimized over all $s$-$t$ paths. $p$ is an $h$_-hop-
restricted path_ if its hop does not exceed $h$. $p$ is the $h$_-hop-shortest
path_ if the weight of $p$ is the minimized over all $h$-hop-restricted
$s$-$t$ paths. For a set of vertices $C$, we say a path is through $C$ if the
path visits at least one vertex in $C$.

##### Uniqueness of Shortest Paths.

In this paper we assume that for every $h$, the $h$-hop shortest paths between
a pair of vertices are unique. We shall describe how this is achieved in
Section 4.5.2.

### Ingredients

Given a hop limit $h$, the single source $h$-hop shortest paths can be
computed in $O(n^{2}h)$ time using the famous Bellman–Ford algorithm. We can
modify the algorithm so that it computes the shortest paths through a set of
centers:

######  Lemma 3.1.

Given a graph $G=\langle\mathrm{V},\mathrm{E}\rangle$ of $n$ vertices. Let
$C\subset\mathrm{V}$ be a set of centers. For a starting vertex $s$ and a hop
limit $h$, there is a procedure $\textsc{BellmanFordThroughCenter}(s,G,C,h)$
that computes for each destination $t$ the shortest among paths between $s$
and $t$ through $C$ with a hop at most $h$ in $\widetilde{O}(n^{2}h)$ time and
$\widetilde{O}(n^{2})$ space.

###### Proof.

In order to force paths to pass through a center in $C$, we split each vertex
$v$ into $(v,0)$ and $(v,1)$ where the second parameter is $1$ if and only if
we visited at least one vertex in $C$. We copy each edge from $u$ to $v$ into
two edges from $(u,0)$ to $(v,0)$ and $(u,1)$ to $(v,1)$, respectively. If
$v\in C$, we also add an edge from $(u,0)$ to $(v,1)$. We can simply run the
algorithm on this new graph to force the paths to pass through $C$. ∎

In Gutenberg and Wilff-Nilsen’s paper they introduced a data structure that
can store the output paths in $\widetilde{O}(n)$ space, but this will be
unnecessary for our algorithm.

We will use a well-known fact that good hitting sets can be obtained by random
sampling. This technique was first used in the context of shortest paths by
Ullman and Yannakakis [UY91]. The fact can be formalized in the following
lemma.

######  Lemma 3.2 (See [UY91]).

Let $N_{1},N_{2},\cdots,N_{n}\subset U$ be a collection of subsets of $U$,
with $u=\left\lvert U\right\rvert$ and $\left\lvert N_{i}\right\rvert\geq s$
for all $i\in[1,n]$. For any constant $a\geq 1$, let $A$ be a subset of $U$
that was obtained by choosing each element of $U$ independently with
probability $p=\min(x/s,1)$ where $x=a\ln{(un)}+1$. Then with a probability of
at least $1-1/n^{a}$, the following two properties hold:

  * •

$N_{i}\cap A\neq\emptyset$ for all $i$;

  * •

$\left\lvert A\right\rvert\leq 3xu/s=O(u\ln{(un)}/s)=\widetilde{O}(u/s)$.

We will also use the following lemma that efficiently computes the shortest
paths that have a hop no less than a threshold $h$.

######  Lemma 3.3 (See [ACK17]).

Given a graph $G=\langle\mathrm{V},\mathrm{E}\rangle$ of $n$ vertices with
non-negative edge weights, for any $h>0$, there exists a randomized procedure
$\textsc{RandGetShortestPaths}(G,h)$ running in $\widetilde{O}(n^{3}/h)$ time
using $\widetilde{O}(n)$ space that computes a distance matrix $A=a_{s,t}$
such that for every $(s,t)\in\mathrm{V}^{2}$:

  * •

If we let ${\pi}_{s,t}$ be the shortest $s$-$t$ path, then $w({\pi}_{s,t})\leq
A_{s,t}$.

  * •

If we let ${\Pi}_{s,t}$ be the shortest $s$-$t$ path with a hop of at least
$h$, then $A_{s,t}\leq w({\Pi}_{s,t})$ with high probability.

To give an intuition for Lemma 3.3, observe that from Lemma 3.2 we can sample
a hitting set of size $\widetilde{O}(n/h)$ for all shortest paths with a hop
of at least $h$. We can compute the shortest paths to and from vertices in
this set by running Dijkstra’s algorithm from each vertex in this set in $G$
as well as $\overleftarrow{G}$, and then combine the answers trivially. It is
easy to see that the computed distance matrix satisfies the stated conditions.

Finally, we will also use an online version of the Chernoff bound:

######  Lemma 3.4 (Thereorem 2.2 of [CQ18]).

Let $X_{1},\cdots X_{n},Y_{1},\cdots\in[0,1]$ be random variables and let
$\varepsilon\in[0,1/2)$ be a sufficiently small constant. If
$\mathbf{E}[X_{i}\mid X_{1},\cdots X_{i-1},Y_{1}\cdots Y_{i}]\geq Y_{i}$ for
each $i$, then for any $\delta>0$,

$\operatorname*{\mathbf{Pr}}[\sum\limits_{i=1}^{n}{X_{i}}\leq(1-\varepsilon)\sum\limits_{i=1}^{n}{Y_{i}}-\delta]\leq(1-\varepsilon)^{\delta}.$

###  3.1 Path Operations

In this paper, we assume the following operations on paths are possible:

  * •

Given a path $p$, we can retrieve the list of vertices
$\\{p[0],p[1],p[2],\cdots,p[\left\lvert p\right\rvert]\\}$ in $O(\left\lvert
p\right\rvert)$ time.

  * •

Given two paths $u$ and $v$, we can concatenate $u$ and $v$ in $O(1)$ time.

  * •

Both $w(p)$ and $\left\lvert p\right\rvert$ can be found in $O(1)$ time.

We shall discuss how all these path operations are possible within
$\widetilde{O}(n^{2})$ space in Section 4.5.1

##  4 Main Algorithm

###  4.1 A Framework Based on Gutenberg and Wulff-Nilsen’s Approach

Gutenberg and Wulff-Nilsen’s approach was based on a fundamental framework
that reduces the fully dynamic problem into a decremental one, which starts
from the following reduction:

######  Lemma 4.1 (See [HK01, Tho05, ACK17, GWN20b]).

Given we have a data structure on $G$ that supports a batch deletion of up to
$\Delta$ vertices $D\subset\mathrm{V}$ from $G$ such that the data structure
computes for each $(s,t)\in(\mathrm{V}\backslash D)^{2}$ the shortest path
${\pi}_{s,t}$ in $G\backslash D$, if the rebuild time is $t_{\textrm{pre}}$
and the batch deletion worst-case time is $t_{\textrm{del}}$ and the space
usage is $M$, there exists a fully dynamic APSP algorithm with
$O(t_{\textrm{pre}}/\Delta+t_{\textrm{del}}+\Delta n^{2})$ worst-case update
time and $O(M)$ space.

The framework is based on the following Lemma:

######  Lemma 4.2 (See Floyd-Warshall Algorithm [Flo62, War62]).

Given a graph $G/C$, where $C\subset V$ of size $\Delta$, and given its
distance matrix $D$ in $G\backslash C$. There is an algorithm that computes
the distance matrix of $G$ in $O(\Delta n^{2})$ time and $O(n^{2})$ space.

To give an intuition for Lemma 4.1, we let $D$ be the set of vertex deletions
accumulated from the updates, and $I$ be the set of vertex insertions. We use
the data structure to compute the shortest paths in $G\backslash D$ with time
$t_{\textrm{del}}$ and insert $I$ back to the graph in $O(In^{2})$ time using
Lemma 4.2. We rebuild the data structure whenever $\left\lvert
D\right\rvert+\left\lvert I\right\rvert\geq\Delta$ (after at least $\Delta$
updates) and clear $D$ and $I$. Using standard deamortization techniques, we
can split the rebuild time into small chunks that are processed at individual
updates. This guarantees a worst-case running time of
$O(t_{\textrm{pre}}/\Delta)$ per update.

The framework by Gutenberg and Wilff-Nilsen in [GWN20b] is an extension of the
fundamental framework. We create $L=O(\log n)$ layers indexed increasingly
from bottom to top. The next layer of layer $i$ is layer $i-1$ and the
previous layer of layer $i$ is layer $i+1$. For each layer $i$, a subset of
center vertices $C_{i}$ is given as a parameter. For the top layer $L$,
$C_{L}=\mathrm{V}$. For each layer $i$, we employ a data structure $S_{i}$
that supports a batch deletion of up to $2^{i}$ vertices $D_{i}\subset V$.
Each layer $i$ is rebuilt exactly per $2^{i}$ updates, and the set $D_{i}$ is
the set of vertices deleted since layer $i$ is last rebuilt, so $\left\lvert
D_{i}\right\rvert\leq 2^{i}$ and the batch deletion is always within its
limitation. All layers are rebuilt initially. Therefore, every time a layer is
rebuilt, all layers below it are rebuilt. When layers are rebuilt, their
corresponding rebuild steps are invoked from top to bottom (i.e. in decreasing
order of indices). The data structure for layer $i$ computes for each
$(s,t)\in(V\backslash D_{i})^{2}$ some surviving $s$-$t$ path that is at most
as long as the shortest $s$-$t$ path in $G\backslash(D_{i}\cup C_{i-1})$
through $C_{i}$ (Suppose $C_{-1}=\emptyset$). From a telescoping argument, if
we combine the results from layer $i$ to layer $0$, we find the shortest paths
through $C_{i}$. Since $C_{L}=\mathrm{V}$, combining all layers give us the
globally shortest paths.

The framework ensures that in order to get a data structure for the fully
dynamic APSP problem, we only need to design those layers for the decremental
problem. In [GWN20b], they implicitly showed the following lemma:

######  Lemma 4.3.

If for layer $i$, the rebuild step runs in $\widetilde{O}(T2^{i})$ time, the
batch deletion step runs in $\widetilde{O}(T)$ time, and either step uses
$\widetilde{O}(M)$ space, and the number of layers $L$ is such that $2^{L}$ is
at most $\widetilde{O}(T/n^{2})$, then we have a data structure for full-
dynamic APSP under vertex operations with a worst-case update time of
$\widetilde{O}(T)$ and a space usage of $\widetilde{O}(M)$

To give an intuition for Lemma 4.3, first note that since layer $i$ is rebuilt
every $2^{i}$ updates, we can apply the deamortization technique to each layer
to make their worst-case running time $\widetilde{O}(T)$ per layer. Since
there are only $\widetilde{O}(1)$ layers, this gives us a worst-case running
time of $\widetilde{O}(T)$ for the incremental case. To handle an update, for
each layer, we let $D_{i}$ be the set of vertices deleted since the last time
layer $i$ was rebuilt, and call the batch deletion procedures. Since there are
$\widetilde{O}(1)$ layers and the batch deletion procedure takes
$\widetilde{O}(T)$ time for each layer, the total time for batch deletion is
$\widetilde{O}(T)$. To handle insertions, after each update, we insert the
vertices from the at most $2^{L}$ insertions since the last time the entire
data structure was rebuilt using Lemma 4.2, in
$O(2^{L}n^{2})=\widetilde{O}(T)$ time. The space usage is $\widetilde{O}(M)$
since no extra space overhead is introduced.

In the previous algorithm by Gutenberg and Wilff-Nilsen from [GWN20b], the
rebuild step for layer $i$ runs in $\widetilde{O}(n^{8/3}\times 2^{i})$ time,
the batch deletion step runs in $\widetilde{O}(n^{8/3})$ time, either step
uses $\widetilde{O}(n^{2})$ space and the number of layer $L$ is such that
$2^{L}=\widetilde{O}(n^{2/3})$555In their paper the data structure only
contains the top $O(n^{1/3})$ layers but including the other layers doesn’t
affect the overall running time up to a logarithmic factor.. By applying Lemma
4.3 this gives a running time of $\widetilde{O}(n^{2+2/3})$ with a space usage
of $\widetilde{O}(n^{2})$.

Our final algorithm will be such that:

  * •

The rebuild step runs in $\widetilde{O}(n^{2.5}\times 2^{i})$ time,

  * •

The batch deletion step runs in $\widetilde{O}(n^{2.5})$ time,

  * •

Either step uses $\widetilde{O}(n^{2})$ space, and

  * •

$2^{L}=\widetilde{O}(n^{1/2})$.

By applying Lemma 4.3, we get a running time of $\widetilde{O}(n^{2.5})$ with
a space usage of $\widetilde{O}(n^{2})$, proving Theorem 1.1.

To introduce our data structure, we will first introduce our basic data
structure based on Gutenberg and Wilff-Nilsen’s data structure with a
lackluster rebuild time of $\widetilde{O}(n^{3.5})$ while achieving the goal
of a batch deletion time of $\widetilde{O}(n^{2.5})$ and an $L$ where
$2^{L}=\widetilde{O}(n^{1/2})$.

##### Enforcing Non-Negative Edge Weights.

Assuming that the graph contains no negative cycles, there is a famous
“Johnson transformation”[Joh77] that converts a graph with negative edge
weights into a graph with non-negative edge weights. It works by using a
_potential function_ $p:\mathrm{V}\rightarrow\mathbb{R}$ such that for every
edge $u,v\in\mathrm{E}$ with weight $w(u,v)$, the modified weight
$w^{\prime}(u,v)=w(u,v)+p(u)-p(v)\geq 0$. It is well-known that the shortest
paths are preserved after modifying the weights in this fashion. Using this
transformation, in [ACK17] they introduce a technique that reduces negative
edge weights to non-negative edge weights in the fully-dynamic case for
algorithms under this framework. Observe that if we add an additional node $q$
to the graph with an edge of weight $0$ to every node in the original graph,
then a valid potential function can be obtained by setting $p(u)$ to be the
shortest distance from $q$ to $u$. Importantly, this potential function
remains valid under vertex deletion. We can therefore run the Bellman-Ford
algorithm from $q$ in $O(nm)=O(n^{3})$ time during the rebuild algorithm in
the top layer to obtain a valid potential function that remains valid
throughout the upcoming updates. This does not affect the overall rebuild time
of $\widetilde{O}(n^{3})$ for the top layer. One can refer to Section 4.1 of
[ACK17] for a more details description of such reduction. From now on, we will
assume that our graph does not contain negative edge weights at any time.

###  4.2 The Basic Algorithm

This section will be an introduction of the framework used in Gutenberg and
Wilff-Nilsen’s algorithm using slightly different approaches. Most
importantly, we decide to merge the update procedure (the Delete step in
[GWN20b]) from individual layers into a single update procedure that
integrates the results from all the layers for convenience in the later parts
of our algorithm.

Unless otherwise defined, let $G$ be the graph when the sub-routine in context
is invoked, and for $i\in[0,L]$, we let $G_{i}$ be the graph when the rebuild
algorithm layer $i$ was most recently invoked (thus $G=G_{i}\backslash
D_{i}$). When a graph is not explicitly stated in the context, assume the
graph is $G$.

####  4.2.1 Basic Rebuild Algorithm

Recall that on layer $i$, we need to compute paths passing through a set of
centers $C_{i}$ subject to batch deletion of up to $2^{i}$ vertices. To do
this, we pre-compute some shortest paths through $C_{i}$ in the rebuild
procedure so that to deal with batch deletions, we can recover affected paths
by concatenating only a small amount of surviving paths. To achieve this,
Gutenberg and Wilff-Nilsen designed a new way to use congestion. The
congestion incurred by a path on a vertex is proportional to the running time
cost we later pay when this path needs to be recovered. Hence the total
congestion on a vertex is the running time cost that we will pay if this
vertex is deleted. We define parameters $h_{j}=(3/2)^{j}$ for $j\in[0,i_{h}]$,
where $i_{h}=\left\lceil\log_{3/2}{n^{0.5}}\right\rceil$. We let
$H=h_{i_{h}}=\Theta(n^{0.5})$. For each $j\in[0,i_{h}]$, we compute the
$h_{j}$-hop shortest paths through $C_{i}$ and add up the congestion
contributions. The core idea in the rebuild procedure is that if a vertex is
too congested, we delegate the computation of paths passing through it to the
next layer by adding it to $C_{i-1}$. To achieve this, any vertex with
congestion more than a threshold is labeled congested and removed from the
graph, but we do not replace the already computed paths that contain this
vertex. We introduce this procedure in Algorithm 1 with a much slower
implementation than the one introduced in their original paper for later
convenience. For the bottom-most layer $0$, there is no rebuild step, and
batch deletion step can be done by a simple recomputation in
$\widetilde{O}(n^{2}C_{0})$ time666Here since we assume the edge weights are
non-negative, we can simply compute the shortest paths from and to each center
by running Dijkstra’s algorithm in $G$ and $\overleftarrow{G}$ reversed and
combine the answers..

Algorithm 1 Basic Rebuild Algorithm

1:procedure BasicRebuild($i,C_{i}$)

2: $O_{i}\leftarrow\emptyset$

3: Set threshold ${\tau}_{i}\leftarrow n^{2.5}/2^{i}$

4: for $j\in[0,i_{h}]$ do

5: Initialize $\textsc{Congestion}_{i}[j,v]\leftarrow 0$ for all
$v\in\mathrm{V}$

6: for $k\in[1,\left\lvert\mathrm{V}\right\rvert]$ do

7: $s=\mathrm{V}[k]$

8: $\pi_{i}[s,*,j]\leftarrow\textsc{BellmanFordThroughCenter}(s,G\backslash
O_{i},C_{i},h_{j})$

9: for $t\in V,u\in\pi_{i}[s,t,j]$ do

10:
$\textsc{Congestion}_{i}[j,u]\leftarrow\textsc{Congestion}_{i}[j,u]+n/h_{j}$

11: end for

12: $O_{i}\leftarrow
O_{i}\cup\\{v\in\mathrm{V}\mid\textsc{Congestion}_{i}[j,v]>{\tau}_{i}\\}$

13: end for

14: end for

15: $C_{i-1}\leftarrow O_{i}$

16:end procedure

For now, the procedure introduced has a lackluster running time of
$\widetilde{O}(n^{3}H)$. In [GWN20b] a running time of
$\widetilde{O}(\left\lvert C_{i}\right\rvert n^{2}H)$ was achieved using
randomization. We now introduce the core lemma for the correctness of this
rebuilding procedure.

######  Lemma 4.4.

Algorithm 1 preserves the following invariants:

  1. 1.

$\forall(j,v)\in[0,i_{h}]\times\mathrm{V}:\textsc{Congestion}_{i}[j,v]\leq
2{\tau}_{i}$,

  2. 2.

$\sum_{j\in[0,i_{h}],v\in\mathrm{V}}{\textsc{Congestion}_{i}[j,v]}=O(n^{3}\log
n)$,

  3. 3.

$\left\lvert O_{i}\right\rvert=O(n^{3}\log
n/{\tau}_{i})=\widetilde{O}(n^{0.5}2^{i})$,

  4. 4.

$\pi_{i}[s,t,j]$ has a hop of at most $h_{j}$ and is not longer than the
$h_{j}$-hop-shortest path between $s$ and $t$ in $G\backslash O_{i}$.

###### Proof.

To see (1), observe that a single iteration of the while loop does not
contribute more than $n^{2}<{\tau}_{i}$ to the congestion on a single vertex,
since a vertex is removed from the path when its congestion exceeds
$\tau_{i}$, the final congestion does not exceed
$\tau_{i}+\tau_{i}=2\tau_{i}$. To see (2), note that a path contributes
exactly $n$ to the total congestion and there are $O(n^{2}\log n)$ paths.
Therefore the total congestion does not exceed $n\times O(n^{2}\log
n)=O(n^{3}\log n)$. To see (3), note that a vertex is added to $O_{i}$ only if
its congestion value exceeds ${\tau}_{i}$, since from (2) the total congestion
is $O(n^{3}\log n)$, the claim follows. (4) is due to the fact that the graph
$G\backslash O_{i}$ is decremental since we can only exclude more vertices
from $G\backslash O_{i}$. ∎

We define the total congestion on a vertex $v$ on layer $i$ to be
$\textsc{Congestion}_{i}(v)$. By definition,
$\textsc{Congestion}_{i}(v)=\sum_{0\leq j\leq
i_{h}}{\textsc{Congestion}_{i}[j,v]}$. Since $i_{h}=O(\log n)$, we have
$\textsc{Congestion}_{i}(v)=\widetilde{O}(\tau_{i})$.

####  4.2.2 Basic Update Algorithm

Although in the original framework from [GWN20b], there is a separate batch
deletion procedure for each layer. Our data structure uses a global update
procedure that handles patch deletions on all the layers by polling the
information on each layer. For the update procedure, at the start of the
procedure, for each tuple $(s,v,t,j)\in\mathrm{V}^{3}\times[0,i_{h}]$ we
sample a random 0-1 variable $X[u,v,w,j]$ which equals $1$ with probability
$\frac{100\log_{2}{n}}{h_{j}}=\widetilde{O}(1/h_{j})$. The variables are fixed
throughout the update. We will show in Section 4.5.1 how to implement these
random variables space-efficiently. To do the update, we first check the
effects of batch deletion on each layer. For layer $i$, if the removal of
$D_{i}$ invalidates a computed path, we mark the path as a path that “needs
recovery.” We look at the remaining paths on each layer. We let
$\pi^{\prime}[s,t,j]$ be the shortest $\pi_{i}[s,t,j]$ that remains for layer
$i\in[0,L]$. We use these paths to recover the missing paths by using the
random variables above to determine a hitting set777In [GWN20b] they did not
use randomness in this part but constructed hitting sets deterministically..
The update procedure is described in Algorithm 2.

Algorithm 2 Basic Update Procedure

1:function Recover($\pi_{o},s,t,j$) $\triangleright$ Recover
${\pi_{o}}[s,t,j]$

2: $\eta\leftarrow\\{v\mid X[s,v,t,j]=1\\}\cup\\{s,t\\}$ $\triangleright$
Construct a hitting set.

3:
$x^{\prime}\leftarrow\textrm{argmin}_{x\in\eta}{w({\pi_{o}}[s,x,j-1]\circ{\pi_{o}}[x,t,j-1])}$

4: return ${\pi_{o}}[s,x^{\prime},j-1]\circ{\pi_{o}}[x^{\prime},t,j-1]$

5:end function

6:function BasicUpdate $\triangleright$ Compute the distance matrix after the
update

7: $\pi^{\prime}\leftarrow\perp$

8: $\mathrm{NeedsRecovery}[*,*,*]\leftarrow\mathrm{FALSE}$

9: for $i\in[0,L]$ do

10: for $j\in[0,i_{h}]$ do

11: for $s,t\in\mathrm{V}$ do

12: if $\pi_{i}[s,t,j]\cap D_{i}=\emptyset$ then

13: if $w(\pi_{i}[s,t,j])<w({\pi^{\prime}}[s,t,j])$ then

14: ${\pi^{\prime}}[s,t,j]\leftarrow\pi_{i}[s,t,j]$

15: end if

16: else

17: $\mathrm{NeedsRecovery}[s,t,j]=\mathrm{TRUE}$

18: end if

19: end for

20: end for

21: end for

22: $\pi_{o}\leftarrow\textrm{a copy of }\pi^{\prime}$

23: for $j\in[0,i_{h}]$ do

24: for $s,t\in\mathrm{V}$ do

25: if $\mathrm{NeedsRecovery}[s,t,j]=\mathrm{TRUE}$ then

26: ${\pi_{o}}[s,t,j]\leftarrow\textsc{Recover}(\pi_{o},s,t,j)$

27: end if

28: end for

29: end for

30: $A=\textsc{RandGetShortestPaths}(G,H)$ $\triangleright$ From Lemma 3.3

31: for $s,t\in\mathrm{V}$ do

32: $A_{s,t}\leftarrow\min(A_{s,t},w({\pi_{o}}[s,t,i_{h}]))$

33: end for

34: return $A$

35:end function

For a triple $(s,t,j)\in\mathrm{V}^{2}\times[0,i_{h}]$, define the _recovery
cost_ $c[s,t,j]=n/h_{j}$. We first have the following lemma:

######  Lemma 4.5.

The total time spent running Line 26 is no more than the total recovery cost
of triples $(s,t,j)$ such that $\mathrm{NeedsRecovery}[s,t,j]=\mathrm{TRUE}$
(up to a logarithmic factor) with high probability.

###### Proof.

It is easy to see that the $\textsc{Recover}(\pi_{o},s,t,j)$ takes
$O(\left\lvert H\right\rvert)=\sum_{v}{X[s,v,t,j]}$ time. Note that
$X[u,v,w,j]$ equals $1$ with probability
$\frac{100\log_{2}{n}}{h_{j}}=\widetilde{O}(1/h_{j})$ and all random variables
are independent. We have $O(\left\lvert
H\right\rvert)=\sum_{v}{X[s,v,t,j]}=\widetilde{O}(c[s,t,j])$ with high
probability from the Chernoff bound888The multiplicative form of Chernoff
bound is as follows: Let $x_{1},x_{2},\cdots,x_{n}$ be $n$ independent random
variables taking values from $\\{0,1\\}$ and let $x=\sum_{i}{x_{i}}$, and
$\mu=E(x)$. Then, for any $\varepsilon>0$, we have
$Pr(x\geq(1+\varepsilon)\mu)\leq
e^{-\frac{\varepsilon^{2}\mu}{2+\varepsilon}})$ and
$Pr(x\leq(1-\varepsilon)\mu)\leq e^{-\frac{\varepsilon^{2}\mu}{2}})$..
Therefore, the total time spent running Line 26 is proportional to the total
recovery cost of triples $(s,t,j)$ such that
$\mathrm{NeedsRecovery}[s,t,j]=\mathrm{TRUE}$ with high probability. ∎

We now show the core argument used in Gutenberg and Wilff-Nilsen’s framework
in the following lemma:

######  Lemma 4.6.

With high probability, the total time spent running Line 26 is no more than
the total congestion on vertex $v$ (up to a logarithmic factor), which is
$\sum_{i}\sum_{v\in D_{i}}{\textsc{Congestion}_{i}(v)}$.

###### Proof.

The total recover cost of triples $(s,t,j)$ such that
$\mathrm{NeedsRecovery}[s,t,j]=\mathrm{TRUE}$ is no more than the total sum
over $i\in[0,L]$ of the recovery cost of triples $(s,t,j)$ such that
$\pi_{i}[s,t,j]\cap D_{i}\neq\emptyset$. From the rebuild algorithm we can see
that $\textsc{Congestion}_{i}(v)$ is equal to the total recovery cost of paths
through $v$. Therefore the total recovery cost of triples $(s,t,j)$ such that
$\mathrm{NeedsRecovery}[s,t,j]=\mathrm{TRUE}$ is no more than
$\sum_{i}\sum_{v\in D_{i}}{\textsc{Congestion}_{i}(v)}$. From Lemma 4.5, the
total time spent running Line 26 is $\widetilde{O}(\sum_{i}\sum_{v\in
D_{i}}{\textsc{Congestion}_{i}(v)})$ with high probability. ∎

######  Lemma 4.7.

Algorithm 2 runs in $\widetilde{O}(n^{2.5})$ time.

###### Proof.

From Lemma 4.6, the running time of the update procedure is

$\widetilde{O}(\sum_{u\in
D_{i}}{\textsc{Congestion}_{i}(u)})=\widetilde{O}(\left\lvert
D_{i}\right\rvert\times 4\tau_{i})=\widetilde{O}(\left\lvert
D_{i}\right\rvert\tau_{i})=\widetilde{O}(2^{i}\times
n^{2.5}/2^{i})=\widetilde{O}(n^{2.5}).$

Since $H=n^{0.5}$, from Lemma 3.3 the call to RandGetShortestPaths runs in
$\widetilde{O}(n^{2.5})$ time. Therefore, the procedure runs as desired in
$\widetilde{O}(n^{2.5})$ time. The line 12 can be done by simply retrieving
all the vertices on the paths, which takes
$\widetilde{O}(n^{2}H)=\widetilde{O}(n^{2.5})$ time. The rest of the procedure
can clearly be implemented in $\widetilde{O}(n^{2.5})$ time. ∎

The next three lemmas show the correctness of Algorithm 2.

######  Lemma 4.8.

If $\mathrm{NeedsRecovery}[s,t,j]=\mathrm{FALSE}$, then $\pi^{\prime}[s,t,j]$
is the $h_{j}$-hop shortest $s$-$t$ path. Moreover, if we constrain the for
loop on 9 to $i\in[i^{\prime},L]$ for some $i^{\prime}\in[0,L]$, then
$\pi^{\prime}[s,t,j]$ is not longer than the $h_{j}$-hop shortest $s$-$t$ path
through $C_{i^{\prime}}$ in the current graph $G$.

###### Proof.

From invariant (4) in Lemma 4.4, for every $i\in[0,L]$, $\pi_{i}[s,t,j]$ is
not longer than the $h_{j}$ shortest $s$-$t$ path through $C_{i}$ in
$G_{i}\backslash O_{i}$. Since $G_{i}\backslash O_{i}\supset G_{i}\backslash
C_{i-1}\supset G\backslash C_{i-1}$, $\pi_{i}[s,t,j]$ is not longer than the
$h_{j}$ shortest $s$-$t$ path through $C_{i}$ in $G\backslash C_{i-1}$. Since
$\mathrm{NeedsRecovery}[s,t,j]=\mathrm{FALSE}$, every $\pi_{i}[s,t,j]$ is
present. Therefore from a telescoping argument, $\pi^{\prime}[s,t,j]$ is not
longer than the $h_{j}$-hop shortest $s$-$t$ path. Since $\pi^{\prime}[s,t,j]$
has a hop at most $h_{j}$, $\pi^{\prime}[s,t,j]$ is the $h_{j}$-hop shortest
$s$-$t$ path.

The proof of the second part of the lemma is similar. ∎

######  Lemma 4.9.

Given $j\in[0,i_{h}]$, suppose for all pairs $(u,v)\in\mathrm{V}^{2}$,
$\pi_{o}[u,v,j-1]$ is not longer than the $h_{j-1}$-hop-shortest $u$-$v$ path.
Then for a fixed $(s,t)\in\mathrm{V}^{2}$, $\pi_{o}[s,t,j]$ is not longer than
the $h_{j}$-hop shortest path between $s$ and $t$ with probability at least
$1-1/n^{10}$.

###### Proof.

Let $p$ be the $h_{j}$-hop shortest path between $s$ and $t$. It suffices to
show that $w(\pi_{o}[s,t,j])\leq w(p)$ with probability at least $1-1/n^{10}$.

If $\mathrm{NeedsRecovery}[s,t,j]=\mathrm{FALSE}$, then
$w(\pi_{o}[s,t,j])=w(\pi^{\prime}[s,t,j])\leq w(p)$ from Lemma 4.8.

Suppose $\mathrm{NeedsRecovery}[s,t,j]=\mathrm{TRUE}$. Let the $h_{j}$-hop-
shortest $s$-$t$ path be $p$. If $p$ has a hop more than $h_{j-1}$, then for
any vertex $u$ on $p[\left\lvert p\right\rvert-h_{j-1},h_{j-1}]$, both
$\left\lvert p[<u]\right\rvert$ and $\left\lvert p[>u]\right\rvert$ are no
more than $h_{j-1}$. Therefore by the assumption in the lemma,
$w({\pi_{o}}[s,u,i-1])\leq w(p[<u])$ and $w({\pi_{o}}[u,t,i-1])\leq w(p[>u])$.
which means that there are at least $h_{j-1}-(h_{j}-h_{j-1})\geq 1/3h_{j}$
candidates $u$ such that $w({\pi_{o}}[s,u,i-1]\circ{\pi_{o}}[u,t,i-1])\leq
w(p)$. From the Chernoff bound, with probability at least $1-1/n^{10}$, at
least one such candidate $u$ is such that $X[s,u,t,j]=1$, which will enforce
that $w(\pi_{o}[s,t,j])\leq w(p)$. For the case when $p$ has a hop of at most
$h_{j-1}$, since both $s$ and $t$ are included in the hitting set $\eta$ on
Line 2, and from the assumption in the lemma $w(\pi_{o}[s,t,j-1])\leq w(p)$,
setting $x$ to be either $s$ or $t$ on Line 4 enforces that
$w(\pi_{o}[s,t,j])\leq w(p)$ ∎

######  Lemma 4.10.

At the end of Algorithm 2, with a probability of at least
$1-1/\Omega(n^{7.99})$, for all $(s,t,j)\in\mathrm{V}^{2}\times[0,i_{h}]$,
$\pi_{o}[s,t,j]$ is the $h_{j}$-hop-shortest path.

###### Proof.

We do induction on $j$ in increasing order and apply Lemma 4.9. By union bound
over all $\widetilde{O}(n^{2})$ recoveries throughout the update, our
procedure is correct with probability at least $1-1/\Omega(n^{7.99})$. ∎

######  Lemma 4.11.

At the end of Algorithm 2, with high probability, for every
$(s,t)\in\mathrm{V}^{2}$, $A_{s,t}$ is the length of the shortest $s$-$t$
path.

###### Proof.

By Lemma 4.10, with high probability, for every $(s,t)\in\mathrm{V}^{2}$,
$\pi_{o}[s,t,i_{h}]$ is not longer than the $H$-hop shortest $s$-$t$ path. It
is easy to see from our procedure that $\pi_{o}[s,t,i_{h}]$ is a valid $s$-$t$
path in $G$, and therefore is not shorter than the shortest $s$-$t$ path. From
Lemma 3.3, on Line 30, $A_{s,t}$ is not shorter than the shortest $s$-$t$
path, and if the shortest $s$-$t$ path has a hop more than $H$, $A_{s,t}$ is
the length of the shortest $s$-$t$ path with high probability. Due to Line 32,
at the end of the algorithm, with high probability, for every
$(s,t)\in\mathrm{V}^{2}$, $A_{s,t}$ is the length of the shortest $s$-$t$
path. ∎

###  4.3 An Efficient Data Structure With An Oracle

We will now introduce a data structure that achieves our desired running time
with the help of an oracle that we will later dispose of. An $h$-hop shortest
$s$-$t$ path is called _$h$ -hop-dominant_ if it’s also $2h$-hop shortest. A
path $p$ is _strongly-hop-dominant_ if it’s $4\left\lvert p\right\rvert$-hop
shortest. We will later prove that strongly-hop-dominant paths can be computed
efficiently using the following lemma: lemmacomputedominant For a graph $G$ of
$n$ vertices and $m$ edges and a starting vertex $s$ and a hop limit $H$,
there is an algorithm $\textsc{SSSHDP}(G,H,s)$ that can, in
$\widetilde{O}(n+m)$ time and space, compute a set of paths from $s$ in $G$
that contains all strongly-hop-dominant paths starting from vertex $s$ with a
hop at most $H$.

####  4.3.1 Rebuild Algorithm

To speed up the rebuilds, we will employ two ideas. The first idea is to use
random sampling to compute the set $O_{i}$. Instead of going through all the
vertices and computing their contribution to congestion as we did in Algorithm
1, we only do so for some vertices sampled randomly, and we try to simulate
the original algorithm in an approximate sense by magnifying the congestion
contributions. The second idea is that instead of computing all hop-restricted
paths, we use Lemma 4.3 to compute only those that are strongly hop-dominant.
With the oracle, we will show that these paths are sufficient for an efficient
update procedure.

The sampling step is shown in Algorithm 3. The difference between Algorithm 3
and Algorithm 1 is that in Algorithm 3, we skip the majority of vertices but
we magnify the congestion contributions from paths to vertices by a large
factor inverse to the probability of keeping a vertex.

Algorithm 3 Sampling congested vertex set $O_{i}$ for paths through centers
$C_{i}$

1:function Sample($i,C_{i}$)

2: $O_{i}\leftarrow\emptyset$

3: Set threshold ${\tau}_{i}\leftarrow n^{2.5}/2^{i}$

4: for $j\in[0,i_{h}]$ do

5: Initialize $\textsc{Congestion}_{i}[j,v]\leftarrow 0$ for all
$v\in\mathrm{V}$

6: $p_{j}\leftarrow\frac{n^{2}\log{n}}{\tau_{i}h_{j}}$ $\triangleright$
Probability of keeping a vertex

7: Uniformly sample indices in $[1,\left\lvert\mathrm{V}\right\rvert]$ with
probability $p_{j}$.

8: for $k\in[1,\left\lvert\mathrm{V}\right\rvert]$ do

9: $s\leftarrow\mathrm{V}[k]$

10: if Index $k$ is sampled then

11: $\pi_{i}[s,*,j]\leftarrow\textsc{BellmanFordThroughCenter}(s,G\backslash
O_{i},C_{i},h_{j})$

12: for $t\in V,u\in\pi_{i}[s,t,j]$ do

13:
$\textsc{Congestion}_{i}[j,u]\leftarrow\textsc{Congestion}_{i}[j,u]+(n/h_{j})/p_{j}$

14: end for

15: $O_{i}\leftarrow
O_{i}\cup\\{v\in\mathrm{V}\mid\textsc{Congestion}_{i}[j,v]>{\tau}_{i}\\}$

16: end if

17: end for

18: end for

19: return $O_{i}$

20:end function

We now show that Algorithm 3 indeed approximates a good set of congested
vertices and runs efficiently. We analyze the running time, bound the size of
$C_{i}$, and argue that our set bounds the congestion values in an approximate
sense for an implicit set of paths.

######  Lemma 4.12.

Algorithm 3 runs in
$\widetilde{O}(\frac{n^{5}}{\tau_{i}})=\widetilde{O}(n^{2.5}2^{i})$ time with
high probability.

###### Proof.

For each $j$, observe that the number of indices sampled on Line 7 is
$I_{j}=O(p_{j}n)$ with high probability due to the Chernoff Bound. Thus the
running time of Algorithm 3 is $O(\sum_{j}{I_{j}\times
n^{2}h_{j}})=O(\sum_{j}{p_{j}n^{3}h_{j}})=\widetilde{O}(\frac{n^{5}}{\tau_{i}})$
with high probability. ∎

Our congested vertex set satisfies the following:

######  Lemma 4.13.

$\left\lvert O_{i}\right\rvert=O(\frac{n^{3}}{\tau_{i}})$ with high
probability.

###### Proof.

For each level $j\in[0,i_{h}]$, since the number of indices sampled on Line 7
is $I_{j}=O(p_{j}n)$ and each source vertex contributes a congestion of
$(n/h_{j})/p_{j}$ to at most $n$ vertices,
$\sum_{u}{\textsc{Congestion}_{i}[j,u]}\leq
I_{j}\times(n^{2}/h_{j})/p_{j}=O(n^{3}/h_{j})$ with high probability. Since
all congested vertices have a congestion value of at least $\tau_{i}$, the
contribution to $\left\lvert C_{i}\right\rvert$ on level $j$ is
$O(\frac{n^{3}}{\tau_{i}h_{j}})$ with high probability. Since
$\sum_{j\in[0,i_{h}]}1/h_{j}=\sum_{j\in[0,i_{h}]}{1/(3/2)^{j}}=O(1)$, the
contribution across all $j$ is
$\sum_{j\in[0,i_{h}]}{\frac{n^{3}}{\tau_{i}h_{j}}}=O(\frac{n^{3}}{\tau_{i}})$
with high probability. ∎

We argue that the sampled vertices bound the congestion incurred by a set of
paths that we could not afford to obtain. We consider a hypothetical data
structure run in parallel with the actual data structure with the same random
seeds. In the hypothetical data structure, suppose that we execute Line 11 for
every index $k$ instead of only for those that are sampled. The set of paths
$\pi_{i}[*,*,*]$ will now be complete, and this modified routine is very
similar to Algorithm 1 except that we calculate contribution in a randomized
way. It is easy to see that in the hypothetical data structure, Lemma 4.8 and
Invariant (4) from Lemma 4.4 are both still true. We argue that for the
computed set of paths $\pi_{i}[*,*,*]$, the associated congestion is bounded
on each vertex. Namely, consider the congestion
$\overline{\textsc{Congestion}}_{i}[*,*]$ computed in this way in the
hypothetical data structure: for each index $k$ from the for loop on Line 8,
we run the for loop on Line 12 and add $n/h_{j}$ to
$\overline{\textsc{Congestion}}_{i}[j,u]$. We will argue that the accumulation
on $\overline{\textsc{Congestion}}_{i}[j,u]$ is bounded with high probability
for every $(j,u)\in[0,i_{h}]\times\mathrm{V}$.

######  Lemma 4.14.

In the hypothetical data structure, for any $c>0$, with probability
$1-n^{-c}$, for every $(j,u)\in[0,i_{h}]\times\mathrm{V}$,
$\overline{\textsc{Congestion}}_{i}[j,u]\leq(2c+9)\tau_{i}$.

###### Proof.

We first show that $\overline{\textsc{Congestion}}_{i}[j,u]\leq(2c+9)\tau_{i}$
is unconditionally true as long as
$\overline{\textsc{Congestion}}_{i}[j,u]\leq(2c+8)\tau_{i}$ when
$\textsc{Congestion}_{i}[j,u]\leq\tau_{i}$. To see this, suppose
$\textsc{Congestion}_{i}[j,u]>\tau_{i}$. Consider the last execution of the
for loop on Line 8 (with the modification mentioned above) before
$\textsc{Congestion}_{i}[j,u]>\tau_{i}$. Before this execution
$\textsc{Congestion}_{i}[j,u]\leq\tau_{i}$. If
$\overline{\textsc{Congestion}}_{i}[j,u]\leq(2c+8)\tau_{i}$, since a single
source contributes at most $n^{2}/h_{j}<\tau_{i}$ to
$\overline{\textsc{Congestion}_{i}[j,u]}$ and $u$ is removed from the graph
after the execution,
$\overline{\textsc{Congestion}}_{i}[j,u]\leq(2c+9)\tau_{i})$ will remain true.

Therefore, it suffices to prove that with probability $1-n^{-c}$, for every
$u$, whenever $\textsc{Congestion}_{i}[j,u]\leq\tau_{i}$,
$\overline{\textsc{Congestion}}_{i}[j,u]\leq(2c+8)\tau_{i}$. We prove that
with probability $1-n^{-c}$, the contra-positive is true: for every $u$,
whenever $\overline{\textsc{Congestion}}_{i}[j,u]>(2c+8)\tau_{i}$,
$\textsc{Congestion}_{i}[j,u]>\tau_{i}$.

Assume $\overline{\textsc{Congestion}}_{i}[j,u]>(2c+8)\tau_{i}$. Let
$c_{0}=n^{2}/h_{j}$. We let $Y_{k}$ be the value between $[0,1]$ that equals
$p_{j}/c_{0}$ times the contribution to
$\overline{\textsc{Congestion}}_{i}[j,u]$ from $s=\mathrm{V}[k]$, and let
$X_{k}$ be the random variable between $[0,1]$ that is equal to $Y_{k}/p_{j}$
if $k$ is sampled and $0$ otherwise. We can see that
$\textsc{Congestion}_{i}[j,u]=c_{0}/p_{j}\sum_{k}{X_{k}}$ and
$\overline{\textsc{Congestion}}_{i}[j,u]=c_{0}/p_{j}\sum_{k}{Y_{k}}$.
$\textsc{Congestion}_{i}[j,u]>\tau_{i}$ is equivalent to
$c_{0}/p_{j}\sum_{k}{X_{k}}>\tau_{i}$, which is then equivalent to
$\sum_{k}{X_{k}}>\log n$. Under the assumption that
$\overline{\textsc{Congestion}}_{i}[j,u]=c_{0}/p_{j}\sum_{k}{Y_{k}}>(2c+8)\tau_{i}$,
we have $\sum_{k}{Y_{k}}>(2c+8)\tau_{i}\times p_{j}/c_{0}=(2c+8)\log{n}$. We
have $\mathbb{E}(X_{k}\mid X_{1}\cdots X_{k-1},Y_{1},\cdots
Y_{k})=p_{j}\times(Y_{k}/p_{j})+(1-p_{j})\times 0=Y_{k}$ since the indices are
sampled independently. We can now apply Lemma 3.4 on $X$ and $Y$ with
$\varepsilon=1/2$ and $\delta=(c+3)\log n$, which proves that
$\sum_{k}{X_{k}}>\log n$ does not hold with probability at most $n^{-c-3}$. By
taking the union bound over triples
$(j,u,k)\in[0,i_{h}]\times\mathrm{V}\times[1,\left\lvert\mathrm{V}\right\rvert]$,
which there are $n^{2}i_{h}\leq n^{3}$ of, we prove the claim. ∎

Our new rebuild algorithm combines the idea of computing only strongly
dominant paths and the idea of applying random sampling. We first obtain the
set $O_{i}$ using the sampling sub-routine above. Then we compute all the
strongly-hop-dominant paths to and from a vertex in $C_{i}$ in $G\backslash
O_{i}$ using Lemma 4.3, and combine them to cover all strongly-hop-dominant
paths through $C_{i}$ in $G\backslash O_{i}$. For an positive interger $x$ we
let $h^{-1}(x)$ be the smallest $y$ such that $x\leq h_{y}$. For a path $p$,
let the _hop level_ of $p$ be $h^{-1}(\left\lvert p\right\rvert)$. Our rebuild
algorithm is described in Algorithm 4.

Algorithm 4 New Rebuild Algorithm

1:procedure RebuildNew($i,C_{i}$)

2: $O_{i}\leftarrow\textsc{Sample}(i,C_{i})$

3: $\Pi_{i}[*,*,*]\leftarrow\perp$

4: for $c\in C_{i}$ do

5: $P_{\textrm{from}}\leftarrow\textsc{SSSHDP}(G\backslash O_{i},h,c)$

6: $P_{\textrm{to}}\leftarrow\textsc{SSSHDP}(\overleftarrow{G\backslash
O_{i}},h,c)$

7: for $p_{\textrm{from}}\in P_{\textrm{from}},p_{\textrm{to}}\in
P_{\textrm{to}}$ do

8: $p=\overleftarrow{p_{\textrm{to}}}\circ p_{\textrm{from}}$

9: $j\leftarrow h^{-1}(\left\lvert p\right\rvert)$

10: if $w(p)<w(\Pi_{i}[p[0],p[\left\lvert p\right\rvert],j])$ then

11: $\Pi_{i}[p[0],p[\left\lvert p\right\rvert],j]\leftarrow p$

12: end if

13: end for

14: end for

15: $C_{i-1}\leftarrow O_{i}$

16:end procedure

Due to Lemma 4.3, Algorithm 4 obviously runs in
$\widetilde{O}(n^{2}\left\lvert C_{i}\right\rvert)$ time. The next two lemmas
prove that the algorithm is correct.

######  Lemma 4.15.

If a path $p$ is strongly-hop-dominant, for every $k\in[0,\left\lvert
p\right\rvert]$, both $p[0,k]$ and $p[k,\left\lvert p\right\rvert]$ are
strongly-hop-dominant.

###### Proof.

Suppose without loss of generality $p[0,k]$ is not strongly-hop-dominant.
There is a path $p^{\prime}$ with a hop no more than $4k$ from $p[0]$ to
$p[k]$ that is shorter than $p[0,k]$. By replacing $p[0,k]$ with $p^{\prime}$
we find a shorter path with the same starting and ending vertices as $p$ with
a hop no more than $\left\lvert p\right\rvert+3k\leq 4\left\lvert
p\right\rvert$, which contradicts the fact that $p$ is strongly-hop-dominant.
∎

######  Lemma 4.16.

The path $\Pi_{i}[s,t,j]$ has a hop of at most $h_{j}$ and is not longer than
the $h_{j}$-hop shortest strongly-hop-dominant path between $s$ and $t$ in
$G\backslash O_{i}$.

###### Proof.

Straightforward from the procedure due to Lemma 4.3 and Lemma 4.15. ∎

####  4.3.2 Update Algorithm with An Oracle

For each update, suppose we have an oracle $\textsc{HopAndLength}(s,t)$ that
tells us the hop and the length of the shortest path between each pair of
vertices $(s,t)\in\mathrm{V}^{2}$. We argue that we can use the oracle to
concatenate paths computed in the rebuilding procedures to efficiently
retrieve the shortest paths that have a hop at most $H$. To do this, for every
$(s,t)\in\mathrm{V}^{2}$, we find ${\Pi^{\prime}}[s,t]$ which is the shortest
surviving $s$-$t$ path computed from rebuilding each layer. Then for every
$(s,t)\in\mathrm{V}^{2}$, if the shortest surviving $s$-$t$ path is not
optimal, we recover it using the hitting set for the hop level of the shortest
$s$-$t$ path, as detailed in Algorithm 5.

Algorithm 5 Update Procedure With Oracle

1:function Recover($\Pi_{o},s,t,j$) $\triangleright$ Recover ${\Pi_{o}}[s,t]$
using the hitting set for hop level $j$

2: $\eta\leftarrow\\{v\mid X[s,v,t,j]=1\\}$ $\triangleright$ Construct the
hitting set.

3:
$x^{\prime}\leftarrow\textrm{argmin}_{x\in\eta}{w({\Pi_{o}}[s,x]\circ{\Pi_{o}}[x,t])}$

4: return ${\Pi_{o}}[s,x^{\prime}]\circ{\Pi_{o}}[x^{\prime},t]$

5:end function

6:function UpdateWithOracle

7: $\Pi^{\prime}[*,*]\leftarrow\perp$

8: for $i\in[0,L]$ do

9: for $j\in[0,i_{h}]$ do

10: for $s,t\in\mathrm{V}$ do

11: if $\Pi_{i}[s,t,j]\cap D_{i}=\emptyset$ then

12: if $w(\Pi_{i}[s,t,j])<w({\Pi^{\prime}}[s,t])$ then

13: ${\Pi^{\prime}}[s,t]\leftarrow\Pi_{i}[s,t,j]$

14: end if

15: end if

16: end for

17: end for

18: end for

19: $\Pi_{o}=\textrm{a copy of }\Pi^{\prime}$

20: for $j\in[0,i_{h}]$ do

21: for $s,t\in\mathrm{V}$ do

22: $(x,y)\leftarrow\textsc{HopAndLength}(s,t)$

23: if $h^{-1}(x)=j\ \textbf{AND }w({\Pi_{o}}[s,t])>y$ then

24: ${\Pi_{o}}[s,t]\leftarrow\textsc{Recover}(\Pi_{o},s,t,j)$

25: end if

26: end for

27: end for

28: $A=\textsc{RandGetShortestPaths}(G,H)$

29: for $s,t\in\mathrm{V}$ do

30: $A_{s,t}\leftarrow\min(A_{s,t},w({\Pi_{o}}[s,t]))$

31: end for

32: return $A$

33:end function

Recall the hypothetical data structure mentioned before where we obtain the
full array of $\pi_{i}[*,*,*]$ for each layer $i$ in Algorithm 3 by executing
Line 11 for every index $k$. Assume that in that hypothetical data structure,
for every update, instead of calling Algorithm 5 we call Algorithm 2. Recall
that in the hypothetical data structure, Lemma 4.8 and Invariant (4) from
Lemma 4.4 are both still true. We show that Algorithm 5 runs in
$\widetilde{O}(n^{2.5})$ time by relating its total recovery cost to the total
recovery cost of Algorithm 2 in the hypothetical data structure. We prove the
following Lemma:

######  Lemma 4.17.

If the unique shortest $s$-$t$ path $p$ has a hop level $j\leq i_{h}$ and gets
recovered on Line 24 of Algorithm 5, then in the hypothetical data structure,
$\mathrm{NeedsRecovery}[s,t,j^{\prime}]$ is TRUE in Algorithm 2 for some
$j^{\prime}\in\\{j,j+4\\}$.

###### Proof.

Assume that $p$ gets recovered on Line 24 of Algorithm 5 and that
$\mathrm{NeedsRecovery}[s,t,j]$ is FALSE in Algorithm 2. By the second
assumption and Lemma 4.8, in Algorithm 2, $\pi^{\prime}[s,t,j]=p$ and
therefore we can find some $i\in[0,L]$ such that $\pi_{i}[s,t,j]=p$. By the
first assumption, in Algorithm 5, $w(\Pi^{\prime}[s,t])>w(p)$ since otherwise
the second condition on Line 23 will never be true. Therefore
$w(\Pi_{i}[s,t,j])>w(p)$. From Lemma 4.16, $p$ must not have been a strongly-
hop-dominant $s$-$t$ path through $C_{i}$ in $G\backslash O_{i}$. From
Invariant (4) in Lemma 4.4, $\pi_{i}[s,t,j+4]$ is not longer than
$h_{j+4}$-hop shortest $s$-$t$ path through $C_{i}$ in $G\backslash O_{i}$.
Since $h_{j+4}>4h_{j}$, $w(\pi_{i}[s,t,j+4])<w(p)$. Since $p$ is the shortest
path after the batch deletion procedure, $\pi_{i}[s,t,j+4]$ must have been
deleted in the batch deletion in Algorithm 2, which makes
$\mathrm{NeedsRecovery}[s,t,j+4]$ TRUE. ∎

######  Lemma 4.18.

The total update cost for triples $(s,t,j)$ involved on Line 24 is
$\widetilde{O}(n^{2.5})$ with high probability, and the running time of
Algorithm 5 is $\widetilde{O}(n^{2.5})$ with high probability.

###### Proof.

From Lemma 4.17 it is easy to see that the total recovery cost in Algorithm 5
is at most $(3/2)^{4}$ times the recovery cost in Algorithm 2 of the
hypothetical data structure. From Lemma 4.14 it is easy to see the latter is
$\widetilde{O}(n^{2.5})$ with high probability, which means that the former is
also $\widetilde{O}(n^{2.5})$ with high probability.

The total running time of Line 24 is equal to the total recovery cost with
high probability, which is $\widetilde{O}(n^{2.5})$. It is easy to verify that
the rest of Algorithm 2 runs in $\widetilde{O}(n^{2.5})$ time. Therefore, the
running time of Algorithm 2 is $\widetilde{O}(n^{2.5})$ with high probability.
∎

We now show the correctness.

######  Lemma 4.19.

With high probability, at the end of Algorithm 10, for every
$(s,t)\in\mathrm{V}^{2}$ such that the shortest $s$-$t$ path has a hop at most
$H$, ${\Pi_{o}}[s,t]$ is the shortest $s$-$t$ path, and for every
$(s,t)\in\mathrm{V}^{2}$, $A_{s,t}$ is the length of the shortest $s$-$t$
path.

###### Proof.

We do induction on the hop level $j$ of the shortest paths.

Suppose for every $(s,t)\in\mathrm{V}^{2}$ such that the shortest $s$-$t$ path
has a hop at most $h_{j-1}$, ${\Pi_{o}}[s,t]$ is the shortest $s$-$t$ path.
Then for the hop level $j$, if for some $(s,t)\in\mathrm{V}^{2}$ such that the
shortest $s$-$t$ path has a hop between $h_{j-1}+1$ and $h_{j}$, then when the
for loop on Line 20 reaches hop level $j$, on Line 23, either the second
condition is true and ${\Pi_{o}}[s,t]$ is recovered to be the $h_{j}$-hop
shortest $s$-$t$ path due the same argument in the proof of Lemma 4.9, which
by assumption is the shortest $s$-$t$ path, or the second condition is false
and ${\Pi_{o}}[s,t]=\Pi^{\prime}[s,t]$ is already the shortest $s$-$t$ path.
By induction, for every $(s,t)\in\mathrm{V}^{2}$ such that the shortest
$s$-$t$ path has a hop at most $H$, ${\Pi_{o}}[s,t]$ is the shortest $s$-$t$
path.

From a similar argument as the one in Lemma 4.11, with high probability, for
every $(s,t)\in\mathrm{V}^{2}$, $A_{s,t}$ is the length of the shortest
$s$-$t$ path. ∎

####  4.3.3 Computing Single-Source Strongly-Hop-Dominant Paths

Finally, we prove Lemma 4.3. * To introduce the algorithm that computes the
single source strongly-hop-dominant paths, we first introduce a helper
algorithm that computes the $h$-hop-dominant paths for a given parameter $h$.
Our algorithm is based on Dijkstra’s single source shortest path algorithm. We
find the unextended vertex with the shortest distance from the source and try
to extend from that vertex, but different from Dijkstra’s algorithm, we
constrain that the hop does not exceed the given limit $h$ at any time. The
details are shown in Algorithm 6.

Algorithm 6 Single Source Hop Dominant Paths

1:function SSHDP($G,h,s$)

2: for $v\in\mathrm{V}\backslash s$ do

3: $\pi[s,v]\leftarrow\perp$

4: end for

5: $\pi[s,s]\leftarrow\langle s\rangle$

6: ${\mathrm{V}}_{0}\leftarrow\mathrm{V}$

7: while $\\{v\mid v\in V_{0}\cap\pi[s,v]\neq\perp\\}\neq\emptyset$ do

8: $u\leftarrow\operatorname*{arg\,min}\\{w(\pi[s,v^{\prime}])\mid
v^{\prime}\in{\mathrm{V}}_{0}\\}$

9: ${\mathrm{V}}_{0}\leftarrow{\mathrm{V}}_{0}\backslash u$

10: if $\left\lvert\pi[s,u]\right\rvert<h$ then

11: for $v\in{\mathrm{V}}_{0}$ do

12: if $w(\pi[s,v])>w(\pi[s,u]\circ\langle u,v\rangle)$ OR
($w(\pi[s,v])=w(\pi[s,u]\circ\langle u,v\rangle)$ AND
$\left\lvert\pi[s,v]\right\rvert>\left\lvert\pi[s,u]\circ\langle
u,v\rangle\right\rvert$) then

13: $\pi[s,v]\leftarrow\pi[s,u]\circ\langle u,v\rangle$

14: end if

15: end for

16: end if

17: end while

18: return $\\{\pi[s,v]\mid v\in\mathrm{V}\\}\backslash\perp$

19:end function

Algorithm 6 can be optimized using a Fibonacci Heap to $O(n\log n+m)$ time and
$O(n+m)$ space on an $n$-vertex, $m$-edge graph, similar to the standard
Dijkstra’s Algorithm [Dij59, FT87]. The output paths can be stored in $O(n)$
space if we store the paths as a rooted tree. Here since $m=O(n^{2})$, the
running time is $\widetilde{O}(n^{2})$, and the space usage is $O(n^{2})$.

###### Proof of Lemma 4.3.

We first show that in Algorithm 6 the set $\\{\pi[s,v]\mid v\in V\\}$ contains
all the $h$-hop-dominant paths. We show that if an $h$-hop-dominant path
exists from $s$ to $v$, then $\pi[s,v]$ is the $h$-hop-dominant path. Suppose
an $h$-hop-dominant path $p$ exists between $s$ and $v$, but $\pi[s,v]\neq p$.
Since we assume that hop-restricted shortest paths are unique and $\pi[s,v]$
is either $\perp$ or a path with a hop at most $h$, we have
$w(\pi[s,v])>w(p)$. Let $i>0$ be the minimum index such that either
$w(\pi[s,p[i]])\neq w(p[0,i])$ or
$\left\lvert\pi[s,p[i]]\right\rvert>\left\lvert p[0,i]\right\rvert$. Since
$w(\pi[s,p[i-1]])=w(p[0,i-1])$ and
$\left\lvert\pi[s,p[i-1]]\right\rvert\leq\left\lvert p[0,i-1]\right\rvert<h$,
from the algorithm we know $w(\pi[0,p[i]])\leq w(p[0\dots i])$ and
$\left\lvert\pi[0,p[i]]\right\rvert\leq\left\lvert p[0,i]\right\rvert$. From
the choice of index $i$, we have $w(\pi[0,p[i]])\neq w(p[0\dots i])$.
Therefore, $w(\pi[0,p[i]])<w(p[0\dots i])$. Therefore the path
$\pi[s,p[i]]\circ p[i,h]$ has a shorter length than $p$ and has a hop of at
most $h+h-i\leq 2h$, which contradicts the fact that $p$ is $h$-hop-dominant.

In order to include all single source strongly-hop-dominant paths with a hop
_at most_ $H$, run Algorithm 6 with
$h=1,2,4,\cdots,2^{\left\lceil\log_{2}{H}\right\rceil}$. If a path $p$ is
strongly-hop-dominant, then it is $2^{\left\lceil\log_{2}{\left\lvert
p\right\rvert}\right\rceil}$-hop-dominant. Since there are $O(\log
n)=\widetilde{O}(1)$ possible values of $h$, the total running time is still
$\widetilde{O}(n^{2})$, and space usage is still $O(n^{2})$ and the output
paths can be stored in $\widetilde{O}(n)$ space. ∎

###  4.4 Final Data Structure Without The Oracle

Now we assume that we no longer have access to the oracle used in Algorithm 5
in the actual data structure. Throughout the section when we refer to
Algorithm 5, we refer to the one inside another hypothetical data structure
run in parallel with the actual data structure with the same random seeds but
with access to the oracle. Consider Algorithm 5. We can categorize the
$(s,t)\in\mathrm{V}^{2}$ pairs where the shortest $s$-$t$ path has a hop at
most $H$ into two types:

  * •

Primary: if $\Pi_{o}[s,t]=\Pi^{\prime}[s,t]$, that is, the shortest path has
been present before the start of the for loop on Line 20, the pair $(s,t)$ and
the path $\Pi_{o}[s,t]$ are called _primary_

  * •

Secondary: if path $\Pi_{o}[s,t]\neq\Pi^{\prime}[s,t]$, that is, the shortest
path is recovered on Line 24, the pair $(s,t)$ and the path $\Pi_{o}[s,t]$ are
called _secondary_

In Algorithm 5, every time we try to recover a secondary vertex pair $(s,t)$
where the hop level of the shortest $s$-$t$ path is $j$, we go through
candidates $v$ such that $X[s,v,t,j]=1$ and use the concatenation of paths
$\Pi_{o}[s,v]$ and $\Pi_{o}[v,t]$ as a candidate. There are two types of
candidates here:

  1. 1.

Type I: both of $(s,v)$ and $(v,t)$ are primary.

  2. 2.

Type II: one or both of $(s,v)$ and $(v,t)$ are secondary.

We will first introduce how we can deal with type I candidates, and then we
will deal with type II candidates.

####  4.4.1 Type I candidates

Given the paths $\Pi^{\prime}[*,*]$ computed in Algorithm 5, for each pair of
vertices $(s,t)$ we define an $s$-$t$ _concatenation_ to be any path of the
form $\Pi^{\prime}[s,v]\circ\Pi^{\prime}[v,t]$ for some $v\in\mathrm{V}$. Let
$j$ be the hop level of the shortest path between $s$ and $t$. The
concatenation is called _hitting set compatible_ if $X[s,v,t,j]=1$. We
consider the auxiliary problem of maintaining _all-pairs shortest hitting set
compatible concatenations_ subject to vertex deletions. Specifically, for each
pair of vertices $(s,t)\in\mathrm{V}^{2}$, we will find an $s$-$t$ path in the
current graph that is at most as long as the shortest $s$-$t$ concatenation
that is hitting set compatible.

This task is similar to the problem of maintaining APSP subject to vertex
deletion, and it is very easy to design an auxiliary data structure similar to
the previous data structure for dynamic APSP by Gutenberg and Wilff-Nilsen and
attach it to our existing data structure. Intuitively, since we only
concatenate two primary paths, it is almost as if we only need to maintain
all-pairs 2-hop shortest paths, so the auxiliary data structure can actually
be implemented efficiently. We now introduce how we implement such an
auxiliary data structure in detail.

We will use the following lemma to be proven later as an ingredient:
lemmaconcat Given a set of paths $P$ with hop at most $h$ inside a graph
$G=\langle\mathrm{V},\mathrm{E}\rangle$ with
$n=\left\lvert\mathrm{V}\right\rvert$, and a vertex $c\in\mathrm{V}$. Suppose
that for every path $p\in P$, the following operations can be done in $O(1)$
time:

  * •

Given a vertex $c\in\mathrm{V}$, check whether $c\in p$;

  * •

Given a vertex $c\in\mathrm{V}$, find the path $p[<c]$;

  * •

Given a vertex $c\in\mathrm{V}$, find the path $p[>c]$.

Then there is an algorithm $\textsc{Concat}(P,Q,c)$ in
$\widetilde{O}(\left\lvert P\right\rvert+n^{2})$ time and space that can
compute an array $\pi[*,*]$ where for any pair of vertices
$(s,t)\in\mathrm{V}^{2}$, $\pi[s,t]$ is either an $s$-$t$ path with a hop of
$O(h)$ in $G$ or $\perp$, such that for all $p_{0},p_{1}\in P$ such that $c\in
p_{0}$ and $p_{0}\circ p_{1}$ is an $s$-$t$ path, $w(\pi[s,t])<w(p_{0}\circ
p_{1})$. Similarly, there is an algorithm $\overline{\textsc{Concat}}(P,Q,c)$
in $\widetilde{O}(\left\lvert P\right\rvert+n^{2})$ time and space that can
compute an array $\overline{\pi}[*,*]$ where for any pair of vertices
$(s,t)\in\mathrm{V}^{2}$, $\overline{\pi}[s,t]$ is either an $s$-$t$ path with
a hop of $O(h)$ in $G$ or $\perp$, such that for all $p_{0},p_{1}\in P$ such
that $c\in p_{1}$ and $p_{0}\circ p_{1}$ is an $s$-$t$ path,
$w(\overline{\pi}[s,t])<w(p_{0}\circ p_{1})$.

For the rebuild algorithms, our idea is to find a set of good concatenations
such that after each batch deletion, only a small amount of these
concatenations need to be recomputed. Whenever a layer $i$ is rebuilt, for
each hop level $j$ and vertex pair $(s,t)\in\mathrm{V}^{2}$, we perform an
additional routine to cover the possible concatenations of some path
$\Pi_{i_{0}}[s,v,j_{0}]$ ($(v,j_{0})\in\mathrm{V}\times[0,j]$) from layer
$i_{0}\in[0,i]$, and some path $\Pi_{i_{1}}[v,t,j_{1}]$
($(t,j_{1})\in\mathrm{V}\times[0,j]$) from layer $i_{1}\in[0,i]$, and we keep
track of the congestion caused by these concatenations and remove congested
vertices in a similar fashion as the algorithms before. We adopt the
randomization technique from Gutenberg and Wilff-Nilsen’s paper. We go through
the centers in $C_{i}$ in a uniformly random order. For every center, we use
Lemma 4.4.1 to cover the concatenations involving that center avoiding the set
of congested vertices stored in the set $\overline{O}_{i}$, and then we
compute the congestion increase on the vertices and add the congested vertices
to $\overline{O}_{i}$. The final rebuild algorithm is described in Algorithm
7.

Algorithm 7 Final Data Structure: Rebuild c.f. Algorithm 4 in [GWN20b]

1:procedure Rebuild($i,C_{i}$)

2: Compute $O_{i}$ and $\Pi_{i}[*,*,*]$ in the same way as Algorithm 4

3: $C^{\prime}\leftarrow\emptyset$

4: Set threshold ${\tau}_{i}\leftarrow n^{2.5}/2^{i}$

5: $\overline{\Pi}_{i}[*,*,*]\leftarrow\perp$

6: $\overline{O}_{i}\leftarrow\emptyset$

7: Initialize $\overline{\textsc{Congestion}}_{i}[v]\leftarrow 0$ for all
$v\in\mathrm{V}$

8: for $c\in C_{i}$ in a uniformly random order do

9: do

10: for $j\in[0,i_{h}]$ do

11:
$P\leftarrow\\{\Pi_{i^{\prime}}[s,t,j^{\prime}]\mid(i^{\prime},s,t,j^{\prime})\in[0,i]\times\mathrm{V}^{2}\times[0,j]\wedge\Pi_{i^{\prime}}[s,t,j^{\prime}]\cap\overline{O}_{i}=\emptyset\\}$

12: $\pi[*,*]\leftarrow\textsc{Concat}(P,c)$

13: $\overline{\pi}[*,*]\leftarrow\overline{\textsc{Concat}}(P,c)$

14: For every $(s,t)\in\mathrm{V}^{2}$, $\phi[s,t,j]\leftarrow$ the shorter of
$\pi[s,t]$ and $\overline{\pi}[s,t]$

15: end for

16: for $(s,t,j)\in\mathrm{V}^{2}\times[0,i_{h}]$ do

17: if $w(\phi[s,t,j])<\overline{\Pi}_{i}[s,t,j]$ then

18: $\overline{\Pi}_{i}[s,t,j]\leftarrow\phi[s,t,j]$

19: for $u\in\overline{\Pi}_{i}[s,t,j]$ do

20:
$\overline{\textsc{Congestion}}_{i}[v]\leftarrow\overline{\textsc{Congestion}}_{i}[v]+n/h_{j}$

21: end for

22: end if

23: if
$\overline{O}_{i}\neq\\{v\in\mathrm{V}\mid\overline{\textsc{Congestion}}[v]>{\tau}_{i}\\}$
then

24:
$\overline{O}_{i}\leftarrow\\{v\in\mathrm{V}\mid\overline{\textsc{Congestion}}[v]>{\tau}_{i}\\}$

25: for $j\in[0,i_{h}]$ do

26:
$P\leftarrow\\{\Pi_{i^{\prime}}[s,t,j^{\prime}]\mid(i^{\prime},s,t,j^{\prime})\in[0,i]\times\mathrm{V}^{2}\times[0,j]\wedge\Pi_{i^{\prime}}[s,t,j^{\prime}]\cap\overline{O}_{i}=\emptyset\\}$

27: $\pi[*,*]\leftarrow\textsc{Concat}(P,c)$

28: $\overline{\pi}[*,*]\leftarrow\overline{\textsc{Concat}}(P,c)$

29: For every $(s,t)\in\mathrm{V}^{2}$, $\phi[s,t,j]\leftarrow$ the shorter of
$\pi[s,t]$ and $\overline{\pi}[s,t]$

30: end for

31: end if

32: end for

33: while $\overline{O}_{i}\neq\emptyset$

34: end for

35: $C_{i-1}\leftarrow O_{i}\cup\overline{O}_{i}$

36:end procedure

First we will show that the conditions in Lemma 4.4.1 are satisfied for $P$.

######  Lemma 4.20.

For every $(i,s,t,j)\in[0,L]\times\mathrm{V}^{2}\times[0,i_{h}]$, let
$p=\Pi_{i}[s,t,j]$. If $p\neq\perp$, the following operations can be done in
$O(1)$ time without using more than $\widetilde{O}(n^{2})$ space:

  * •

Given a vertex $c\in\mathrm{V}$, check whether $c\in p$;

  * •

Given a vertex $c\in p$, find the path $p[<c]$;

  * •

Given a vertex $c\in p$, find the path $p[>c]$.

###### Proof.

Observe Algorithm 7 and note that $p$ is the concatenation of two paths that
are outputs of Algorithm 6. Since the outputs of Algorithm 6 can be stored as
a rooted tree, it suffices to perform two queries on two rooted trees of the
following type: given $c$ and $x$, check whether $c$ is on the path from the
root to node $x$, and if so, find the position of $c$ on the path. This can be
done using standard techniques on static $n$-node rooted trees in
$\widetilde{O}(1)$ time per query using $\widetilde{O}(n)$ space999One such
technique is to get the DFS traversal of the tree. The sub-tree of each node
is an interval in the DFS traversal. The problem is equivalent to checking if
$x$ is in the sub-tree of $c$, which can be done by simply checking if $x$ is
in the interval of $c$ in the DFS traversal. The position of $c$ on the path
is simply the depth of $c$ in the tree.. Since there are $\widetilde{O}(n)$
trees in total, the total space usage is $\widetilde{O}(n^{2})$. To store
$p[<c]$ and $p[>c]$, we can see that either of them is a concatenation of at
most two paths on two trees. It suffices to simply store the pointers to the
starting and the ending nodes on the trees. ∎

The reader can compare the following Lemmas to Lemma 4.3 in
[GWN20b]101010Lemma 4.5 in the full version on arXiv and Lemma 4.3 in the
proceedings version..

######  Lemma 4.21.

With a probability at least $1/2$, Algorithm 7 preserves the following
invariant:

$\sum_{v\in\mathrm{V}}{\overline{\textsc{Congestion}}_{i}[v]}=O(n^{3}\log^{2}n).$

###### Proof.

Firstly, for any $(s,t,j)\in\mathrm{V}^{2}\times[0,i_{h}]$, for a fixed center
$c$, $\overline{\Pi}_{i}[s,t,j]$ gets updated at most once since adding more
vertices to $\overline{O}_{i}$ does not improve $\phi[s,t,j]$. From Lemma
4.4.1, $\phi[s,t,j]$ has a hop of at most $O(h_{j})$, and therefore every time
$\overline{\Pi}_{i}[s,t,j]$ is updated, at most $O(h_{j})$ vertices receive a
congestion increase of $n/h_{j}$. Therefore for $(s,t,j)$, the total increase
in total congestion due to center $c$ is at most $O(h_{j})\times
n/h_{j}=O(n)$.

Fix $(s,t,j)\in\mathrm{V}^{2}\times[0,i_{h}]$. Suppose the current center $c$
is the $k$-th chosen center. The probability that the $k$-th center updates
$\overline{\Pi}_{i}[s,t,j]$ is the probability that the following event
$E_{0}$ happens: $\Phi[s,t,j]$ computed at this center $c$, using some
congested set $\overline{O}_{i}$, is shorter than $\Phi[s,t,j]$ computed at
all previous centers, using what the set $\overline{O}_{i}$ was at those
centers. Consider the following event $E_{1}$: $\Phi[s,t,j]$ computed at this
center $c$ using $\overline{O}_{i}$, is shorter than $\Phi[s,t,j]$ computed at
previous centers using the _same_ $\overline{O}_{i}$. Since we only add
vertices to $\overline{O}_{i}$, the constraints on previous centers can only
be the same or stricter in $E_{1}$ compared to in $E_{0}$, and $\Phi[s,t,j]$
computed from these previous centers can only be the same or longer in $E_{1}$
compared to in $E_{0}$. Therefore $E_{0}$ implies $E_{1}$, and therefore
$Pr[E_{0}]\leq Pr[E_{1}]$. In $E_{1}$, since the set $\overline{O}_{i}$ is
fixed, the sequence of computation does not matter and $Pr[E_{1}]$ is equal to
the probability that among the first $k$ centers, $\Phi[s,t,j]$ is the
shortest when computed at the $k$-th center using the same set
$\overline{O}_{i}$, and such probability is obviously $1/k$. Thus
$Pr[E_{0}]\leq Pr[E_{1}]=1/k$. Let $Y[s,t,j]$ be the expected amount of
congestion added on Line 20. We have

$E[Y[s,t,j]]\leq\sum_{1\leq k\leq\left\lvert C_{i}\right\rvert}{1/k\times
O(n)}=O(nH_{n})=O(n\log n),$

where $H_{n}=O(\log n)$ is the $n$-th harmonic number. Since there are $O(\log
n)$ choices of $j$’s and $O(n^{2})$ choices of $s$ and $t$, the expected total
congestion
$E[\sum_{v\in\mathrm{V}}{\overline{\textsc{Congestion}}_{i}[v]}]=O(n^{3}\log^{2}n)$.
From Markov’s inequality,
$E[\sum_{v\in\mathrm{V}}{\overline{\textsc{Congestion}}_{i}[v]}]=O(n^{3}\log^{2}n)$
with a probability of at least $1/2$. ∎

######  Lemma 4.22.

With a probability of at least $1/2$, Algorithm 7 preserves the following
invariants:

  1. 1.

$\forall(j,v)\in[0,i_{h}]\times\mathrm{V}:\overline{\textsc{Congestion}}_{i}[v]\leq
2{\tau}_{i}$,

  2. 2.

$\sum_{v\in\mathrm{V}}{\overline{\textsc{Congestion}}_{i}[v]}=O(n^{3}\log^{2}n)$,

  3. 3.

$\left\lvert\overline{O}_{i}\right\rvert=O(n^{3}\log^{2}n/{\tau}_{i})=\widetilde{O}(n^{0.5}2^{i})$,

  4. 4.

For every $(s,t,j)\in\mathrm{V}^{2}\times[0,i_{h}]$,
$\overline{\Pi}_{i}[s,t,j])$ is an $s$-$t$ path with a hop of $O(h_{j})$ that
at most as long as the shortest $s$-$t$ path not visiting a vertex in
$\overline{O}_{i}$ that is of the form
$\Pi_{i_{0}}[s,v,j_{0}]\circ\Pi_{i_{1}}[v,t,j_{1}]$ for some
$(i_{0},i_{1},v,j_{0},j_{1})\in[0,i]^{2}\times\mathrm{V}\times[0,j]^{2}$ where
$c\in\Pi_{i}[v,t,j_{1}]$.

Algorithm 7 runs in $\widetilde{O}(n^{2.5}2^{i})$ time.

###### Proof.

Since a single path increases the congestion on a vertex by at most $n$,
$\overline{\textsc{Congestion}}[v]<{\tau}_{i}+n<2{\tau}_{i}$ for every vertex
$v$, which proves (1). (2) is proven in Lemma 4.21. Since each vertex
$v\in\overline{O}_{i}$ is such that
$\overline{\textsc{Congestion}}_{i}[v]\geq{\tau}_{i}$,
$\left\lvert\overline{O}_{i}\right\rvert\leq
O(n^{3}\log^{2}n/{\tau}_{i})=\widetilde{O}(n^{0.5}2^{i})$, which proves (3).
(4) is not hard to see from the construction of the set of paths $P$ in the
algorithm and the correctness of Lemma 4.4.1, as well as the fact that the
graph $G\backslash\overline{O}_{i}$ is decremental.

For every recomputation of $\phi[*,*,*]$, $\left\lvert
P\right\rvert=\widetilde{O}(n^{2})$. It is easy to see that Lemma 4.4.1
applies for $P$ from Lemma 4.20. From Lemma 4.4.1 the recomputation takes
$\widetilde{O}(n^{2})$ time. Since before every recomputation of $\phi[*,*,*]$
either some vertex is added to $\overline{O}_{i}$ or we move on to the next
center in $C_{i}$, there are $O(\left\lvert
C_{i}\right\rvert+\left\lvert\overline{O}_{i}\right\rvert)$ recomputations in
total and the total running time for these recomputations is
$\widetilde{O}((\left\lvert
C_{i}\right\rvert+\left\lvert\overline{O}_{i}\right\rvert)n^{2})=\widetilde{O}(n^{2.5}2^{i})$.
The rest of the algorithm clearly runs in $\widetilde{O}(n^{2.5}2^{i})$ time,
which proves the claim. ∎

For any arbitrarily large constant $c^{\prime}$, we can repeat the procedure
$c^{\prime}\log_{2}{n}=\widetilde{O}(1)$ times until the invariants are met,
which magnifies the probability of success to $1-n^{-c^{\prime}}$.

The update procedure for all-pairs shortest concatenation is similar to
Algorithm 2, but recovery is done using two paths in $\Pi^{\prime}$. The
update procedure is described in Algorithm 8.

Algorithm 8 Update Procedure for Concatenations Only

1:function Recover($\Pi^{\prime},s,t,j$) $\triangleright$ Recover
${\pi^{\prime}}[s,t]$ using the hitting set for hop level $j$

2: $x^{\prime}\leftarrow\textrm{argmin}_{x\in\\{v\mid
X[s,v,t,j]=1\\}\cup\\{s,t\\}}{w({\Pi^{\prime}}[s,x]\circ{\Pi^{\prime}}[x,t])}$

3: return ${\Pi^{\prime}}[s,x^{\prime}]\circ{\Pi^{\prime}}[x^{\prime},t]$

4:end function

5:function UpdateForAllPairsConcatenations

6: Compute $\Pi^{\prime}$ using the Lines 7 to 18 from 5.

7: $\overline{\Pi^{\prime}}\leftarrow\perp$

8: $\mathrm{NeedsRecovery}[*,*,*]\leftarrow\mathrm{FALSE}$

9: for $i\in[0,L]$ do

10: for $j\in[0,i_{h}]$ do

11: for $s,t\in\mathrm{V}$ do

12: if $\overline{\Pi}_{i}[s,t,j]\cap D_{i}=\emptyset$ then

13: if $w(\overline{\Pi}_{i}[s,t,j])<w({\overline{\Pi^{\prime}}}[s,t,j])$ then

14: ${\overline{\Pi^{\prime}}}[s,t,j]\leftarrow\overline{\Pi}_{i}[s,t,j]$

15: end if

16: else

17: $\mathrm{NeedsRecovery}[s,t,j]=\mathrm{TRUE}$

18: end if

19: end for

20: end for

21: end for

22: for $j\in[0,i_{h}]$ do

23: for $s,t\in\mathrm{V}$ do

24: if $\mathrm{NeedsRecovery}[s,t,j]=\mathrm{TRUE}$ then

25:
${\overline{\Pi^{\prime}}}[s,t,j]\leftarrow\textsc{Recover}(\Pi^{\prime},s,t,j)$

26: end if

27: end for

28: end for

29: return $\overline{\Pi^{\prime}}$

30:end function

To execute Line 15 in $\widetilde{O}(1)$ time, one can use a Fibonacci Heap,
similar to the standard Dijkstra’s Algorithm [Dij59, FT87].

######  Lemma 4.23.

Algorithm 8 runs in $\widetilde{O}(n^{2.5})$ time with high probability.

###### Proof.

Can be derived from a similar argument as the one used to prove Lemma 4.7. ∎

The next lemma shows the correctness.

######  Lemma 4.24.

At the end of the procedure, for every $(s,t)\in\mathrm{V}^{2}$, if some
shortest hitting set compatible $s$-$t$ concatenation is the shortest $s$-$t$
path, then $\overline{\Pi^{\prime}}[s,t,i_{h}]$ is the shortest $s$-$t$ path.

###### Proof.

Suppose some shortest hitting set compatible $s$-$t$ concatenation is the
shortest $s$-$t$ path. Let $j$ be the hop level of the shortest $s$-$t$ path.
Let some shortest hitting set compatible $s$-$t$ concatenation be
$\Pi^{\prime}[s,v]\circ\Pi^{\prime}[v,t]$. Suppose $\Pi^{\prime}[s,v]$ comes
from $\Pi_{i_{0}}[s,v,j_{0}]$ and $\Pi^{\prime}[v,t]$ comes from
$\Pi_{i_{1}}[v,t,j_{1}]$. Obviously, $\max(j_{0},j_{1})\leq j$. We will show
that $\overline{\Pi^{\prime}}[s,t,j]$ is the shortest $s$-$t$ path. Since on
Line 2 both $s$ and $t$ are included to be candidates,
$\overline{\Pi^{\prime}}[s,t,i_{h}]$ will also be the shortest $s$-$t$ path.

If $\mathrm{NeedsRecovery}[s,t,j]=\mathrm{FALSE}$, suppose
$\Pi^{\prime}[s,v]=\Pi_{i_{0}}[s,v,j_{0}]$ and
$\Pi^{\prime}[v,t]=\Pi_{i_{1}}[v,t,j_{1}]$. Let $i^{\prime}$ be the largest
index such that $\Pi^{\prime}[s,v]\cap C_{i^{\prime}}\neq\emptyset$ or
$\Pi^{\prime}[v,t]\cap C_{i^{\prime}}\neq\emptyset$. Then
$\Pi^{\prime}[s,v]\cap C_{i^{\prime}+1}=\emptyset$ and $\Pi^{\prime}[v,t]\cap
C_{i^{\prime}+1}=\emptyset$ which means that $\Pi^{\prime}[s,v]\cap
O_{i^{\prime}}=\emptyset$ and that $\Pi^{\prime}[v,t]\cap
O_{i^{\prime}}=\emptyset$. Note that
$\Pi^{\prime}[s,v]=\Pi_{i_{0}}[s,v,j_{0}]$ is through $C_{i_{0}}$ and
$\Pi^{\prime}[v,t]=\Pi_{i_{1}}[v,t,j_{1}]$ is through $C_{i_{1}}$, which means
that $\Pi^{\prime}[s,v]\cap C_{i_{0}}\neq\emptyset$ and $\Pi^{\prime}[v,t]\cap
C_{i_{1}}\neq\emptyset$. Therefore we have $i^{\prime}\geq\max(i_{0},i_{1})$.
From Invariant (4) in Lemma 4.22, $\overline{\Pi}_{i^{\prime}}[s,t,j]$ is not
longer than $\Pi^{\prime}[s,v]\circ\Pi^{\prime}[v,t]$. Since this path will be
used to update $\overline{\Pi^{\prime}}[s,t,j]$ on Line 14,
$\overline{\Pi^{\prime}}[s,t,j]$ is an $s$-$t$ path that is not longer than
the shortest hitting set compatible $s$-$t$ concatenation. Since the shortest
hitting set compatible $s$-$t$ concatenation is the shortest $s$-$t$ path and
the algorithm makes sure that $\overline{\Pi^{\prime}}[s,t,j]$ is either
$\perp$ or an $s$-$t$ path, $\overline{\Pi^{\prime}}[s,t,j]$ is the shortest
$s$-$t$ path.

If $\mathrm{NeedsRecovery}[s,t,j]=\mathrm{TRUE}$, then Line 25 will be run for
$(s,t,j)$. Since $X[s,v,t,j]=1$, $v$ will be a candidate on Line 2, and
therefore $w(\overline{\Pi^{\prime}}[s,t,j])\leq w(Pi^{\prime}[s,v]\circ
Pi^{\prime}[v,t])$. Since $Pi^{\prime}[s,v]\circ Pi^{\prime}[v,t]$ is the
shortest $s$-$t$ path and the algorithm makes sure that
$\overline{\Pi^{\prime}}[s,t,j]$ is either $\perp$ or an $s$-$t$ path,
$\overline{\Pi^{\prime}}[s,t,j]$ is the shortest $s$-$t$ path. ∎

We will show that for $(s,t)\in\mathrm{V}^{2}$ where the hitting set
compatible $s$-$t$ concatenation is not the shortest $s$-$t$ path, some type
II candidate can be used to correctly recover the shortest $s$-$t$ path.
Therefore, Lemma 4.24 will turn out to be sufficient for type I candidates.

Finally, we prove Lemma 4.4.1. * We now only show how to implement
$\textsc{Concat}(P,c)$ since the implementation of
$\overline{\textsc{Concat}}(P,c)$ is similar:

Algorithm 9 Algorithmic Proof of Lemma 4.4.1

1:procedure concat($P,c$)

2: $P_{\textrm{from}}[*]\leftarrow\perp$

3: $P_{\textrm{to}}[*]\leftarrow\perp$

4: $\Pi[*,*]\leftarrow\perp$

5: for $p\in P$ do

6: if $w(p)<w(\Pi[0,p[\left\lvert p\right\rvert]])$ then

7: $\Pi[0,p[\left\lvert p\right\rvert]]\leftarrow p$

8: end if

9: if $c\in p$ then

10: if $w(p[<c])<w(P_{\textrm{from}}[p[0]])$ then

11: $P_{\textrm{from}}[p[0]]\leftarrow p[<c]$

12: end if

13: if $w(p[>c])<w(P_{\textrm{to}}[p[\left\lvert p\right\rvert]])$ then

14: $P_{\textrm{to}}[p[\left\lvert p\right\rvert]]\leftarrow p[>c]$

15: end if

16: end if

17: end for

18: for $(u,t)\in\mathrm{V}^{2}$ do

19: $p\leftarrow P_{\textrm{to}}[u]\circ\Pi[u,t]$

20: if $(w(p)<w(\pi_{[}c,t])$ then

21: $\pi_{[}c,t]\leftarrow p$

22: end if

23: end for

24: for $(s,t)\in\mathrm{V}^{2}$ do

25: $p\leftarrow P_{\textrm{from}}[s]\circ\pi[c,t]$

26: if $w(p)<w(\pi[s,t])$ then

27: $\pi[s,t]\leftarrow p$

28: end if

29: end for

30:end procedure

###### Proof of Lemma 4.4.1.

The algorithm clears runs in $\widetilde{O}(\left\lvert P\right\rvert+n^{2})$
time and space.

We now show that in Algorithm 9, for any pair of vertices
$(s,t)\in\mathrm{V}^{2}$, $\pi[s,t]$ is either an $s$-$t$ path with a hop of
$O(h)$ in $G$ or $\perp$, such that for all $p_{0},p_{1}\in P$ such that $c\in
p_{0}$ and $p_{0}\circ p_{1}$ is an $s$-$t$ path, $w(\pi[s,t])<w(p_{0}\circ
p_{1})$.

It is easy to see that $\pi[s,t]$ is not longer than the shortest possible
concatenation of the following three parts:

  * •

A $s$-$c$ path $p_{\textrm{from}}$ such that for some $p\in P$,
$p_{\textrm{to}}$ is part of $p$,

  * •

A $c$-$u$ path $p_{\textrm{to}}$ such that for some $p^{\prime}\in P$,
$p_{\textrm{from}}$ is part of $p^{\prime}$, and

  * •

A $u$-$t$ path $p_{\textrm{other}}\in P$.

Since paths in $P$ has a hop of at most $h$, $\pi[s,t]$ has a hop of at most
$3h=O(h)$. Let $p_{0},p_{1}\in P$ be such that $c\in p_{0}$ and $p_{0}\circ
p_{1}$ is an $s$-$t$ path. Then when $u=p_{0}[\left\lvert
p_{0}\right\rvert]=p_{1}[0]$, $p_{\textrm{from}}={p_{0}}[<c]$,
$p_{\textrm{to}}={p_{0}}[>c]$, and $p_{\textrm{other}}=p_{1}$,
$p_{\textrm{from}}\circ p_{\textrm{to}}\circ p_{\textrm{other}}=p\circ q$.
Therefore, $w(\pi[s,t])\leq w(p_{\textrm{from}}\circ p_{\textrm{to}}\circ
p_{\textrm{other}})=w(p\circ q)$. ∎

####  4.4.2 Type II candidates

For type II candidates, we consider recovering paths the other way around.
Whenever a secondary path from $s$ to $t$ with hop level $j$ gets recovered,
we perform an _extension_ on the pair $(s,t)$. To do this, we enumerate all
other pairs that use the recovered $s$-$t$ path in their recovery, which are
$\\{(x,t)\mid\sum_{j^{\prime}\in[j,i_{h}]}X[x,s,t,j^{\prime}]=1\\}$, for which
we combine the path from $x$ to $s$ and the path from $s$ to $t$, and
$\\{(s,y)\mid\sum_{j^{\prime}\in[j,i_{h}]}X[s,t,y,j^{\prime}]=1\\}$, for which
we combine the path from $s$ to $t$ and the path from $t$ to $y$. The core
observation here is that with high probability,
$\sum_{x\in\mathrm{V},j^{\prime}\in[j,i_{h}]}X[x,s,t,j^{\prime}]$ and
$\sum_{y\in\mathrm{V},j^{\prime}\in[j,i_{h}]}{X[s,t,y,j^{\prime}]}$ are both
$\sum_{j^{\prime}\in[j,i_{h}]}O(n/h_{j^{\prime}})=O(n/h_{j})$. Since recovery
cost $C[s,t,j]=n/h_{j}$, the cost of the extension will be of the same order
as the recovery cost with high probability. Therefore if we can make sure that
we only perform extension exactly once for every secondary path, the total
running time for these extensions will be of the same order as the total
update cost of secondary paths with high probability, which from Lemma 4.18 is
$\widetilde{O}(n^{2.5})$. To ensure that a secondary path only gets extended
once, we recover paths in a similar fashion as Dijkstra’s algorithm: we always
take the shortest unextended secondary path and extend it. The final update
algorithm including both types of candidates is described in Algorithm 10.

Algorithm 10 Final Data Structure: Update

1:function Update

2: Compute $\Pi^{\prime}$ using the Lines 7 to 18 from 5.

3:
$\overline{\Pi^{\prime}}\leftarrow\textsc{UpdateForAllPairsConcatenations}()$

4: $Q=\\{\\}$

5: for $(s,t)\in\mathrm{V}^{2}$ do

6: if $w({\overline{\Pi^{\prime}}}[s,t,i_{h}])<w({\Pi^{\prime}}[s,t])$ then

7: $\Pi_{o}[s,t]\leftarrow\overline{\Pi^{\prime}}[s,t,i_{h}]$

8: $Q\leftarrow Q\cup\\{(s,t)\\}$

9: else

10: $\Pi_{o}[s,t]\leftarrow{\Pi}^{\prime}[s,t]$

11: end if

12: end for

13: $A=\textsc{RandGetShortestPaths}(G,H)$

14: while $Q$ is not empty do

15: $(s,t)\leftarrow\operatorname*{arg\,min}(\\{w(\Pi_{o}[s,t])\mid(s,t)\in
Q\\})$

16: if $w(\Pi_{o}[s,t])<A_{s,t})$ then

17: $Q\leftarrow Q\backslash\\{(s,t)\\}$

18: $j\leftarrow h^{-1}(\left\lvert\Pi_{o}[s,t]\right\rvert)$

19: for $x$ such that $\sum_{j^{\prime}\in[j,i_{h}]}X[x,s,t,j^{\prime}]\geq 1$
do

20: $p\leftarrow\Pi_{o}[x,s]\circ\Pi_{o}[s,t]$

21: if $w(p)<w(\Pi_{o}[x,t])$ then

22: $\Pi_{o}[x,t]\leftarrow p$

23: $Q\leftarrow Q\cup\\{(x,t)\\}$

24: end if

25: end for

26: for $y$ such that $\sum_{j^{\prime}\in[j,i_{h}]}X[s,t,y,j^{\prime}]\geq 1$
do

27: $p\leftarrow\Pi_{o}[s,t]\circ\Pi_{o}[t,y]$

28: if $w(p)<w(\Pi_{o}[s,y])$ then

29: $\Pi_{o}[s,y]\leftarrow p$

30: $Q\leftarrow Q\cup\\{(s,y)\\}$

31: end if

32: end for

33: end if

34: end while

35: for $s,t\in\mathrm{V}$ do

36: $A_{s,t}\leftarrow\min(A_{s,t},w(\Pi_{o}[s,t]))$

37: end for

38: return $A$

39:end function

In order to implement the set $Q$ in $\widetilde{O}(1)$ time per operation and
$\widetilde{O}(\left\lvert Q\right\rvert)$ space, one can use a Fibonacci Heap
similar to the standard Dijkstra’s Algorithm [Dij59, FT87].

The next three lemmas bound the running time.

######  Lemma 4.25.

If a vertex pair $(s,t)\in\mathrm{V}^{2}$ is added to $Q$ at some point of
Algorithm 10 and passes the condition check on Line 16, $(s,t)$ is a secondary
pair.

###### Proof.

From Lemma 3.3, if a vertex pair $(s,t)\in\mathrm{V}^{2}$ passes the condition
check on Line 16, the shortest $s$-$t$ path has a hop at most $H$, and
therefore $(s,t)$ is either primary or secondary.

If $(s,t)$ is primary, then ${\Pi}^{\prime}[s,t]$ is already the shortest
path. Therefore the condition on Line 6 must be false and $\Pi_{o}[s,t]$ gets
assigned to be ${\Pi}^{\prime}[s,t]$ on Line 10. Since $\Pi_{o}[s,t]$ is
already the shortest, the conditions on Line 21 and 28 will never be satisfied
for this pair and therefore $(s,t)$ will never be added to $Q$. Therefore if a
vertex pair $(s,t)\in\mathrm{V}^{2}$ is added to $Q$ at some point of
Algorithm 10, $(s,t)$ is a secondary pair. ∎

######  Lemma 4.26.

Any vertex pair $(s,t)\in\mathrm{V}^{2}$ is extracted from $Q$ at most once.

###### Proof.

If a vertex pair $(s,t)\in\mathrm{V}^{2}$ is extracted from $Q$,
$w(\Pi_{o}[s,t])$ is the shortest among all $(s,t)\in Q$. Since the edge
weights are non-negative, all future addition to $Q$ will be some pair of
vertices $(s^{\prime},t^{\prime})$ with $w(\Pi_{o}[s^{\prime},t^{\prime}])\geq
w(\Pi_{o}[s,t])$. However, one needs an improvement on $\Pi_{o}[s,t]$ to add
$(s,t)$ to $Q$ again, which is not possible. Therefore, any vertex pair
$(s,t)\in\mathrm{V}^{2}$ is extracted from $Q$ at most once. ∎

######  Lemma 4.27.

Algorithm 10 runs in $\widetilde{O}(n^{2.5})$ time with high probability.

###### Proof.

If the condition on 16 is satisfied for a vertex pair
$(s,t)\in\mathrm{V}^{2}$, from Lemma 4.25, $(s,t)$ is a secondary pair.
$(s,t)$ will only be extended once due to Lemma 4.26. Let $j$ be the hop level
of the shortest $s$-$t$ path. Since the number of candidates for $x$ and $y$
on Line 19 and Line 26 is
$\sum_{j^{\prime}\in[j,i_{h}]}O(n/h_{j^{\prime}})=O(n/h_{j})$ with high
probability, the running time for its extension will be
$\widetilde{O}(n/h_{j})$ with high probability. Since the update cost
$C[s,t,j]=n/h_{j}$, with high probability, the total running time inside the
condition on 16 is no more than the total update cost of the secondary paths
up to a logarithmic factor, which from Lemma 4.18 is $\widetilde{O}(n^{2.5})$.

It is easy to verify that the rest of Algorithm 10 runs in
$\widetilde{O}(n^{2.5})$ time. Therefore, the running time of Algorithm 10 is
$\widetilde{O}(n^{2.5})$ with high probability. ∎

The next lemma proves the correctness.

######  Lemma 4.28.

With high probability, at the end of Algorithm 10, for every
$(s,t)\in\mathrm{V}^{2}$ such that the shortest $s$-$t$ path has a hop at most
$H$, ${\Pi_{o}}[s,t]$ is the shortest $s$-$t$ path, and for every
$(s,t)\in\mathrm{V}^{2}$, $A_{s,t}$ is the length of the shortest $s$-$t$
path.

###### Proof.

We do induction on the hop of the shortest paths. Let $(s,t)\in\mathrm{V}^{2}$
be such that the shortest $s$-$t$ path has a hop of $h^{\prime}\leq H$.
Suppose that for every other $(s^{\prime},t^{\prime})\in\mathrm{V}^{2}$ such
that the shortest $s^{\prime}$-$t^{\prime}$ path has a hop less than
$h^{\prime}$, ${\Pi_{o}}[s^{\prime},t^{\prime}]$ is the shortest
$s^{\prime}$-$t^{\prime}$ path at the end of Algorithm 10.

Let $j=h^{-1}(h^{\prime})$. From a similar argument as the one employed in the
proof of Lemma 4.9, with high probability there is some candidate
$v\notin(s,t)$ such that $X[s,v,t,j]=1$ and the concatenation of the shortest
$s$-$v$ path and the shortest $v$-$t$ path is the shortest $s$-$t$ path.

If $v$ is a type I candidate, from Lemma 4.24,
$\overline{\Pi^{\prime}}[s,t,i_{h}]$ is the shortest $s$-$t$ path and
$\Pi_{o}[s,t]$ will be assigned to this path on Line 7. It is easy to see that
$\Pi_{o}[s,t]$ will remain the shortest $s$-$t$ path for the rest of the
procedure.

If $v$ is a type II candidate, then one of $(s,v)$ and $(v,t)$ is secondary.
Since both the shortest $s$-$v$ path and the shortest $v$-$t$ path have a hop
smaller than $h^{\prime}$, by assumption, $\Pi_{o}[s,v]$ is the shortest
$s$-$v$ path and $\Pi_{o}[v,t]$ is the shortest $v$-$t$ path at the end of the
procedure. Without loss of generality suppose that $\Pi_{o}[s,v]$ gets
assigned to be the shortest $s$-$v$ path after $\Pi_{o}[v,t]$ gets assigned to
be the shortest $v$-$t$ path. Since one of $(s,v)$ and $(v,t)$ is secondary
and a primary path always gets assigned to be the shortest path on Line 10
before any secondary paths are recovered, $(s,v)$ is secondary. Therefore
$\Pi^{\prime}[s,v]$ is not the shortest $s$-$v$ path, and therefore
$\Pi_{o}[s,v]$ must have been assigned to be the shortest $s$-$v$ path on Line
7, 22 or 29, any of which would have led to $(s,v)$ being added to $Q$. Since
the shortest $s$-$v$ path has a hop smaller than $h^{\prime}\leq H$, it passes
the condition check on Line 16 and therefore $(s,v)$ must have been extended
at some point in the algorithm. When $(s,v)$ was extended, since
$X[s,v,t,j]=1$ and $h^{-1}(\left\lvert\Pi_{o}[s,v]\right\rvert)\leq j$, we
must have used $\Pi_{o}[s,v]\circ\Pi_{o}[v,t]$ to update $\Pi_{o}[s,t]$ inside
the for loop starting on Line 26. Since we assumed that $\Pi_{o}[s,v]$ becomes
the corresponding shortest path after $\Pi_{o}[v,t]$. When we extend $(s,v)$,
both $\Pi_{o}[s,v]$ and $\Pi_{o}[v,t]$ are already the corresponding shortest
paths. Thus, $\Pi_{o}[s,t]$ will be assigned to be the shortest $s$-$t$ path
on Line 29. It is easy to see that $\Pi_{o}[s,t]$ will remain the shortest
$s$-$t$ path for the rest of the procedure.

Therefore, for every $(s,t)\in\mathrm{V}^{2}$ such that the shortest $s$-$t$
path has a hop at most $H$, ${\Pi_{o}}[s,t]$ is the shortest $s$-$t$ path.
From a similar argument as the one in the proof of Lemma 4.11, with high
probability, for every $(s,t)\in\mathrm{V}^{2}$, $A_{s,t}$ is the length of
the shortest $s$-$t$ path. ∎

###  4.5 Space Efficiency and Tie-breaking

####  4.5.1 Space Efficiency

There are two major obstacles to achieving space efficiency. Firstly we need
to implement the random variables $X[*,*,*,*]$ within $\widetilde{O}(n^{2})$
space while still being able to implement all operations involving these
random variables efficiently. Secondly, we need to efficiently store the paths
involved in our algorithm while still being able to access the nodes in order
efficiently as required in Section 3.1.

To achieve space efficiency we have to implement the random variables
$X[*,*,*,*]$ within $\widetilde{O}(n^{2})$ space while still being able to
implement all operations involving these random variables efficiently. Instead
of keeping the random variables constant throughout the update procedure,
every time we access the random variable $X[s,v,t,j]$ for
$(s,v,t,j)\in\mathrm{V}^{3}\times[0,i_{h}]$, we resample the 0-1 random
variable to be $1$ with probability
$\frac{100\log_{2}{n}}{h_{j}}=\widetilde{O}(1/h_{j})$.

At the end of the update procedure, the random variables take values sampled
at different times. To prove correctness, at each update, for each
$(s,v,t,j)\in\mathrm{V}^{3}\times[0,i_{h}]$, we take a _snapshot_ of
$X[s,v,t,j]$ which is equal to the value of this random value at some time in
the update procedure. The way to take the snapshot is as follows:

  * •

If the hop level of the shortest $s$-$t$ path is not $j$, or if the shortest
$s$-$t$ path is not the concatenation of the shortest $s$-$v$ path and the
shortest $v$-$t$ path, take the snapshot arbitrarily.

  * •

If both $(s,v)$ and $(v,t)$ are primary (i.e. $v$ is a type I candidate), let
the snapshot be the value sampled on Line 2 of Algorithm 8.

  * •

If at least one of $(s,v)$ and $(v,t)$ is secondary (i.e. $v$ is a type II
candidate), if in Algorithm 10, $(s,v)$ gets assigned to be the shortest
$s$-$v$ path after $(v,t)$ gets assigned to be the shortest $v$-$t$ path, let
the snapshot be the value sampled on Line 26 in Algorithm 10, otherwise let
the snapshot be the value sampled on Line 19 in Algorithm 10.

It is easy to see that the execution of our update algorithm is correct as
long as it would be correct if random variables were pre-sampled to be equal
to their snapshots at the start of the execution and remained the same
throughout the execution. Since the snapshots have the same distribution as
the random variables themselves, and the pre-sample algorithm has been shown
to be correct, the new sample-on-the-spot algorithm is also correct.

Clearly, this new implementation can be done in $\widetilde{O}(n^{2})$ space
as we do not need to store any information. To tackle the operations involving
these random variables efficiently, we note that there are two types of
operations we need to implement:

  * •

Type I: given some $(s,t,j)\in\mathrm{V}^{2}\times[0,i_{h}]$, efficiently
enumerate all $v$ such that $X[s,v,t,j]=1$. (e.g. Line 2 of Algorithm 8).

  * •

Type II: given some $(s,t,j)\in\mathrm{V}^{2}\times[0,i_{h}]$, efficiently
enumerate all $v$ such that
$\sum_{j^{\prime}\in[j,i_{h}]}X[s,v,t,j^{\prime}]\geq 1$. (e.g. Line 26 of
Algorithm 10, with parameters in a different order).

Since we now resample the random variables on the spot, the Type I operations
ask us to randomly sample a subset of $\mathrm{V}$ where each vertex is
sampled with probability $\frac{100\log_{2}{n}}{h_{j}}$, and the Type II
operations ask us to randomly sample a subset of $\mathrm{V}$ where each
vertex is sampled with probability
$1-\prod_{j^{\prime}\in[j,i_{h}]}(1-\frac{100\log_{2}{n}}{h_{j^{\prime}}})$.
It is well-known that both operations can be done efficiently with a running
time proportional to the size of the output subset111111For example, by
sampling the subset size from a Poisson distribution and then performing a
sampling without replacement.

To efficiently store the paths involved in our algorithm while still being
able to access the nodes in order efficiently as required in Section 3.1, we
can see that all paths involved in our main algorithm are either of the
following:

  1. 1.

A path on the rooted tree storing the outputs of Algorithm 6.

  2. 2.

A concatenation of two other paths.

To store the first type of path we simply store the pointers to the starting
and ending nodes on the rooted tree. To access the nodes efficiently, we
simply traverse the path on the tree. To efficiently store and access the
second type of path, for each path, if one of the paths being concatenated
contains no edges, the path is simply the other path being concatenated;
otherwise, we simply store two pointers to the two paths that are
concatenated. Since we never point to a path with no edges, we can easily
access the nodes on the second type of path in linear time by recursion.
Finally, to find the length and the hop of a path of the first type, we can
use standard techniques on rooted trees121212The easiest way to do this is
that we can see that the starting and ending nodes for paths involved in the
data structure are always such that one is an ancestor of the other. Therefore
both the hop and the length are simply the difference between the hops and the
lengths of two paths starting from the root. We can simply store the hops of
lengths of paths from the root to all nodes on the tree in $O(n)$ space and
answer the queries in $O(1)$ time. . To be able to find the length and the hop
of a path of the second type in $O(1)$ time, we can simply use $O(1)$ space
per path to store the hop and length of each path, and every time we
concatenate two paths in the data structure, we compute the hop and the length
of the new path as the sum of the hops and lengths of the two paths being
concatenated.

The other parts of our data structure can clearly be implemented using
$\widetilde{O}(n^{2})$ space.

####  4.5.2 Tie-Breaking

In this paper, we have assumed that for every $h$, the $h$-hop shortest paths
are unique. Previously in [DI04], a way of achieving this uniqueness even in
the deterministic case without loss of efficiency for shortest paths is
introduced by using “extended weights.” Since our algorithm is randomized, we
will use a more straightforward randomized method based on random
perturbation. The perturbation is introduced in the following way: for each
edge $e$ of weight $w$, we change its weight to

$w\times n^{10}+n^{9}+\lambda(e),$

where $\lambda(e)$ is a uniformly random integer in $[0,n^{8})$. We call a
rebuild “major” if the entire data structure is rebuilt from the top layer.
Our algorithm’s major rebuilds are $\Theta(n^{0.5})$ updates apart. At each
major rebuild, we re-introduce random perturbation on every edge present on
the graph. The perturbation is erased at the next major rebuild before new
perturbation is introduced.

It is easy to see that a hop-restricted shortest path in the new graph must be
a corresponding hop-restricted shortest path in the original graph. We will
show that with high probability the hop-restricted shortest paths are unique.
For every $(s,t,h)\in\mathrm{V}^{2}\times[0,n-1]$, let $d[s,t,h]$ be length of
the shortest $s$-$t$ path with a hop of exactly $h$. We have the following:

######  Lemma 4.29.

For any given graph $G$, if we perturb the edge weights in the manner above,
with a probability of $1-n^{-3}$, for every
$(s,t,h)\in\mathrm{V}^{2}\times[1,n-1]$, there is only one vertex $t^{prime}$
such that $d[s,t^{\prime},h-1]+w(t^{\prime},t)=d[s,t,h]$.

###### Proof.

Given $(s,t,h)\in\mathrm{V}^{2}\times[1,n-1]$, note that from our
perturbation, the values $\\{(d[s,t^{\prime},h-1]+w(t^{\prime},t))\mod
n^{8}\mid t\in\mathrm{V}\backslash t^{\prime}\\}$ are $n-1$ uniformly random
integers in $[0,n^{8})$, and the probability that these $n-1$ random integers
are distinct is at least $1-1/n^{6}$. If the values
$\\{(d[s,t^{\prime},h-1]+w(t^{\prime},t))\mod n^{8}\mid
t\in\mathrm{V}\backslash t^{\prime}\\}$ are distinct, the values
$\\{d[s,t^{\prime},h-1]+w(t^{\prime},t)\mid t\in\mathrm{V}\backslash
t^{\prime}\\}$ must also be distinct and therefore there is only one minimum.

The claim follows from union bound over all $n^{2}(n-1)\leq n^{3}$ tuples. ∎

Now we prove that with high probability the hop-restricted shortest paths are
unique.

######  Lemma 4.30.

For any given graph $G$, if we perturb the edge weights in the manner above,
with a probability of $1-n^{-3}$, for every
$(s,t,h)\in\mathrm{V}^{2}\times[1,n-1]$, the shortest $h$-hop-restricted
$s$-$t$ path is unique.

###### Proof.

We argue that as long as the condition in Lemma 4.29 holds, for every
$(s,t,h)$, the shortest $h$-hop-restricted $s$-$t$ path is unique.

Suppose for some $(s,t,h)\in\mathrm{V}^{2}\times[1,n-1]$ there are two
distinct shortest $h$-hop-restricted $s$-$t$ paths $p_{0}$ and $p_{1}$. By the
way we perturb the edge weights, $\left\lvert
p_{0}\right\rvert=\left\lfloor(w(p_{0})\mod
n^{10})/n^{9}\right\rfloor+1=\left\lfloor(w(p_{1})\mod
n^{10})/n^{9}\right\rfloor+1=\left\lvert p_{1}\right\rvert$. Suppose
$i\in[1,\left\lvert p_{0}\right\rvert-1]$ is the index such that $p_{0}[i]\neq
p_{1}[i]$ and $p_{0}[i+1,\left\lvert p_{0}\right\rvert]=p_{1}[i+1,\left\lvert
p_{1}\right\rvert]$. Let $t^{\prime}=p_{0}[i+1]=p_{1}[i+1]$. We have
$d[s,t^{\prime},i+1]=w(p_{0}[0,i+1])=d[s,p_{0}[i],i]+w(p_{0}[i],t^{\prime})$
and
$d[s,t^{\prime},i+1]=w(p_{1}[0,i+1])=d[s,p_{1}[i],i]+w(p_{1}[i],t^{\prime})$,
which is a contradiction of the condition in Lemma 4.29.

Since Lemma 4.29 hold with $1-n^{-3}$ probability, with $1-n^{-3}$
probability, for every $(s,t,h)\in\mathrm{V}^{2}\times[0,n-1]$, the shortest
$h$-hop-restricted $s$-$t$ path is unique. ∎

######  Lemma 4.31.

The uniqueness condition holds for all graphs involved in the data structure
between two major rebuilds with probability at least $1-1/\Omega(n^{1.49})$.

###### Proof.

Between major rebuilds, there are $O(n^{0.5})$ updates, and for each update,
we rebuild $O(\log n)$ layers, and therefore there are
$\widetilde{O}(n^{0.5})$ rebuilds. Each rebuild involves $\widetilde{O}(n)$
sub-graphs for which we need to ensure that the uniqueness condition holds.
Therefore by the union bound, the uniqueness condition holds for all these
graphs with probability at least $1-1/\Omega(n^{1.49})$. ∎

## References

  * [AC13] Ittai Abraham and Shiri Chechik.  Dynamic decremental approximate distance oracles with $(1+\varepsilon,2)$ stretch.  07 2013.
  * [ACG12] Ittai Abraham, Shiri Chechik, and Cyril Gavoille.  Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels.  pages 1199–1217, 05 2012.  doi:10.1145/2213977.2214084.
  * [ACK17] Ittai Abraham, Shiri Chechik, and Sebastian Krinninger.  Fully dynamic all-pairs shortest paths with worst-case update-time revisited.  In SODA, 2017.
  * [ACT14] I. Abraham, S. Chechik, and K. Talwar.  Fully dynamic all-pairs shortest paths: Breaking the o(n) barrier.  Leibniz International Proceedings in Informatics, LIPIcs, 28:1–16, 09 2014.  doi:10.4230/LIPIcs.APPROX-RANDOM.2014.1.
  * [AISN90] Giorgio Ausiello, Giuseppe F. Italiano, Alberto Marchetti Spaccamela, and Umberto Nanni.  Incremental algorithms for minimal length paths.  In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’90, page 12–21, USA, 1990. Society for Industrial and Applied Mathematics.
  * [Ber09] Aaron Bernstein.  Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time.  pages 693–702, 10 2009.  doi:10.1109/FOCS.2009.16.
  * [Ber16] Aaron Bernstein.  Maintaining shortest paths under deletions in weighted directed graphs.  SIAM Journal on Computing, 45:548–574, 01 2016.  doi:10.1137/130938670.
  * [BGS22] Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak.  Deterministic decremental sssp and approximate min-cost flow in almost-linear time.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1000–1008. IEEE, 2022.
  * [BHS02] Surender Baswana, Ramesh Hariharan, and Sandeep Sen.  Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths.  pages 117–123, 01 2002.  doi:10.1145/509927.509928.
  * [BHS03] Surender Baswana, Ramesh Hariharan, and Sandeep Sen.  Maintaining all-pairs approximate shortest paths under deletion of edges.  In SODA ’03, 2003.
  * [Che18] Shiri Chechik.  Near-optimal approximate decremental all pairs shortest paths.  pages 170–181, 10 2018.  doi:10.1109/FOCS.2018.00025.
  * [Chu21] Julia Chuzhoy.  Decremental all-pairs shortest paths in deterministic near-linear time, 09 2021.
  * [CQ18] Chandra Chekuri and Kent Quanrud.  Randomized mwu for positive lps.  In SODA, 2018.
  * [CZ] Shiri Chechik and Tianyi Zhang.  Faster Deterministic Worst-Case Fully Dynamic All-Pairs Shortest Paths via Decremental Hop-Restricted Shortest Paths, pages 87–99.  URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch4, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch4, doi:10.1137/1.9781611977554.ch4.
  * [DI02] Camil Demetrescu and Giuseppe Italiano.  Improved bounds and new trade-offs for dynamic all pairs shortest paths.  pages 633–643, 07 2002.  doi:10.1007/3-540-45465-9_54.
  * [DI04] Camil Demetrescu and Giuseppe Italiano.  A new approach to dynamic all pairs shortest paths.  J. ACM, 51:968–992, 01 2004.  doi:10.1145/780542.780567.
  * [DI06] Camil Demetrescu and Giuseppe Italiano.  Fully dynamic all-pairs shortest paths with real weights.  Journal of Computer and System Sciences, 72:813–837, 08 2006.  doi:10.1016/j.jcss.2005.05.005.
  * [Dij59] E. W. Dijkstra.  A note on two problems in connexion with graphs.  Numerische Mathematikn, 1:269–271, 1959.
  * [EFHGWN21] Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen.  Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 64:1–64:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2021/14133, doi:10.4230/LIPIcs.ICALP.2021.64.
  * [ES81] Shimon Even and Yossi Shiloach.  An on-line edge-deletion problem.  J. ACM, 28:1–4, 1981.
  * [Flo62] Robert W. Floyd.  Algorithm 97: Shortest path.  Commun. ACM, 5(6):345, jun 1962.  doi:10.1145/367766.368168.
  * [FR06] Jittat Fakcharoenphol and Satish Rao.  Planar graphs, negative weight edges, shortest paths, and near linear time.  Journal of Computer and System Sciences, 72:868–889, 08 2006.  doi:10.1016/j.jcss.2005.05.007.
  * [FT87] M. L. Fredman and R. E. Tarjan.  Fibonacci heaps and their uses in improved network optimization algorithms.  Journal of the ACM, 34(3):596–615, 1987.
  * [GWN20a] Maximilian Probst Gutenberg and Christian Wulff-Nilsen.  Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler, pages 2522–2541.  2020\.  URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.154, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611975994.154, doi:10.1137/1.9781611975994.154.
  * [GWN20b] Maximilian Probst Gutenberg and Christian Wulff-Nilsen.  Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds, pages 2562–2574.  SIAM, 2020.  URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.156, doi:10.1137/1.9781611975994.156.
  * [HK01] Monika Henzinger and Valerie King.  Maintaining minimum spanning forests in dynamic graphs.  SIAM Journal on Computing, 31, 10 2001.  doi:10.1137/S0097539797327209.
  * [HKN16] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai.  Dynamic approximate all-pairs shortest paths: Breaking the $o(mn)$ barrier and derandomization.  SIAM Journal on Computing, 45:947–1006, 01 2016.  doi:10.1137/140957299.
  * [HKRS97] Monika Henzinger, Philip Klein, Satish Rao, and Sairam Subramanian.  Faster shortest-path algorithms for planar graphs.  J. Comput. Syst. Sci., 55:3–23, 08 1997.  doi:10.1006/jcss.1997.1493.
  * [Joh77] Donald B. Johnson.  Efficient algorithms for shortest paths in sparse networks.  Journal of the ACM (JACM), 24:1 – 13, 1977.
  * [Kar21] Adam Karczmarz.  Fully dynamic algorithms for minimum weight cycle and related problems.  In International Colloquium on Automata, Languages and Programming, 2021.
  * [Kin99] Valerie King.  Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs.  Foundations of Computer Science, 1975., 16th Annual Symposium on, 09 1999.  doi:10.1109/SFFCS.1999.814580.
  * [KL] Adam Karczmarz and Jakub Lacki.  Simple Label-Correcting Algorithms for Partially Dynamic Approximate Shortest Paths in Directed Graphs, pages 106–120.  URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611976014.15, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611976014.15, doi:10.1137/1.9781611976014.15.
  * [KL19] Adam Karczmarz and Jakub Lacki.  Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs.  In ESA, 2019.
  * [KS98] P. Klein and S. Subramanian.  A fully dynamic approximation scheme for shortest paths in planar graphs.  Algorithmica, 22:235–249, 11 1998.  doi:10.1007/PL00009223.
  * [KT01] Valerie King and Mikkel Thorup.  A space saving trick for directed dynamic transitive closure and shortest path algorithms.  volume 2108, pages 268–277, 08 2001.  doi:10.1007/3-540-44679-6_30.
  * [Roy59] Bernard Roy.  Transitivité et connexité.  C. R. Acad. Sci. Paris (in French), (249):216–218, 1959.
  * [RZ04a] Liam Roditty and Uri Zwick.  Dynamic approximate all-pairs shortest paths in undirected graphs.  Foundations of Computer Science, 1975., 16th Annual Symposium on, 41, 05 2004.  doi:10.1109/FOCS.2004.22.
  * [RZ04b] Liam Roditty and Uri Zwick.  On dynamic shortest paths problems.  volume 61, 05 2004.  doi:10.1007/978-3-540-30140-0_52.
  * [Tho04] Mikkel Thorup.  Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles.  pages 384–396, 07 2004.  doi:10.1007/978-3-540-27810-8_33.
  * [Tho05] Mikkel Thorup.  Worst-case update times for fully-dynamic all-pairs shortest paths.  pages 112–119, 01 2005.  doi:10.1145/1060590.1060607.
  * [UY91] Jeffrey Ullman and Mihalis Yannakakis.  High-probability parallel transitive-closure algorithms.  SIAM J. Comput., 20:100–125, 02 1991.  doi:10.1145/97444.97686.
  * [vdBN19] Jan van den Brand and Danupon Nanongkai.  Dynamic approximate shortest paths and beyond: Subquadratic and worst-case update time.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 436–455, 2019.  doi:10.1109/FOCS.2019.00035.
  * [War62] Stephen Warshall.  A theorem on boolean matrices.  J. ACM, 9(1):11–12, jan 1962.  doi:10.1145/321105.321107.
  * [Wil14] Ryan Williams.  Faster all-pairs shortest paths via circuit complexity.  STOC ’14, page 664–673, New York, NY, USA, 2014. Association for Computing Machinery.  doi:10.1145/2591796.2591811.