# Early Lessons from a Voice-Only Interface for Finding Movies

Joshua Wissbroecker  University of Minnesota<EMAIL_ADDRESS>,  F. Maxwell
Harper  0000-0003-0552-5773 University of Minnesota<EMAIL_ADDRESS>and

(2018)

###### Abstract.

The current generation of streaming media players often allow users to speak
commands (e.g., users can change the TV channel by pressing a button and
saying “ESPN”). However, these devices typically support a narrow range of
control- and search-oriented commands, and do not support deeper
recommendation or exploration queries. To study spoken natural language
interactions with recommenders, we have built MovieLens TV, a movie
recommender system with no input modalities except voice. In this poster, we
describe MovieLens TV, with a focus on lessons learned building a prototype
system around an off-the-shelf Amazon Echo.

recommender systems; natural language; virtual assistants.

††journalyear: 2018††conference: Late-Breaking Results track part of the
Twelfth ACM Conference on Recommender Systems; October 2–7, 2018; Vancouver,
BC, Canada††booktitle: Late-Breaking Results track part of the Twelfth ACM
Conference on Recommender Systems (RecSys ’18), October 2–7, 2018, Vancouver,
BC, Canada††isbn: ††doi: ††copyright: rightsretained

##  1\. Introduction

As voice recognition continues to improve, voice user interfaces are becoming
more capable and pervasive. As recommender systems researchers, it is exciting
to consider the potential for rich user interactions from voice input. For
example, recent work (Kang et al., 2017) found that users issue a broad range
of queries when interacting with a natural language recommender. However, the
current generation of voice-controlled streaming devices emphasize a small set
of command- and search-oriented commands over a deeper recommendation
experience.

To study voice user interfaces for recommendation, we built a prototype system
called MovieLens TV using web technologies and an Amazon Echo. This system
offers no input modalities except for speech. It presents responses on-screen
and using voice output; it incorporates a recommendation engine to personalize
the display of results. This poster paper describes the architecture of
MovieLens TV and several challenges to developing voice user interfaces for
recommender systems using current off-the-shelf hardware.

Figure 1. Screenshots of the MovieLens TV interfaces: the explore view (top)
and the details view (bottom). Because there are no available input modalities
except for voice, we label available actions in the interface in quotes (e.g.,
“go back”).

##  2\. MovieLens TV System

MovieLens TV is a prototype system that requires no custom hardware — it can
be run with an Amazon Echo and a web browser. To use the system, a user must
install and sign in to our custom Alexa skill on the Echo. After this one-time
setup, the user opens the app in a web browser and says “Alexa, open
MovieLens” to launch the voice interface. At this point, the user may begin
sending requests, prefixed by “Alexa”, to ensure that the Echo is listening.
For example, the user might say “Alexa, show action movies”, followed by
“Alexa, show me more”.

For user testing, we only allow users to drive the user interface by voice
(i.e., we do not allow the user to navigate using a mouse, keyboard, or remote
control). To achieve this, we developed the architecture shown in Figure 2.
Central to this architecture is the idea that the MovieLens TV server pushes
WebSocket messages to the client, which uses JavaScript to render views. The
MovieLens server internally maintains the state of each user, supporting
queries like “play the trailer” (which requires knowledge of the currently-
displayed movie), or “show more” (which requires knowledge of the previous
search).

Figure 2. MovieLens TV system architecture. (1) The user speaks a request to
the Echo (“Alexa, I’m looking for futuristic movies”). (2) The Echo sends the
audio to Amazon’s Alexa API, where we have created a skill. (3) Amazon sends
the transcribed text of the query to our server as unstructured text. (4) Our
server sends the text to wit.ai, which returns a structured representation of
the text, including an intent and other extracted features. (5) Our server
uses the structured representation of the request to determine an action to
take, then retrieves the relevant information, such as recommendations or
movie information. (6) Our server pushes a message to the browser using a
WebSocket, and the browser updates the view. (7) Our server sends a text
response to Amazon. (8) The Echo vocalizes the text response. (6) and (8) are
approximately simultaneous.

MovieLens TV has several views (see Figure 1 for two examples), including an
explore view for displaying movies in a grid, a details view for viewing
information about a movie, and a home/help screen. Simultaneous with showing
the view, the Echo vocalizes a response; we are currently experimenting with
design options. For early testing, we vocalize brief summaries of the action
(e.g., “Here are some movies that I think are futuristic”).

The explore view supports top-N requests (e.g., “show me science fiction
movies”, or “what are some popular comedies?”), as well as related-item
recommendation requests (“show me more like Pitch Black”). We model these two
types of requests as different intents. For top-N requests, unless we detect
an explicit sort order (e.g., “recent”, or “popular”), we rank results using
the MovieLens item-based K-nearest neighbors collaborative filtering
algorithm. For related-item requests, we use a content-based method to rank
the candidates, most similar movies first. For user testing, we instruct users
to first create a personalized profile using the cold start interface in
MovieLens.

##  3\. Challenges and Lessons

Voice triggers. The Echo has two important limitations for researchers wishing
to develop voice-driven systems. First, it requires that each request is
prefixed by an activation word (by default, “Alexa”). In early testing, we
have found that this interrupts users’ natural flow, and is a barrier for
users to engage in a two-way dialogue. Second, since the Echo supports many
commands (not just those related to MovieLens), the user must either
constantly re-open the app, or further prefix queries (“Alexa, ask MovieLens
to show action movies”), further draining the dialogue of its natural
qualities. We address this second limitation with a widely-used hack: we
append a silent audio clip to the end of each response, forcing the connection
to stay open. Unfortunately, this method times out after two minutes, and if
the user has not issued a new query during this window, he or she must again
say “Alexa, open MovieLens”. Ultimately, these challenges make the user
experience much more “request/response” than “conversational”, a limitation to
current voice interfaces identified and discussed in depth in (Porcheron et
al., 2018).

Intent detection. Alexa skills are typically built around Amazon’s own intent
detection process, which is a way of mapping several ways of asking for
something (a goal) to a structured representation including any variables
(i.e., slots) present in the query (Xu and Sarikaya, 2013). However, Amazon’s
method relies on pattern matching, which is not flexible enough to accommodate
the broad range of queries that early testing revealed. We therefore use a
third party intent detection service (wit.ai), which uses supervised machine-
learning to predict user intent. Using this approach has several advantages:
its accuracy improves as we train more example queries, and it is often able
to correctly guess the intent of a query that we have not seen before.
However, we have found that the intent detection approach has some inherent
limitations, such as disambiguating between and/or, and determining when the
user is attempting to build on the current set of results rather than starting
a fresh query. Mapping natural language to recommendation tasks using intent
detection or other approaches is an open challenge for researchers.

##  4\. Next Steps

In early user testing, we have found that MovieLens TV is a minimum viable
product with many areas for improvement. Users are not familiar with the
voice-only input modality, and find it helpful to see example queries on the
screen. These hints, although they assist in usability, may limit users’
creativity in formulating their own requests. Users are surprised at the range
of queries they can express. Equally surprising, however, are the many cases
where the system can break, often due to transcription errors: it is still
difficult to accurately transcribe some actors’ names or movie titles.

We are currently conducting a user study to learn more about the possibilities
and challenges involved with developing voice user interfaces for recommender
systems. We are excited to learn more about users’ expectations concerning
voice-based recommendations, to document the most prominent failure cases, and
to continue working towards more effective recommendation technology.

##  5\. Acknowledgments

This material is based on work supported by the National Science Foundation
under grant IIS-1319382, by a grant from Amazon, and by the University of
Minnesota’s Undergraduate Research Opportunities Program.

## References

  * (1)
  * Kang et al. (2017) Jie Kang, Kyle Condiff, Shuo Chang, Joseph A. Konstan, Loren Terveen, and F. Maxwell Harper. 2017\.  Understanding How People Use Natural Language to Ask for Recommendations. In _Proceedings of the Eleventh ACM Conference on Recommender Systems_ _(RecSys ’17)_. ACM, New York, NY, USA, 229–237.  https://doi.org/10.1145/3109859.3109873
  * Porcheron et al. (2018) Martin Porcheron, Joel E. Fischer, Stuart Reeves, and Sarah Sharples. 2018.  Voice Interfaces in Everyday Life. In _Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems_ _(CHI ’18)_. ACM, New York, NY, USA, 640:1–640:12.  https://doi.org/10.1145/3173574.3174214
  * Xu and Sarikaya (2013) P. Xu and R. Sarikaya. 2013\.  Convolutional neural network based triangular CRF for joint intent detection and slot filling. In _2013 IEEE Workshop on Automatic Speech Recognition and Understanding_. 78–83.  https://doi.org/10.1109/ASRU.2013.6707709


# Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space
Bounds

Maximilian Probst Gutenberg BARC, University of Copenhagen, Universitetsparken
5, Copenhagen 2100, Denmark, The author is supported by Basic Algorithms
Research Copenhagen (BARC), supported by Thorup’s Investigator Grant from the
Villum Foundation under Grant No. 16582. Christian Wulff-Nilsen Department of
Computer Science, University of Copenhagen. This research is supported by the
Starting Grant 7027-00050B from the Independent Research Fund Denmark under
the Sapere Aude research career programme.

###### Abstract

Given a directed weighted graph $G=(V,E)$ undergoing vertex insertions _and_
deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data
structure that processes updates efficiently and returns after each update the
distance matrix to the current version of $G$. In two breakthrough results,
Italiano and Demetrescu [STOC ’03] presented an algorithm that requires
$\tilde{O}(n^{2})$ _amortized_ update time, and Thorup showed in [STOC ’05]
that _worst-case_ update time $\tilde{O}(n^{2+3/4})$ can be achieved. In this
article, we make substantial progress on the problem. We present the following
new results:

  * •

We present the first deterministic data structure that breaks the
$\tilde{O}(n^{2+3/4})$ worst-case update time bound by Thorup which has been
standing for almost 15 years. We improve the worst-case update time to
$\tilde{O}(n^{2+5/7})=\tilde{O}(n^{2.71..})$ and to
$\tilde{O}(n^{2+3/5})=\tilde{O}(n^{2.6})$ for unweighted graphs.

  * •

We present a simple deterministic algorithm with $\tilde{O}(n^{2+3/4})$ worst-
case update time ($\tilde{O}(n^{2+2/3})$ for unweighted graphs), and a simple
Las-Vegas algorithm with worst-case update time $\tilde{O}(n^{2+2/3})$
($\tilde{O}(n^{2+1/2})$ for unweighted graphs) that works against a non-
oblivious adversary. Both data structures require space $\tilde{O}(n^{2})$.
These are the first exact dynamic algorithms with truly-subcubic update time
_and_ space usage. This makes significant progress on an open question posed
in multiple articles [COCOON’01, STOC ’03, ICALP’04, Encyclopedia of
Algorithms ’08] and is critical to algorithms in practice [TALG ’06] where
large space usage is prohibitive. Moreover, they match the worst-case update
time of the best previous algorithms and the second algorithm improves upon a
Monte-Carlo algorithm in a weaker adversary model with the same running time
[SODA ’17].

##  1 Introduction

The All-Pairs Shortest Paths problem is one of the most fundamental
algorithmic problems and is commonly taught in undergraduate courses to every
Computer Science student. Whilst static algorithms for the problem are well-
known for several decades, the dynamic versions of the problem have recently
received intense attention by the research community. In the dynamic setting,
the underlying graph $G=(V,E)$ undergoes updates, most commonly edge
insertions and/or deletions. Most dynamic All-Pairs Shortest Paths algorithms
can further handle vertex insertions (with up to $n$ incident edges) and/or
deletions.

#### The problem.

In this article, we are only concerned with the fully-dynamic All-Pairs
Shortest Path (APSP) problem with worst-case update time, i.e. given a fully-
dynamic graph $G=(V,E)$, undergoing vertex insertions and deletions, we want
to guarantee minimal update time after each vertex update to recompute the
distance matrix of the new graph. This is opposed to the version of the
problem that allows for amortized update time. Moreover, we focus on space-
efficient data structures and show that our data structures even improve over
the most space-efficient APSP algorithms with amortized update time. We
further point out, that for the fully-dynamic setting, vertex updates are more
general than edge updates, since any edge update can be simulated by a
constant number of vertex updates.

#### Related Work.

The earliest partially-dynamic algorithm to the All-Pairs Shortest Path
problem is most likely the algorithm by Johnson [Joh77] that can be easily
extended to handle vertex insertions in $O(n^{2})$ worst-case update time per
insertion given the distance matrix of the current graph. The first fully-
dynamic algorithm was presented by King [Kin99] with $O(n^{2.5}\sqrt{W\log
n})$ amortized update time per edge insertion/deletion where $W$ is the
largest edge weight building upon a classic data structure for decremental
Single-Source Shortest Paths by Even and Shiloach [E+79]. Later, King and
Thorup [KT01] improved the space bound to $\tilde{O}(n^{2.5}\sqrt{W})$. In
follow-up work by Demetrescu and Italiano [DI02, DI06a], the result was
generalized to real edge weights with the same bounds. In 2004, Demetrescu and
Italiano[DI04] presented a new approach to the All-Pairs Shortest Paths
problems that only requires $\tilde{O}(n^{2})$ amortized update time for
vertex insertions/deletions using $O(n^{3})$ space. Thorup improved and
simplified the approach in [Tho04] and even extended it to handle negative
edge weights. Based on this data structure, he further developed the first
data structure with $\tilde{O}(n^{2+3/4})$ worst-case update time [Tho05] for
vertex insertion/deletions improving over the trivial $O(n^{3})$ worst-case
update time that can be obtained by recomputation. However, his data structure
requires _supercubic_ space in $n$.

Abraham, Chechik and Krinninger [ACK17] showed that using randomization a
Monte Carlo data structure can be devised with worst-case update time
$\tilde{O}(n^{2+2/3})$. For unweighted graphs, they further obtain worst-case
update time $\tilde{O}(n^{2+1/2})$. Both algorithms require $O(n^{3})$ space
since they require a list of size $O(n)$ for each pair of vertices. Both
algorithms work against an oblivious adaptive adversary, that is the adversary
can base the update sequence on the output produced by the algorithm but has
no access to the random choices that the algorithm makes. A drawback of the
algorithm is that if it outputs an incorrect shortest path (which it does with
probability at most $1-n^{-c}$ for some constant $c>0$), the adversary can
exploit the revealed information and compromise the data structure for up to
$n^{1/3}$ updates before their data structure is recomputed.

We also point out that the problem of Approximate All-Pairs Shortest Paths was
solved in various dynamic graph settings [BHS02, DI04, RZ04, Ber09, RZ12,
AC13, Ber16, HKN16, Che18, BN19, PW20]. In the setting of
$(1+\epsilon)$-approximate shortest paths, the best algorithms achieve
amortized update time $\tilde{O}(m/\epsilon)$. However, the only of these
algorithms that gives a better guarantee than the trivial
$\tilde{O}(mn/\epsilon)$ on the worst-case update time is the algorithm in
[BN19] that achieves time $\tilde{O}(n^{2.045}/\epsilon^{2})$ for directed
graphs with positive edge weights relies on fast matrix multiplication.

#### Our results.

We present the first deterministic data structure that breaks Thorup’s
longstanding bound of $\tilde{O}(n^{2+3/4})$ worst-case update time.

######  Theorem 1.1.

Let $G$ be an $n$-vertex directed edge-weighted graph undergoing vertex
insertions and deletions. Then there exists a deterministic data structure
which can maintain distances in $G$ between all pairs of vertices in worst-
case update time $O(n^{19/7}(\log n)^{8/7})$. If the graph is unweighted, the
running time can be improved to $O(n^{2.6}\log n)$.

Further, we present the first algorithm for the fully-dynamic All-Pairs
Shortest Paths problem (even amortized) in weighted graphs that obtains truly
sub-cubic time and space usage at the same time111For small weights, i.e.
weights in $n^{1-\epsilon}$ for some $\epsilon>0$, the algorithm [DI06a] gives
subcubic update time and space, both bound by $\tilde{O}(n^{2.5}\sqrt{W})$.
However, as pointed out in [DI06], real-world graphs often have large edge
weights (for example, the internet graph had largest weight of roughly
$10^{4}$ in 2006). Further, this is also the first algorithm that breaks the
space/update-time product of $\Omega(n^{5})$ which stood up to this article
even for unweighted, undirected graphs. We hope that this gives new motivation
to study amortized fully-dynamic algorithms that achieve $\tilde{O}(n^{2})$
update-time _and_ space which is a central open question in the area, posed in
[DI04, Tho04, DI06, Ita08] and has practical importance.

######  Theorem 1.2.

Let $G$ be an $n$-vertex directed edge-weighted graph undergoing vertex
insertions and deletions. Then there exists a deterministic data structure
which can maintain distances in $G$ between all pairs of vertices in worst-
case update time $O(n^{2+3/4}(\log n)^{2/3})$ using space $\tilde{O}(n^{2})$.
If the graph is unweighted, the running time can be improved to
$O(n^{2+2/3}(\log n)^{2/3})$.

Finally, we present a data structure that is randomized and matches the update
times achieved in [ACK17] up to polylogarithmic factors. However, their data
structure is Monte-Carlo, and our data structure uses only $\tilde{O}(n^{2})$
compared to $\tilde{O}(n^{3})$ space and is slightly more robust, i.e. the
data structure in [ACK17] works against an adaptive adversary and therefore
the adversary can base its updates on the output of the algorithm, whilst our
algorithm works against a non-oblivious adversary that is the adversary also
has access to the random bits used throughout the execution of the
algorithm222The former model assumes for example that the adversary cannot use
information about the running time of the algorithm during each update whilst
we do not require this assumption..

######  Theorem 1.3.

Let $G$ be an $n$-vertex directed edge-weighted graph undergoing vertex
insertions and deletions. Then, there exists a Las-Vegas data structure which
can maintain distances in $G$ between all pairs of vertices with update time
$O(n^{2+2/3}(\log n)^{3})$ w.h.p. using space $\tilde{O}(n^{2})$ against a
non-oblivious adversary. If the graph is unweighted, the running time can be
improved to $O(n^{2+1/2}(\log n)^{3})$.

#### Our Techniques.

We focus on the decremental problem that we then generalize to the fully-
dynamic setting using Johnson’s algorithm. The most crucial ingredient of our
new decremental algorithms is a new way to use congestion: for each shortest
path $\pi_{s,t}$ from $s$ to $t$, each vertex on the shortest path is assigned
a congestion value that relates to the costs induced by a deletion of such a
vertex. If a vertex participates in many shortest paths, its deletion is
expensive since we need to restore all shortest paths in which it
participated. Thus, if the congestion of a vertex $v$ accumulated during some
shortest path computations is too large, we simply remove the vertex from the
graph and continue our shortest path computations on the graph
$G\setminus\\{v\\}$. We defer handling the vertices of high congestion to a
later stage and prepare for their deletion more carefully. This differs
significantly from previous approaches that compute all paths in a specific
order to avoid high congestion. Our new approach is simpler, more flexible and
can be used to avoid vertices even at lower thresholds.

The second technique we introduce is to use separators to recompute shortest
paths after a vertex deletion. This allows us to speed up the computation
since we can check fewer potential shortest paths. Since long paths have
better separators, we can reduce the congestion induced by these paths and
therefore reduce the overall amount of congestion on all vertices.

Once we complete our shortest path computations, we obtain the set of highly
congested vertices and handle them using a different approach presented by
Abraham, Chechik and Krinninger [ACK17] that maintains deterministically the
shortest paths through these vertices. These are exactly the shortest paths
that we might have missed in the former step when we removed congested
vertices. Thus, taking the paths of smaller weight, we obtain the real
shortest paths in $G$.

Finally, we present a randomized technique to layer our approach where we use
a low congestion threshold initially to identify uncritical vertices and then
obtain with each level in the hierarchy a smaller set of increasingly critical
vertices that require more shortest path computations on deletion. Since the
sets of critical vertices are decreasing in size, we can afford to invest more
update time in the maintenance of shortest paths through these vertices.

##  2 Preliminaries

We denote by $G=(V,E,w)$ the input digraph where $w$ is the weight function
mapping each edge to a number in the reals and define $n=|V|$ and $m=|E|$. In
this article, we define $H\subseteq G$ to refer to $H$ being a vertex-induced
subgraph of $G$, i.e. $H=G[V\setminus D]$ for some $D\subseteq V$. We also
slightly abuse notation and write $G\setminus D$ for $D\subseteq V$ to denote
$G[V\setminus D]$. We let the graph $H$ with edge directions reversed be
denote by $\overleftarrow{H}$.

The _weight_ of a path $\pi$ in an edge-weighted graph $G$ is the sum of
weights of its edges. We let $w$ denote the weight function that maps each
path in $\pi$ to its weight. We use $\bot$ to denote the empty path of weight
$\infty$. Given two paths $\pi_{1}=\langle u_{1},u_{2},\ldots,u_{p}\rangle$
and $\pi_{2}=\langle v_{1},v_{2}\ldots,v_{q}\rangle$ in $G$ where
$u_{p}=v_{1}$, denote by $\pi_{1}\circ\pi_{2}$ the concatenated path $\langle
u_{1},u_{2}\ldots,u_{p}=v_{1},v_{2},\ldots,v_{q}\rangle$. For any path $\pi$,
we define $\pi\circ\bot=\bot\circ\pi=\bot$.

Let $\pi_{s,t}$ be a path starting in vertex $s$ and ending in vertex $t$.
Then $\pi_{s,t}$ is a _shortest path_ in $G$ if its sum of edge weights is
minimized over all paths from $s$ to $t$ in $G$. We denote the weight of a
shortest path from $s$ to $t$ by $\mathbf{dist}_{G}(s,t)$.

We say $\pi_{s,t}$ is the shortest path from $s$ to $t$ _through_ $C\subset
V$, if $\pi_{s,t}$ is the path of minimum weight from $s$ to $t$ that contains
a vertex in $C$. We further say a path $\pi_{s,t}$ has hop $h$ or is a _$h$
-hop-restricted path_ in $G$ if it consists of at most $h$ edges. We denote by
$\mathbf{dist}_{G}^{h}(s,t)$ the weight of the $h$-hop-restricted shortest
path from $s$ to $t$. Finally, we define the notion of an _improving_ shortest
path $\pi_{s,t}$ in $G$ with regard to $H\subseteq G$ to be a path of weight
at most $\mathbf{dist}_{H}(s,t)$. We often combine these notions, saying, for
example, that $\pi_{s,t}$ is an $h$-hop-improving shortest path through $C$ in
$G$ with respect to $G\setminus D$ to refer to a path $\pi_{s,t}$ that is in
$G$ and has weight at most equal to the shortest path between $s$ and $t$ of
hop $h$ that contains a vertex in $C$ in $G\setminus D$.

In this paper, we often use a black box a result by Zwick [Zwi02] that extends
$h$-hop-improving shortest paths in $G\setminus D$ to improving shortest-
paths. Since the lemma is implicit in [Zwi02] we provide an implementation of
the algorithm and a proof of correctness that can be found in appendix A.

######  Lemma 2.1 (see [Zwi02, ACK17]).

Given a collection $\Pi$ of the $h$-hop-improving shortest paths for all pairs
$(s,t)\in V^{2}$ in $G\setminus D$, then there exists a procedure
$\textsc{DetExtDistances}(\Pi,h)$ that returns improving shortest paths for
all pairs $(s,t)\in V^{2}$ in time $O(n^{3}\log n/h+n^{2}\log^{2}n)$.

##  3 The Framework

In this section, we describe the fundamental approach that we use for our data
structures. We then refine this approach in the next section to obtain our new
data structures. We start by stating a classic reduction that was used in all
existing approaches.

######  Lemma 3.1 (see [HK01, Tho05, ACK17]).

Given a data structure on $G$ that supports a batch deletion of up to
$2\Delta$ vertices $D\subseteq V$ from $G$ such that the data structure
computes for each $(s,t)\in V^{2}$ a shortest path $\pi_{s,t}$ in $G\setminus
D$, and can return the $k$ first edges on $\pi_{s,t}$ in time $O(k)$ time.
Then, if the preprocessing time is $t_{pre}$ and the batch deletion worst-case
time is $t_{del}$, there exists a fully dynamic APSP algorithm with
$O(t_{pre}/\Delta+t_{del}+\Delta n^{2})$ worst-case update time.

This lemma reduces the problem to finding a data structure with good
preprocessing time that can handle batch deletions. To get some intuition on
how the reduction stated above works, note that vertex insertions can be
solved very efficiently.

######  Lemma 3.2 (implied by Johnson’s algorithm, see for example [Cor+09]).

Given a graph $G\setminus C$, where $C\subset V$ of size $\Delta$, and given
all-pairs shortest paths $G\setminus C$, we can compute all-pairs shortest
paths in $G$ in time $O(\Delta n^{2})$.

Therefore, the algorithm can reduce the problem to a decremental problem and
using the shortest paths in $G\setminus(D\cup C)$ insert a batch of vertices
$C\setminus D$ after each update. When $C$ becomes of size larger than
$\Delta$ (i.e. after at least $\Delta$ updates), we recompute the decremental
data structure. Using standard deamortization techniques for rebuilding the
data structure, the preprocessing time can be split into small chunks that are
processed at each update and therefore we obtain a worst-case guarantee for
each update.

###  3.1 A Batch Deletion Data Structure with Efficient Preprocessing Time

In the following, we present a procedure
$\textsc{DetPreprocessing}(G,\tau,h)$, given in Algorithm 1, that is invoked
with parameters $G$ and integers $h>0$ and $\tau\geq 2n^{2}$ to compute paths
$\pi^{i}_{s,t}$ for each tuple $(s,t)\in V^{2}$ and for every $i\in[0,i_{h}]$
with $i_{h}=\lceil\log_{3/2}h\rceil$. Our goal is to use these paths in the
batch deletion to recompute all-pairs shortest paths.

Input: A graph $G=(V,E)$, a positive integer $h>0$ determining the maximum hop
and an integer $\tau\geq 2n^{2}$ regulating the congestion.

Output: A tuple $(C,\\{\textsc{Congestion}(v)\\}_{v\in
V},\\{\pi^{i}_{s,t}\\}_{s,t\in V,i\in\\{0,\ldots,i_{h}\\}})$ with the
properties of Lemma 3.4.

1 $C\leftarrow\emptyset$;

2 foreach  _$v\in V$_ do $\textsc{Congestion}(v)\leftarrow 0$;

3 foreach  _$s,t\in V,i\in[0,i_{h}]$_ do $\pi^{i}_{s,t}\leftarrow\bot$;

4

5$X\leftarrow V$ ;

6 while  _$X\neq\emptyset$_ do

7 Remove an arbitrary root $s$ from $X$;

8

9 foreach  _$i\in[0,i_{h}]$_ do

10 $\\{\pi^{i}_{s,t}\\}_{t\in V}\leftarrow\textsc{BellmanFord}(s,G[V\setminus
C],h_{i})$ ;

11

12 foreach  _$t\in V,u\in\pi^{i}_{s,t}$_ do

13 $\textsc{Congestion}(u)\leftarrow\textsc{Congestion}(u)+\lceil
n/h_{i}\rceil$;

14

15 $C\leftarrow\\{v\in V|\textsc{Congestion}(v)>\tau/2\\}$;

16

17

Algorithm 1 $\textsc{DetPreprocessing}(G,\tau,h)$

This procedure maintains congestion values $\textsc{Congestion}(u)$ for each
$u\in V$. These counters are initially $0$. Let
$i_{h}=\lceil\log_{3/2}h\rceil$ and let $h_{i}=(3/2)^{i}$, for
$i=0,\ldots,i_{h}$ throughout the rest of the article. For each such $i$,
$h_{i}$-hop-restricted shortest paths $\pi^{i}_{s,t}$ in $G$ are computed from
roots $s$ to all $t\in V$ where roots are considered in an arbitrary order.

For each $u\in V$, whenever an $h_{i}$-hop-restricted path $\pi^{i}_{s,t}$ is
found that passes through $u$, $\textsc{Congestion}(u)$ is increased by
$\lceil n/h_{i}\rceil$. Hence, paths of long hop congest vertices on them less
than small hop paths; this is key to getting our update time improvement as it
helps us to keep the amount of congestion at $O(n)$ for a path of _any_ hop
(as opposed to existing techniques which can only bound the cost at $O(nh)$).
Once a congestion value $\textsc{Congestion}(u)$ increases beyond threshold
value $\tau/2$, $u$ is removed from the vertex set. More precisely, a growing
set $C$ keeps track of the set of vertices whose congestion value is above
$\tau/2$ and all hop-restricted paths are computed in the shrinking graph
$G[V\setminus C]$.

######  Lemma 3.3.

The procedure $\textsc{DetPreprocessing}(G,\tau,h)$ can be implemented to run
in $O(n^{3}h)$ time.

###### Proof.

In each iteration of the for-loop in line 1, computing $h_{i}$-hop-restricted
shortest paths from source $s$ to all $t\in V\setminus C$ can be done with
$h_{i}$ iterations of Bellman-Ford from $s$ in $G[V\setminus C]$ in time
$O(n^{2}h_{i})$ time. It is straight-forward to see that this dominates the
cost incurred by the accounting in lines 1 to 1. From this and from a
geometric sums argument, it follows that the total running time over all
sources $s$ is
$O(n\cdot\sum_{i=0}^{\lceil\log_{3/2}h\rceil}n^{2}(3/2)^{i})=O(n^{3}h)$. The
lemma now follows. ∎

To bound the time for updates in the next subsection, we need the following
lemma.

######  Lemma 3.4.

At termination of $\textsc{DetPreprocessing}(G,\tau,h)$, the algorithm ensures
that

  1. 1.

$\forall v\in V$: $\textsc{Congestion}(v)\leq\tau$,

  2. 2.

$\sum_{v\in V}\textsc{Congestion}(v)=O(n^{3}\log h)$, and

  3. 3.

$|C|=O(n^{3}\log h/\tau)$.

  4. 4.

Each computed path $\pi^{i}_{s,t}$ is a _$h_{i}$ -hop-improving shortest path_
in $G$ with regard to $G\setminus C$.

###### Proof.

We first observe that we maintain the loop invariant for the while-loop in
line 1 that the congestion of any vertex not in $C$ is at most $\tau/2$. This
is true since initially the congestion of all vertices is $0$ and at the end
of each iteration, we explicitly remove vertices with congestion larger than
$\tau/2$ from $C$. To prove property 1, it therefore suffices to show that
during an iteration of the while-loop in line 1, the congestion of any vertex
is increased by at most $\tau/2$. To see this, observe that there are at most
$n$ paths under consideration in each iteration of the while loop. Every
vertex $u$ has its congestion increased by $\lceil n/h_{i}\rceil\leq n$ for
each such path it belongs to. Therefore, we add at most $n^{2}\leq\tau/2$
congestion to any vertex $u$ during an iteration of the while-loop.

To see property 2, define $\Phi=\sum_{v\in V}\textsc{Congestion}(v)$.
Initially, $\Phi=0$. Observe that during an iteration of the while-loop in
line 1, we have at most $n$ paths of hop up to $h_{i}$. Thus at most $h_{i}+1$
vertices increase their congestion due to a path by $\lceil n/h_{i}\rceil$ and
so each such path increases $\Phi$ by at most $O(n)$. Thus each while-loop
iteration adds at most $O(n^{2})$ to $\Phi$ and since we execute the while-
loop exactly $n\lceil\log_{3/2}h\rceil$ times, the final value of $\Phi$ is
$O(n^{3}\log h)$.

Property 3 follows since each vertex $c\in C$ has congestion at least
$\tau/2$, implying that there can be at most $2\Phi/\tau=O(n^{3}\log h/\tau)$
vertices in $|C|$. Property 4 follows from the analysis of Bellman-Ford. ∎

The space-efficiency is straight-forward to analyze since each pair $(s,t)\in
V^{2}$ requires one path $\pi^{i}_{s,t}$ to be stored for each
$i\in[0,i_{h}]$, storing the shortest paths explicitly requires space
$O(\sum_{i=0}^{\lceil\log_{3/2}h\rceil}n^{2}(3/2)^{i})=O(n^{2}h)$. We defer
the description of a more space-efficient data structure with the same
guarantees until Section 4.2.

###  3.2 Handling Deletions

In this section, we use the data structure computed by
$\textsc{DetPreprocessing}(G,\tau,h)$ with $C$ being again the set of
congested vertices, and show how to use this data structure to handle a batch
$D\subseteq V$ of at most $2\Delta$ deletions, i.e. we show how to efficiently
compute all-pairs shortest paths in $G\setminus D$. Our update procedure
proceeds in multiple phases $1,\dots,i_{h}$. Throughout the procedure, we
enforce the following invariant.

######  Invariant 3.5.

For every $(s,t)\in V^{2}$ where $\Pi_{s,t}$ is the collection of shortest-
path from $s$ to $t$ in $G\setminus D$, and

  * •

no $\pi_{s,t}\in\Pi_{s,t}$ contains a vertex in $C$, and

  * •

there is some shortest-path $\pi_{s,t}\in\Pi_{s,t}$ of hop at most $h_{i}$.

Then, after the execution of the $i^{th}$ phase, we have that $\pi^{i}_{s,t}$
is a shortest-path in $\Pi_{s,t}$ of minimal hop.

Before we describe how to enforce the invariant, observe that the invariant
implies that after we finished phase $i_{h}$, we have for each pair $(s,t)$ a
$h$-hop-improving shortest path in $G\setminus D$ which can then be extended
using procedure $\textsc{DetExtDistances}(\\{N_{i}\\}_{i},h)$ as described in
Lemma 2.1 to give all-pairs shortest paths in $G\setminus D$, as required.

1 foreach  _$\pi^{0}_{s,t}\cap D\neq\emptyset$_ do

2 $\pi^{0}_{s,t}\leftarrow\bot$

3

4for  _$i\leftarrow 1$ to $i_{h}$_ do

5 foreach  _$s\in V$_ do

6 if  _$h_{i} >3$_ then

7 Compute an integer
$\textsc{Rad}^{i}(s)\in(\frac{1}{3}h_{i},\frac{2}{3}h_{i})$ that minimizes the
size of $\textsc{Separator}^{i}(s)=\\{x\in V\setminus\\{D\cup
C\\}\;|\;|\pi^{i-1}_{s,x}|=\textsc{Rad}^{i}(s)\\}$

8 else

9 $\textsc{Separator}^{i}(s)\leftarrow V$

10

11

12 foreach  _$\pi^{i}_{s,t}\cap D\neq\emptyset$_ do

13 Let $x$ be any vertex in $\textsc{Separator}^{i}(s)\cup\\{t\\}$ such that
for any vertex $y\in\textsc{Separator}^{i}(s)\cup\\{t\\}$, either
$w(\pi^{i-1}_{s,x}\circ\pi^{i-1}_{x,t})<w(\pi^{i-1}_{s,y}\circ\pi^{i-1}_{y,t})$
or
$w(\pi^{i-1}_{s,x}\circ\pi^{i-1}_{x,t})=w(\pi^{i-1}_{s,y}\circ\pi^{i-1}_{y,t})$
and
$|\pi^{i-1}_{s,x}\circ\pi^{i-1}_{x,t}|\leq|\pi^{i-1}_{s,y}\circ\pi^{i-1}_{y,t}|$.

14 $\pi^{i}_{s,t}\leftarrow\pi^{i-1}_{s,x}\circ\pi^{i-1}_{x,t}$

15

return $\textsc{DetExtDistances}(\\{\pi^{i_{h}}_{s,t}\\}_{(s,t)\in
V^{2}},h_{i})$

Algorithm 2 $\textsc{Delete}(D,h)$

Let us now describe how to implement the execution of a phase which is also
depicted in Algorithm 2. Initially, we change all precomputed paths
$\pi^{0}_{s,t}$ with $s$ or $t$ in $D$ to the empty path $\bot$. Clearly, this
enforces Invariant 3.5 and can be implemented in $O(n^{2})$ time.

In the $i^{th}$ phase (for $i>0$), we start by computing for each vertex $s\in
V$, a hitting set of all $h_{i-1}$-hop-improving shortest paths starting in
$s$. We take the separator set $\textsc{Separator}^{i}(s)$ such that in
particular each (real) shortest path from $s$ of length at least
$\frac{2}{3}h_{i}$ contains at least one vertex in $\textsc{Separator}^{i}(s)$
that is at distance $\textsc{Rad}^{i}(s)$ from $s$. Here $\textsc{Rad}^{i}(s)$
is chosen to be between the $(\frac{1}{3}h_{i})^{th}$ and
$(\frac{2}{3}h_{i})^{th}$ vertex on each path (with exception for very small
$h_{i}$ where we chose the separator to be the entire vertex set). Since there
are $\Theta(h_{i})$ layers to chose $\textsc{Rad}^{i}(s)$ from, and the layers
partition the vertex set $V$, we obtain that $\textsc{Separator}^{i}(s)$ is of
size $O(n/h_{i})$ by the pigeonhole principle. Finally, to fix any precomputed
$h_{i}$-hop-improving shortest path $\pi^{i}_{s,t}$ that is no longer in
$G\setminus D$, we check the paths $\pi^{i-1}_{s,x}\circ\pi^{i-1}_{x,t}$ for
each $x\in\textsc{Separator}^{i}(s)\cup\\{t\\}$ and take a path of minimal
weight (and among those of minimal hop). We point out that this path is either
the concatenation of two $h_{i-1}$-hop-improving shortest paths, or the path
$\pi^{i-1}_{s,t}$. This completes the description of our update algorithm.

######  Lemma 3.6.

The Invariant 3.5 is enforced throughout the entire execution of procedure
$\textsc{Delete}(D,h)$.

###### Proof.

Before the loop starts the invariant is clearly enforced since for $i=0$, we
either have an edge between two points or not. Let us therefore take the
inductive step for $i>0$ and let us focus on some path $\pi^{i}_{s,t}$.
Clearly, if $\pi^{i}_{s,t}$ contains no vertex in $D$, it is still
$h_{i}$-hop-improving in $G\setminus D$ and therefore no action is required.
Otherwise, let $\widehat{\pi_{s,t}}$ be some $s$-to-$t$ shortest-path in
$\Pi_{s,t}$ of minimal hop (we assume that no shortest path intersects $C$).
Clearly, if $\widehat{\pi_{s,t}}$ has $|\widehat{\pi_{s,t}}|\leq h_{i-1}$,
then we have by the induction hypothesis that $\pi^{i-1}_{s,t}$ is a shortest-
path from $s$-to-$t$ of minimal hop, and thus if $x=t$, we obtain
$\pi^{i}_{s,t}=\pi^{i-1}_{s,t}$. If $x\neq t$, then the path $\pi^{i}_{s,t}$
is set to another shortest-path of minimal hop by the way we choose $x$.

It remains to consider the case where
$h_{i}\leq|\widehat{\pi_{s,t}}|>h_{i-1}$. Then, let $\hat{x}$ be the
$\textsc{Rad}^{t}(s)^{th}$ vertex on $\widehat{\pi_{s,t}}$ (which exists since
$\textsc{Rad}^{t}(s)<\frac{2}{3}h_{i}=h_{i-1}<|\widehat{\pi_{s,t}}|$). Then,
observe that $\hat{x}\in\textsc{Separator}^{i}(s)\cup\\{t\\}$ since by
induction hypothesis every $s$-to-$\hat{x}$ shortest-path $\pi_{s,\hat{x}}$ of
minimal hop has exactly $\textsc{Rad}^{t}(s)$ hops and $\pi^{i-1}_{s,\hat{x}}$
is chosen among these paths by induction hypothesis (also none of these paths
intersects $C$ since no $s$-to-$t$ shortest-path does). Similarly, we have
that $\pi^{i-1}_{\hat{x},t}$ is a shortest path of minimal hop from $\hat{x}$
to $t$. This implies that the path
$\pi^{i-1}_{s,\hat{x}}\circ\pi^{i-1}_{\hat{x},t}$ is a shortest $s$-to-$t$
path of minimal hop. Since $x$ has $\hat{x}$ among its choices, we thus have
that $\pi^{i}_{s,t}=\pi^{i-1}_{s,{x}}\circ\pi^{i-1}_{{x},t}$ is a shortest
$s$-to-$t$ path of minimal hop. The lemma follows. ∎

######  Lemma 3.7.

Given a data structure that satisfies the properties listed in Lemma 3.4 with
congestion threshold $\tau$ and a set of congested vertices $C$, there exists
an algorithm that computes all-pairs shortest paths in $G\setminus D$ and
returns the corresponding distance matrix in time
$O(|D|\tau+|C|n^{2}+n^{3}\log n/h)$.

###### Proof.

By Invariant 3.5, we obtain all shortest paths of hop at most $h$ for pairs
that have no shortest path through $C$. Thus, it is straightforward to adapt
the procedure described in Lemma 3.2 to return in $O(|C|n^{2})$ time a
collection of $h$-hop-improving shortest paths in $G\setminus D$. Finally, the
Lemma 2.1 can be applied to recover in $O(n^{3}\log n/h)$ time the shortest
paths in $G\setminus D$, as required.

It remains to analyze the running time of Algorithm 2. We note that each phase
requires us to compute a separator for each vertex in $V$. Since returning the
first $h_{i}$ edges of each path $\pi^{i-1}_{s,x}$ requires time $O(h_{i})$
since we represent paths explicitly, the time required to compute a single
separator in phase $i$ is at most $O(nh_{i})$. Thus, the overall time to
compute all separators can be bound by $O(n^{2}h)$ (using a geometric sum
argument for the different phases).

To bound the time spend in the foreach-loop in line 2, observe that we iterate
only over paths that contain a vertex in $D$ which can be detected in linear
time. Observe that if a vertex $v$ in $D$ is on a path $\pi_{s,t}^{i}$, then
the path contributed $\lceil n/h_{i}\rceil$ credits to the congestion of $v$
in the preprocessing procedure. Since the separator of $s$ at phase $i$ has
size $O(n/h_{i})$ by the arguments mentioned above, we have that the iteration
to recover path $\pi_{s,t}^{i}$ requires time $O(n/h_{i})$ (that is since
checking the weight of each path and concatenation can both be implemented in
constant time). Since each vertex $v\in D$ has total congestion at most $\tau$
by Lemma 3.4, we can bound the total running time of the algorithm by
$O(|D|\tau+n^{2}h)$. ∎

Choosing $\tau=n^{2+1/4}\sqrt{\log n},h=n^{1/4}\sqrt{\log n}$ and
$\Delta=n^{1/2}$ in Lemma 3.1, we obtain the following corollary.

######  Corollary 3.8.

Let $G$ be an $n$-vertex directed edge-weighted graph undergoing vertex
insertions and deletions. Then there exists a deterministic data structure
which can maintain distances in $G$ between all pairs of vertices in worst-
case update time $O(n^{2+3/4}\sqrt{\log n})$.

###  3.3 Batch Deletion Data Structure for Unweighted Graphs

We point out that for unweighted graphs, we can replace the Bellman-Ford
procedure by a simple Breath-First-Search procedure (see for example [Cor+09])
which improves the running time from $O(n^{2}h)$ to $O(n^{2})$. This was also
exploited before in [ACK17].

######  Corollary 3.9.

Let $G$ be an $n$-vertex directed edge-weighted graph undergoing vertex
insertions and deletions. Then there exists a deterministic data structure
which can maintain distances in $G$ between all pairs of vertices in worst-
case update time $O(n^{2+2/3}(\log n)^{2/3})$.

In the following sections, we will not explicitly point out that the Bellman-
Ford procedure can be replaced by BFS but simply state the improved bound.

##  4 Efficient Data Structures

We now describe how to use the general strategy described in the previous
section and describe the necessary changes to obtain efficient data
structures.

###  4.1 A Faster Deterministic Algorithm

To obtain a faster algorithm, we mix our framework with the following result
from by Abraham, Chechik and Forster [ACK17]. It is not explicitly stated in
their paper but follows immediately by replacing their randomly sampled vertex
set by an arbitrary vertex set. Informally, the data structure takes a
decremental graph $G$ and a set $C\subseteq V$ of vertices and maintains for
all vertices $v\in V$, the shortest-path through some vertex in $C$.

######  Lemma 4.1.

Given an edge-weighted directed graph $G=(V,E)$, a set $C\subseteq V$ and a
hop bound $h$. Then there exists a deterministic data structure that supports
the operations:

  * •

$\textsc{ACKPreprocessing}(G,C,\Delta^{\prime},h)$: Initializes the data
structure with the given parameters and returns a pointer to the data
structure.

  * •

$\textsc{ACKDelete}(D)$: assuming $D\subseteq V$, returns for each $(s,t)\in
V^{2}$, a $h$-hop-improving shortest path $\pi_{s,t}$ through some vertex in
$C\setminus D$ in $G\setminus D$ (with respect to $G\setminus D$).

The operation $\textsc{ACKPreprocessing}(G,C,h)$ runs in $O(|C|n^{2}h)$ time
and each operation $\textsc{ACKDelete}(D)$ runs in $O(|D|n^{2}h\log n+|C|nh)$
time.

It is now straight-forward to obtain a new batch deletion data structure that
combines these two data structures. Intuitively, we exploit the strengths of
both algorithms by setting the $\tau$-threshold of the algorithm introduced in
previous section slightly lower which increases the size of the set $C$ of
congested vertices but improves the running time of the data structure to
maintain shortest-paths that do not contain any vertices in $C$. Since $C$ is
precomputed, we then use the data structure described above to obtain the
shortest-paths through some vertex in $C$. Let us now give a more formal
description.

To initialize the new data structure, we invoke algorithm 1 with parameters
$\tau$ and $h$ to be fixed later. The algorithm gives a data structure
$\mathcal{D}_{1}$ and a set $C$ is of size $O(n\log n/\tau)$. We then handle
$2\Delta$ updates as follows: At initialization and every $\Delta^{\prime}$
updates, we compute a data structure $\mathcal{D}_{2}$ by invoking the
preprocessing algorithm in Lemma 4.1 with parameters $C$ and $h$. We later
chose $\tau$ larger than in the last section which implies that we can
increase $\Delta$, and take care of the shortest paths through $C$ by
recomputing $\mathcal{D}_{2}$ more often, i.e. we set
$\Delta^{\prime}\ll\Delta$. Since the preprocessing time of $\mathcal{D}_{2}$
is smaller, this can be balanced efficiently such that both have small batch
update time at all times.

For each update, we let $D_{1}$ be the batch of deletions since
$\mathcal{D}_{1}$ was initialized and $D_{2}$ the batch of deletions since
$\mathcal{D}_{2}$ was initialized. We then invoke
$\mathcal{D}_{1}.\textsc{Delete}(D_{1})$ and
$\mathcal{D}_{2}.\textsc{ACKDelete}(D_{2})$ and combine the results in a
straight-forward manner. This concludes the algorithm.

Using the reduction 3.1, and using that $|D_{1}|\leq\Delta$ and
$D_{2}\leq\Delta^{\prime}$, we obtain an algorithm with worst-case running
time

$O(n^{3}h/\Delta+\Delta n^{2}+n^{3}(\log
n)^{2}/h+\Delta\tau+\Delta^{\prime}hn^{2}\log n+n^{4}h(\log
h)/\tau+n^{5}h(\log h)/(\tau\Delta^{\prime}))$

which is optimized by setting $\tau=n^{7/3}h^{2/3}(\log n\log
h)^{1/3}/\Delta^{2/3}$, $h=n^{2/7}(\log n)^{6/7}$,
$\Delta=\sqrt{n}h^{1/4}/(\log n\log h)^{1/4}$, and
$\Delta^{\prime}=\sqrt{n^{3}(\log h)/(\tau\log n)}$.

######  Corollary 4.2.

Let $G$ be an $n$-vertex directed edge-weighted graph undergoing vertex
insertions and deletions. Then there exists a deterministic data structure
which can maintain distances in $G$ between all pairs of vertices in worst-
case update time $O(n^{19/7}(\log n)^{8/7})$. If the graph is unweighted, the
running time can be improved to $O(n^{2.6}\log n)$.

###  4.2 A Simple and Space-Efficient Deterministic Data Structure

In order to reduce space, we replace the procedure
$\textsc{BellmanFord}(s,G[V\setminus C],h_{i})$ in the preprocessing at line 1
by procedure $\textsc{BellmanFordSpaceEfficient}(s,G[V\setminus C],h_{i})$
that is depicted in algorithm 3. Unlike the Bellman-Ford algorithm, our
algorithm does not return the $h_{i}$-restricted shortest paths but instead
returns $h_{i}$-improving shortest paths of length at most $O(h_{i})$. Using
that the length of each $h_{i}$-improving shortest paths is $O(h_{i})$, it can
be verified that the proof of lemma 3.4 still holds under these conditions.
Moreover, the information computed by
$\textsc{BellmanFordSpaceEfficient}(s,H,h_{i})$ can be efficiently stored in
$\tilde{O}(n)$ space.

Input: A graph $H$ and source $s\in H(V)$, an integer $h_{i}=(3/2)^{i}\geq 1$.

Output: The algorithm returns a set of $h_{i}$-hop-improving shortest paths
$\\{\pi^{i}_{s,t}\\}_{t\in V}$ each of length $O(h_{i})$ that can be
represented in space $\tilde{O}(n)$.

1

2$H^{\prime}\leftarrow H;j\leftarrow i$

3 for  _$j\leftarrow i$ down to $0$_ do

4 $\\{\tau^{j}_{s,t}\\}_{t\in V}\leftarrow\textsc{BellmanFord}(s,H^{j},h_{j})$

5

6 if  _$h_{j} >3$_ then

7 Compute an integer
$\textsc{Rad}^{j}(s)\in(\frac{1}{3}h_{j},\frac{2}{3}h_{j})$ that minimizes the
size of $\textsc{Separator}^{j}(s)=\\{x\in
V||\pi^{j}_{s,x}|=\textsc{Rad}^{j}(s)\\}$

8 else

9 $\textsc{Separator}^{j}(s)\leftarrow V$

10

11 foreach  _$x\in\textsc{Separator}^{j}(s)$_ do

12 Store path $\tau^{j}_{s,x}$

13 $w^{\prime}(s,t)\leftarrow w(\tau^{j}_{s,x})$

14

Algorithm 3 $\textsc{BellmanFordSpaceEfficient}(s,H,h_{i}=(3/2)^{i})$

The algorithm runs in iterations executed by the for-loop where the index $j$
is initially set to $i$ and decreased after every iteration until it is $0$.
In each iteration, we compute the hop-$h_{j}$-restricted shortest paths
$\\{\tau^{j}_{s,t}\\}_{t\in V}$ on the graph $H^{\prime}$. For the sake of
analysis, we let $H^{j}$ be the graph of $H^{\prime}$ at the start of
iteration $j$. After computing the paths on $H^{j}$, we compute a separator
set $\textsc{Separator}^{j}(s)$ that contains all vertices whose shortest path
from $s$ has length $\textsc{Rad}^{j}(s)$ which is taken to be strictly
between $\frac{1}{3}h_{j}$ and $\frac{2}{3}h_{j}$ (except for very small
$h_{j}$ where we chose the separator set to be $V$).

In the foreach-loop in line 3, we store for every vertex $x$ in the hitting
set $\textsc{Separator}^{j}(s)$, the $h_{j}$-hop-restricted shortest path
$\tau^{j}_{s,x}$. If the first edge on the path represents a subpath from a
higher level, we add a pointer to the subpath. Then, we update $H^{j}$ by
setting the weight of the edge from $s$ to $x$ to the weight of
$\tau^{j}_{s,x}$. Observe that after the foreach-loop finished, all paths
$\tau^{j}_{s,t}$, for any $t\in V(H)$, can be mapped to a path in $H^{\prime}$
of same weight and of length at most $h_{j-1}=\frac{2}{3}h_{j}$ and observe
that this graph is graph $H^{j-1}$.

Finally, we store the paths $\pi^{i}_{s,t}$ by a pointer to $\tau^{0}_{s,t}$.
Observe that each path $\tau^{0}_{s,t}$ might then be unpacked to an
$h_{i}$-improving shortest path in $H$ by replacing the first edge on a path
by the corresponding subpath on a higher level.

######  Lemma 4.3.

The procedure $\textsc{BellmanFordSpaceEfficient}(s,H,h_{i})$ computes a
collection of $h_{i}$-hop-improving shortest paths $\\{\pi^{i}_{s,t}\\}_{t\in
V}$ from source $s$ where each path is of length at most $O(h_{i})$ and
provides a $O(n\log h_{i})$ sized data structure such that:

  1. 1.

Each path $\pi^{i}_{s,t}$ can be extracted from the data structure in time
$O(|\pi^{i}_{s,t}|)$, and

  2. 2.

$\forall u\in V$, we can identify all paths
$\Pi_{u}=\\{\pi^{i}_{s,t}|u\in\pi^{i}_{s,t}\\}$ that contain $u$ in time
$O(|\Pi_{u}|)$.

The procedure takes time $O(n^{2}h_{i})$.

###### Proof.

We argued above that every hop $h_{j}$-restricted shortest path in $H^{j}$ can
be mapped to a $h_{j-1}$-restricted shortest path in $H^{j-1}$. Thus,
computing the $h_{j-1}$-restricted shortest path using Bellman-Ford on
$H^{j-1}$ returns $h_{j}$-hop-improving shortest paths. By a simple inductive
argument, it follows that every shortest path $\pi_{s,t}^{j}$ for any $j$ is
$h_{i}$-hop-improving in regard to $H$.

To see that every path $\pi^{i}_{s,t}$ is of length $O(h_{i})$ observe that on
level $j$, we add at most $h_{j}-1$ new edges to the path since the only
subpaths that we replace by shortcuts are $s$ to $t$ paths. Thus the final
path corresponds to a path of length $O(\sum_{j=0}^{i}h_{j})=O(h_{i})$.

To see that the data structure requires only $\tilde{O}(n)$ space, observe
that at iteration $j$, each path $\tau^{j}_{s,t}$ computed on $H^{j}$ consists
of at most $O(h_{j})$ edges that need to be stored explicitly and a pointer to
a higher level subpath corresponding to the first edge of $\tau^{j}_{s,t}$.
Since $|\textsc{Separator}^{j}(s)|=O(n/h_{j})$, and we only store paths
$\tau^{j}_{s,x}$ to each $x\in\textsc{Separator}^{j}(s)$, we therefore only
require space $O(\sum_{j=0}^{i}h_{j}\cdot n/h_{j})=O(n\log h_{i})$

We can further implement the pointers for the subpath corresponding the first
edge on a path $\pi^{i}_{s,t}$ to point to the next higher level where the
subpath is non-trivial (i.e. not itself an edge). Thus following a pointer we
can ensure to add at least one additional edge to the path, and therefore we
can extract the path in time $O(|\tau^{i}_{s,t}|)$. Making pointers of the
structure bidirectional, we can also find all paths $\pi_{s,t}^{i}$ containing
a vertex $u$ in linear time. The overall running time is dominated by running
Bellman-Ford, which takes $O(\sum_{j=0}^{i}n^{2}h_{j})=O(n^{2}h_{i})$ time. ∎

The lemma gives a straight-forward way to verify that Lemma 3.3 and 3.4 hold
even by using the relaxed Bellman-Ford procedure. The corollary below follows.

######  Corollary 4.4.

Let $G$ be an $n$-vertex directed edge-weighted graph undergoing vertex
insertions and deletions. Then there exists a deterministic data structure
which can maintain distances in $G$ between all pairs of vertices in worst-
case update time $O(n^{2+3/4}(\log n)^{2/3})$ using space $\tilde{O}(n^{2})$.
If the graph is unweighted, the running time can be improved to
$O(n^{2+2/3}(\log n)^{2/3})$.

###  4.3 A Space-Efficient and More Robust Las-Vegas Algorithm

In this section, we present a simple randomized procedure that allows to
refine the approach of our framework. On a high-level, we set the congestion
threshold for each vertex quite small (very close to $n^{2}$). Whilst this
implies that our set of congested vertices $C$ is quite large, we ensured that
we have the paths in $G\setminus C$ covered for many deletions. We then try to
fine recursively all paths through vertices in $C$ with slightly larger
congestion threshold. By shrinking the set $C$ in each iteration, we speed-up
the proprecessing procedure and therefore we can re-compute the data structure
more often. We point out that even though our layering process again gives an
efficient data structure to maintain paths that go through vertices in $C$, it
does not rely on the techniques by Abraham, Chechik and Krinninger [ACK17].

Input: A graph $G=(V,E)$, a positive integer $h>0$ determining the maximum hop
and an integer $\tau\geq 2n^{2}$ regulating the congestion.

Output: A tuple $(C_{out},\\{\textsc{Congestion}(v)\\}_{v\in
V},\\{\pi^{i}_{s,t}\\}_{s,t\in V,i\in\\{0,\ldots,i_{h}\\}})$ with the
properties of Lemma 4.5.

1 $C_{out}\leftarrow\emptyset$

2 foreach  _$v\in V$_ do $\textsc{Congestion}(v)\leftarrow 0$

3 foreach  _$s,t\in V,i\in[0,i_{h}]$_ do $\pi^{i}_{s,t}\leftarrow\bot$

4

5$X\leftarrow C_{in}$

6 while  _$X\neq\emptyset$_ do

7 Remove a center $c$ uniformly at random from $X$

8

9 foreach  _$i\in[0,i_{h}]$_ do

10 $\\{\pi^{i}_{c,t}\\}_{t\in
V}\leftarrow\textsc{BellmanFordSpaceEfficient}(c,G[V\setminus C_{out}],h_{i})$

11 $\\{\pi^{i}_{s,c}\\}_{s\in
V}\leftarrow\textsc{BellmanFordSpaceEfficient}(c,\overleftarrow{G[V\setminus
C_{out}]},h_{i})$

12

13 foreach  _$s,t\in V$ with
$w(\pi_{s,c}^{i}\circ\pi_{c,t}^{i})<w(\pi_{s,t}^{i})$_ do

14 $\pi_{s,t}^{i}\leftarrow\pi_{s,c}^{i}\circ\pi_{c,t}^{i}$

15 foreach  _$u\in\pi^{i}_{s,t}$_ do

16 $\textsc{Congestion}(u)\leftarrow\textsc{Congestion}(u)+\lceil
n/h_{i}\rceil$

17

18 if  _$C_{out}\neq\\{v\in V|\textsc{Congestion}(v) >\tau/2\\}$_ then

19 $C_{out}\leftarrow\\{v\in V|\textsc{Congestion}(v)>\tau/2\\}$

20 $\\{\pi^{i}_{c,t}\\}_{t\in
V}\leftarrow\textsc{BellmanFordSpaceEfficient}(c,G[V\setminus C_{out}],h_{i})$

21 $\\{\pi^{i}_{s,c}\\}_{s\in
V}\leftarrow\textsc{BellmanFordSpaceEfficient}(c,\overleftarrow{G[V\setminus
C_{out}]},h_{i})$

22

23

24

25

Algorithm 4 $\textsc{RandPreprocessing}(G,C_{in},\tau,h)$

We start by presenting an adapted version of the preprocessing algorithm 1
that is depicted in algorithm 4. The new algorithm takes a set $C_{in}$ of
vertices and the goal of the procedure is to produce $h$-hop-improving
shortest paths through the vertices in $C_{in}$ in the graph $G[V\setminus
C_{out}]$ where $C_{out}$ is a set of vertices that are congested over the
course of the algorithm. Instead of taking vertices from $X$ in arbitrary
order, we now sample a vertex $c$ uniformly at random in each iteration. We
then compute $h_{i}$-hop-improving shortest paths from and to $c$ by invoking
the adapted Bellman-Ford procedure on the original and the reversed graph.

We then test whether the concatenation of $\pi^{i}_{s,c}\circ\pi^{i}_{c,t}$
has lower weight than the current path from $s$ to $t$. If so, we add $\lceil
n/h_{i}\rceil$ units of congestion to each vertex $u$ on the path
$\pi^{i}_{s,c}\circ\pi^{i}_{c,t}$. In contrast to previous algorithms, if the
congestion of one of the vertices $u$ exceeds $\tau$, we immediately remove
$u$ from the graph and recompute the paths through the vertex $c$ in the new
graph. Let us now analyze the algorithm.

######  Lemma 4.5.

At termination of $\textsc{RandPreprocessing}(G,C_{in},\tau,h)$, the algorithm
ensures that

  1. 1.

$\forall v\in V$: $\textsc{Congestion}(v)\leq\tau$,

  2. 2.

$\sum_{v\in V}\textsc{Congestion}(v)=O(n^{3}(\log n)^{3})$, and

  3. 3.

$|C_{out}|=O(n^{3}(\log n)^{3}/\tau)$.

  4. 4.

Each computed path $\pi^{i}_{s,t}$ is a _$h_{i}$ -hop-improving shortest path_
in $G$ through a vertex in $C_{in}$ with regard to $G\setminus C_{out}$.

The algorithm runs in time $O(|C_{in}\cup C_{out}|n^{2}h)$ and the properties
are satisfied with probability $1-n^{-c}$ for any constant $c>0$.

###### Proof.

We maintain again the loop invariant for the while-loop in line 4 that the
congestion of any vertex not in $C_{out}$ is at most $\tau/2$. It is further
straight-forward to see that during a loop-iteration only one path is
evaluated at a time and therefore a single vertex can only obtain an addition
$\lceil n/h_{i}\rceil\leq 2n$ units of congestion. Since $2n\leq\tau/2$, we
immediately get property 1.

Next, let us analyze the total amount of congestion added in line 4. Observe
therefore that we add $\lceil n/h_{i}\rceil$ congestion to at most
$2(h_{i}+1)$ vertices respectively each time a pair $(s,t)\in V\times V$ has
its path $\pi^{i}_{s,t}$ (strictly) improved by a path
$\pi^{i}_{s,c}\circ\pi^{i}_{c,t}$ through a randomly drawn center vertex $c\in
C$. Further, observe that we pick the centers in random order in line 4. Now
let us first assume that all paths to and from centers are computed in the
graph $G$ (instead of being dependent on the current state of the set
$C_{out}$). Let $c$ be the $j^{th}$ chosen center and let us analyze the
probability that $\pi^{i}_{s,c}\circ\pi^{i}_{c,t}$ is better than the best
center seen so far. Clearly, this probability is

$Pr[c\text{ is better than the best center seen so far}]=\frac{1}{j}.$

Thus, the expected amount of congestion $X^{i}_{s,t}$ added in line 4 for a
pair $(s,t)$ in phase $i$ (under the condition that we compute Bellman-Ford
always on $G$) is
$E[X^{i}_{s,t}]=\sum_{j=1}^{|C_{in}|}\frac{1}{j}2(h_{i}+1)\lceil
n/h_{i}\rceil=O(nH_{n})$ where $H_{n}$ is the $n^{th}$ harmonic number. Since
we compute Bellman-Ford on $G[V\setminus C_{out}]$ and vertex deletions might
increase distances, we conclude that the random variable $Y^{i}_{s,t}$ that is
the expected amount of congestion added in line 4 for a pair $(s,t)$ using
graph $G[V\setminus C_{out}]$ is stochastically dominated by $X^{i}_{s,t}$.
Hence $E[Y^{i}_{s,t}]\leq O(n\log n)$ and using Markov’s inequality, we have
with constant probability that $Y^{i}_{s,t}$ is at most $O(n\log n)$. Using
the Chernoff-Bound, we obtain for any $(s,t)\in V^{2},i\in[0,i_{h}]$

$Pr[Y^{i}_{s,t}>c^{\prime}*n(\log n)^{2}]=1-n^{-(c+2)}$

where $c^{\prime}$ is a constant chosen to be large. Finally, summing over all
these events (for each tuple $(s,t)$ and $i\in[0,i_{h}]$), a union bound
implies that the probability that the total congestion exceeds $O(n^{3}(\log
n)^{3})$ is at most $1-n^{-c}$. Thus, with probability $1-n^{-c}$, the
algorithm satisfies property 2 on termination.

Property 3 follows since each vertex $c\in C_{out}$ has congestion at least
$\tau/2$, implying that there can be at most $2\Phi/\tau=O(n^{3}\log h/\tau)$
vertices in $C_{out}$. Property 4 follows from Lemma 4.3. The running time is
strictly dominated by running Bellman-Ford from and to each vertex in $C_{in}$
and at most $C_{out}$ recomputations in the if-case in algorithm 4.Thus, the
total running time is $O(|C_{in}\cup C_{out}|n^{2}h)$ using again a geometric
sum argument and Lemma 4.3. ∎

It is straight-forward to verify that the update procedure from section 3.2
can be used to recover pre-computed paths that are destroyed by batch
deletions. The following lemma formalizes that we can maintain efficiently
$h$-hop-improving shortest paths through the set $C_{in}$ in the graph
$G\setminus D$ with regard to $G\setminus(D\cup C_{out})$.

######  Lemma 4.6.

Given a data structure that satisfies the properties listed in Lemma 4.5 with
congestion threshold $\tau$, with set $C_{in}\subseteq V$ and with a set of
congested vertices $C_{out}$, there exists an algorithm that computes for each
tuple $(s,t)$ an improving shortest path $\pi_{s,t}$ through $C_{in}$ in
$G\setminus D$ with regard to $G\setminus(D\cup C_{out})$ and returns the
corresponding distance matrix in time $O(|D|\tau+n^{3}/h)$.

Using this new algorithm to preprocess, we maintain data structures
$\mathcal{D}_{0},\mathcal{D}_{1},\dots,\mathcal{D}_{\lceil\lg h\rceil}$ where
each data structure $\mathcal{D}_{i}$ is initialized by invoking procedure
$\textsc{RandPreprocessing}(G,C_{i},\tau_{i},h)$ that returns a set $C_{i+1}$
of congested vertices (here $C_{i}$ takes the role of $C_{in}$ and $C_{i+1}$
the role of $C_{out}$). Initially, we set $C_{0}=V$, and $\tau_{i}=c*(\log
n)^{3}*2^{i}n^{2}$ where $c$ is chosen such that $C_{1}$ in Lemma 4.5 is of
size at most $n/2$ which also stipulates that $|C_{i}|\leq n/2^{i}$ for all
$i$. Computing the data structure $\mathcal{D}_{i}$ once data structure
$\mathcal{D}_{i-1}$ is computed is then well-defined. We finish the
initialization with the data structures
$\mathcal{D}_{0},\mathcal{D}_{1},\dots,\mathcal{D}_{\lceil\lg h\rceil}$ and a
final set $C_{\lceil\lg h\rceil+1}$ of size $O(n(\log n)^{3}/h)$.

We now set for each data structure $\mathcal{D}_{i}$ the number of updates
until we recompute the data structure to $\Delta_{i}=n^{2/3}/2^{i}(\log n)$.
Observe that the total time to rebuild the data structures amortized over the
number of updates can now be bound by

$\sum_{i=0}^{\lceil\lg
h\rceil}\frac{O(|C_{i}|n^{2}h)}{\Delta_{i}}=O(n^{2+1/3}(\log n)^{4}h)$

We can again deamortize by building the data structures in the background
using standard techniques incurring at most an additional constant factor in
the running time. A subtle detail is that if a data structure at level $i$ is
replaced then all data structures at higher levels have to be replaced at the
same time so that the sets $C_{i}$ form the hierarchy proposed in the
preprocessing. Since rebuilding the data structures at higher levels can be
done more efficiently, this however does only increase the running time by
factor $2$.

Finally, let us discuss the delete procedure. Data structure $\mathcal{D}_{1}$
returns the shortest paths in $G\setminus D$ that does not contain a vertex in
$C_{1}$ by Lemma 4.6. Subsequently, each data structure $\mathcal{D}_{i}$ can
be used to find the shortest paths through $C_{i}$ that do not contain a
vertex in $C_{i+1}$. Combining these shortest paths by choosing the one of
minimum weight for each tuple $(s,t)\in V^{2}$, we obtain all shortest paths
that do not contain a vertex in $C_{\lceil\lg h\rceil+1}$. Using Johnson’s
algorithm as described in Lemma 3.2, we can reinsert these vertices in time
$O(|C_{\lceil\lg h\rceil+1}|n^{2})$ and handle the at most $\Delta_{0}$
insertions since the data structure $\mathcal{D}_{0}$ was last build. We can
then return all-pairs shortest paths.

The update time to process the batch deletion in all data structures and the
time spent to reinsert vertices can be bound by

$(|C_{\lceil\lg h\rceil+1}|+\Delta_{0})*n^{2}+\sum_{i=0}^{\lceil\lg
h\rceil}(\Delta_{i}\tau_{i}+n^{3}/h)=O(n^{2+2/3}(\log n)^{3}+n^{3}\log n/h)$

Setting $h=n^{1/3}(\log n)^{2}$ optimizes the running time. Finally, we point
out that after the preprocessing step, each data structure is entirely
deterministic. Since the initialization step also fixes a graph version once
it starts that it keeps working on, the adversary cannot change the graph to
affect the running time of the preprocessing step from that point. This
implies that the algorithm even works against a non-oblivious adversary, that
is an adversary that has access to the random bits used by the algorithms. We
also point out that since we use the adapted Bellman-Ford procedure to store
paths, the space of the data structure only differs by logarithmic factors
from the space usage of the data structure presented in section 4.2.

######  Corollary 4.7.

Let $G$ be an $n$-vertex directed edge-weighted graph undergoing vertex
insertions and deletions. Then, there exists a Las-Vegas data structure which
can maintain distances in $G$ between all pairs of vertices with update time
$O(n^{2+2/3}(\log n)^{3})$ w.h.p. using space $\tilde{O}(n^{2})$ against a
non-oblivious adversary. If the graph is unweighted, the running time can be
improved to $O(n^{2+1/2}(\log n)^{3})$.

##  5 Conclusion

In this article, we present the first deterministic data structure that
improves upon the longstanding result by Thorup [Tho05]. However, it remains
open whether worst-case update time $\tilde{O}(n^{2+2/3})$ can also be
achieved deterministically. We point out that one path to derandomize our last
data structure is to obtain an _amortized_ update-time data structure that
maintains hop-restricted shortest paths. Further a fundamental open problem is
whether the worst-case update time can be further improved (or if lower bounds
can rule out such an improvement).

Finally, we provided the first space-efficient data structures for the dynamic
APSP problem, i.e. the first data structures obtaining $\tilde{O}(n^{2})$
space. Further progress towards an algorithm with $\tilde{O}(n^{2})$
(amortized) update time and $\tilde{O}(n^{2})$ space remains an important open
problem.

## Acknowledgements

The authors would like to thank Adam Karczmarz for pointing out an error in
lemma 4.5 and for providing a simple fix.

## References

  * [AC13] Ittai Abraham and Shiri Chechik  “Dynamic Decremental Approximate Distance Oracles with $(1+\epsilon,2)$ stretch”  In _arXiv preprint arXiv:1307.1516_ , 2013
  * [ACK17] Ittai Abraham, Shiri Chechik and Sebastian Krinninger  “Fully dynamic all-pairs shortest paths with worst-case update-time revisited”  In _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19_ , 2017, pp. 440–452  DOI: 10.1137/1.9781611974782.28
  * [Ber09] Aaron Bernstein  “Fully dynamic (2+ epsilon) approximate all-pairs shortest paths with fast query and close to linear update time”, 2009
  * [Ber16] Aaron Bernstein  “Maintaining shortest paths under deletions in weighted directed graphs”  In _SIAM Journal on Computing_ 45.2 SIAM, 2016, pp. 548–574
  * [BHS02] Surender Baswana, Ramesh Hariharan and Sandeep Sen  “Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths”  In _Proceedings of the thiry-fourth annual ACM symposium on Theory of computing_ , 2002, pp. 117–123  ACM
  * [BN19] Jan van den Brand and Danupon Nanongkai  “Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time”  In _arXiv preprint arXiv:1909.10850_ , 2019
  * [Che18] Shiri Chechik  “Near-Optimal Approximate Decremental All Pairs Shortest Paths”  In _Foundations of Computer Science (FOCS), 2018 IEEE 59th Annual Symposium on_ , 2018, pp. 170–181  IEEE
  * [Cor+09] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest and Clifford Stein  “Introduction to algorithms”  MIT press, 2009
  * [DI02] Camil Demetrescu and Giuseppe F Italiano  “Improved bounds and new trade-offs for dynamic all pairs shortest paths”  In _International Colloquium on Automata, Languages, and Programming_ , 2002, pp. 633–643  Springer
  * [DI04] Camil Demetrescu and Giuseppe F Italiano  “A new approach to dynamic all pairs shortest paths”  In _Journal of the ACM (JACM)_ 51.6 ACM, 2004, pp. 968–992
  * [DI06] Camil Demetrescu and Giuseppe F Italiano  “Experimental analysis of dynamic all pairs shortest path algorithms”  In _ACM Transactions on Algorithms (TALG)_ 2.4 ACM, 2006, pp. 578–601
  * [DI06a] Camil Demetrescu and Giuseppe F Italiano  “Fully dynamic all pairs shortest paths with real edge weights”  In _Journal of Computer and System Sciences_ 72.5 Academic Press, 2006, pp. 813–837
  * [E+79] Shimon Even and Y Shi1oa  “An on-line edge-deletion problem”, 1979
  * [HK01] Monika R Henzinger and Valerie King  “Maintaining minimum spanning forests in dynamic graphs”  In _SIAM Journal on Computing_ 31.2 SIAM, 2001, pp. 364–374
  * [HKN16] Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai  “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization”  In _SIAM Journal on Computing_ 45.3 SIAM, 2016, pp. 947–1006
  * [Ita08] Giuseppe F. Italiano  “Fully Dynamic All Pairs Shortest Paths”  In _Encyclopedia of Algorithms_ Boston, MA: Springer US, 2008, pp. 329–331  DOI: 10.1007/978-0-387-30162-4_151
  * [Joh77] Donald B Johnson  “Efficient algorithms for shortest paths in sparse networks”  In _Journal of the ACM (JACM)_ 24.1 ACM, 1977, pp. 1–13
  * [Kin99] Valerie King  “Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs”  In _Foundations of Computer Science, 1999. 40th Annual Symposium on_ , 1999, pp. 81–89  IEEE
  * [KT01] Valerie King and Mikkel Thorup  “A space saving trick for directed dynamic transitive closure and shortest path algorithms”  In _International Computing and Combinatorics Conference_ , 2001, pp. 268–277  Springer
  * [PW20] Maximilian Probst Gutenberg and Christian Wulff-Nilsen  “Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler”  In _Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2020  SIAM
  * [RTZ05] Liam Roditty, Mikkel Thorup and Uri Zwick  “Deterministic constructions of approximate distance oracles and spanners”  In _International Colloquium on Automata, Languages, and Programming_ , 2005, pp. 261–272  Springer
  * [RZ04] Liam Roditty and Uri Zwick  “On dynamic shortest paths problems”  In _European Symposium on Algorithms_ , 2004, pp. 580–591  Springer
  * [RZ12] Liam Roditty and Uri Zwick  “Dynamic approximate all-pairs shortest paths in undirected graphs”  In _SIAM Journal on Computing_ 41.3 SIAM, 2012, pp. 670–683
  * [Tho04] Mikkel Thorup  “Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles”  In _Scandinavian Workshop on Algorithm Theory_ , 2004, pp. 384–396  Springer
  * [Tho05] Mikkel Thorup  “Worst-case update times for fully-dynamic all-pairs shortest paths”  In _Proceedings of the thirty-seventh annual ACM symposium on Theory of computing_ , 2005, pp. 112–119  ACM
  * [TZ05] Mikkel Thorup and Uri Zwick  “Approximate distance oracles”  In _Journal of the ACM (JACM)_ 52.1 ACM, 2005, pp. 1–24
  * [Zwi02] Uri Zwick  “All pairs shortest paths using bridging sets and rectangular matrix multiplication”  In _J. ACM_ 49.3, 2002, pp. 289–317  DOI: 10.1145/567112.567114

##  Appendix A Proof of lemma 2.1

We often use a simple lemma to compute hitting sets deterministically.

######  Lemma A.1 (see [TZ05, RTZ05]).

Let $N_{1},N_{2},\dots,N_{n}\subseteq U$ be a collection of subsets of $U$,
with $u=|U|$ and $|N_{i}|\geq s$ for all $i\in[1,n]$. Then, we can implement a
procedure $\textsc{Separator}(\\{N_{i}\\}_{i\in[1,n]})$ that returns a set $A$
of size at most $O(\frac{u\log n}{s})$ with $N_{i}\cap A\neq\emptyset$ for all
$i$, deterministically in $O(u+\sum_{i}|N_{i}|)$ time.

Below we describe the algorithm presented in [Zwi02]. It is straight-forward
to return paths, however, for simplicity, our algorithm only returns
distances. Here, $i_{max}=\lceil\log_{3/2}n\rceil$.

Input: A collection of paths $\Pi$, that contains a path for each tuple
$(s,t)\in V\times V$.

Output: Returns the set of distances
$\\{(\textsc{Dist}_{i_{max}}(s,t)\\}_{s,t\in V\times V}$.

1 foreach  _$(s,t)\in V\times V$_ do

2 $\textsc{Dist}_{i_{h}}(s,t)\leftarrow w(\pi_{i_{h}}(s,t))$

3

4for  _$i\leftarrow i_{h}+1$ to $i_{max}$_ do

5 Compute a set Separator of size $O(n\log n/h_{i})$ that contains a vertex
from each path in $\Pi$ of hop at least $\lfloor\frac{1}{4}h_{i}\rfloor$.

6 foreach  _$(s,t)\in V\times V$_ do

7 $\textsc{Dist}_{i}(s,t)\leftarrow\textsc{Dist}_{i-1}(s,t)$

8 foreach  _$x\in\textsc{Separator}$_ do

9
$\textsc{Dist}_{i}(s,t)\leftarrow\min\\{\textsc{Dist}_{i}(s,t),\textsc{Dist}_{i-1}(s,x)+\textsc{Dist}_{i-1}(x,t)\\}$

10

11

return $\\{(\textsc{Dist}_{i_{max}}(s,t)\\}_{s,t\in V\times V}$

Algorithm 5
$\textsc{DeterministicExtendDistances}(\Pi=\\{\pi_{i_{h}}(s,t)\\}_{s,t},h)$

######  Lemma A.2 (Restatement of 2.1).

Given a collection $\Pi$ of the $h$-hop-improving shortest paths for all pairs
$(s,t)\in V^{2}$ in $G\setminus D$, then there exists a procedure
$\textsc{DetExtDistances}(\Pi,h)$ that returns improving shortest path
distances for all pairs $(s,t)\in V^{2}$ in time $O(n^{3}\log
n/h+n^{2}\log^{2}n)$.

###### Proof.

Let us denote by $\textsc{Separator}^{i}$ the separator at phase $i$. We
compute the initial separator $\textsc{Separator}^{i_{h}+1}$ in time
$O(n^{2}h)$ time by finding a hitting set for all paths of hop at least
$\frac{1}{4}h$. For $\textsc{Separator}^{i}$ with $i>i_{h}+1$, we only hit the
shortest paths from and to all vertices in $\textsc{Separator}^{i-1}$ of
length $\frac{1}{4}h_{i}$. This suffices since the $\textsc{Separator}^{i-1}$
"hit" all paths of length $\frac{1}{4}h_{i-1}$ so all paths of hop
$\frac{1}{4}h_{i}$ have to go through at least one such vertex. The running
time to compute the separator at phase $i$ is thus $O(n\log
n/h_{i}*nh_{i})=O(n^{2}\log n)$. Using this layering the initial separator
$\textsc{Separator}^{i_{h}+1}$ can also be computed in time $O(n^{2}\log n)$.
Once, the separator is computed, each path at iteration $i$ can be computed in
time $O(|\textsc{Separator}^{i}|)$. Using a geometric sum argument, we obtain
the claimed running time.

The correctness of the lemma follows if we can establish the loop-invariant
for the for-loop in line 5 that at the beginning of iteration $i$, for each
pair $(s,t)$, if there is a shortest path from $s$ to $t$ in $G\setminus D$
which has hop at most $h_{i-1}$ then $\textsc{Dist}_{i-1}(s,t)$ is the weight
of a shortest path from $s$ to $t$ in $G\setminus D$. Here, we prove the claim
only for shortest paths, however, an extension to improving shortest-paths is
straight-forward.

The proof is by induction on $i\geq i_{h}+1$. When $i=i_{h}+1$, the claim is
true by our assumption on $\Pi$. Now consider the beginning of an iteration
$i\leq i_{\max}$ and assume that the invariant holds at this point. Let
$s,t\in V$ be given and assume that there is a shortest path $P$ from $s$ to
$t$ in $G\setminus D$ such that $P$ has hop at most $h_{i}$. Pick $P$ such
that its hop is minimized.

If $|P|\leq\frac{2}{3}h_{i}=h_{i-1}$ then in line 5,
$\textsc{Dist}_{i}(s,t)=\textsc{Dist}_{i-1}(s,t)=w(P)=d_{G\setminus D}(s,t)$
by the induction hypothesis. Since $\textsc{Dist}_{i}(s,t)$ can never
increase, the invariant holds at the beginning of iteration $i+1$ for $s$ and
$t$.

Now, assume that $|P|>\frac{2}{3}h_{i}$. Since $i\geq i_{h}+1$, we have
$|P|>\frac{2}{3}h_{i_{h}+1}=h=h$. Let $a$ be the vertex of $P$ such that
$|P[s,a]|=\lceil\frac{1}{2}|P|-\frac{1}{8}h\rceil$ and let $b$ be the vertex
of $P[a,t]$ such that $|P[a,b]|=\lfloor\frac{1}{4}h\rfloor$. Since $P[a,b]$ is
a shortest path of minimum hop, the induction hypothesis implies that
$P^{\prime}=P[s,a]\circ\pi_{i_{h}}(a,b)\circ P[b,t]$ is a shortest path from
$s$ to $t$ in $G\setminus D$ of minimum hop $|P^{\prime}|=|P|$. Since
$|\pi_{i_{h}}(a,b)|=|P[a,b]|=\lfloor\frac{1}{4}h\rfloor$, $\pi_{i_{h}}(a,b)$
intersects Separator in a vertex $x$. Since
$|P^{\prime}[s,x]|\leq\lceil\frac{1}{2}|P|-\frac{1}{8}h\rceil+\lfloor\frac{1}{4}h\rfloor\leq\frac{2}{3}|P|\leq\frac{2}{3}h_{i}=h_{i-1}$,
we have $\textsc{Dist}_{i-1}(s,x)=w(P^{\prime}[s,x])$. Similarly, since
$|P^{\prime}[x,t]|\leq|P|-\lceil\frac{1}{2}|P|-\frac{1}{8}h\rceil\leq\frac{2}{3}|P|\leq
h_{i-1}$, we have $\textsc{Dist}_{i-1}(x,t)=w(P^{\prime}[x,t])$. Hence, in
line 5, $\textsc{Dist}_{i}(s,t)$ is set to
$w(P^{\prime}[s,x])+w(P^{\prime}[x,t])=w(P^{\prime})=\textsc{Dist}_{G\setminus
D}(s,t)$. This shows that the invariant holds at the beginning of iteration
$i+1$ for $s$ and $t$, as desired.

At termination, $i=i_{\max}+1$ and the invariant states that for all $s,t\in
V$, if there is a shortest path from $s$ to $t$ in $G\setminus D$ and this
path has at most $h_{i_{\max}}\geq n$ hops then
$\textsc{Dist}_{i_{\max}}(s,t)=\textsc{Dist}_{G\setminus D}(s,t)$. The lemma
now follows since any simple shortest path has at most $n-1$ hops. ∎