with sublinear query is based on an techniques used in [RZ12, BN19]. We modify
the algorithm of [BN19] by incorporating our new dynamic emulators which allow
us to improve upon the internally used dynamic $(1+\epsilon)$-MSSP algorithm.
This way we obtain the following corollary.

######  Corollary A.3.

Given an unweighted, undirected graph $G=(V,E)$, and $0<\epsilon<1$, we can
maintain a data structure that supports all-pair $(1+\epsilon)$-approximate
distance queries with following guarantees:

  * •

Preprocessing time: $O(n^{2.585})\cdot
O(\tfrac{1}{\epsilon})^{\sqrt{2\log_{1/\epsilon}n}}$.

  * •

Worst-case update time: $O(n^{1.788})\cdot
O(\tfrac{1}{\epsilon})^{\sqrt{2\log_{1/\epsilon}n}}$.

  * •

Query time: $O(n^{0.45}\epsilon^{-2})$.

Moreover, these bounds hold with high probability against an adaptive
adversary.

At a high-level the algorithm uses a well-known path hitting set151515Note
that path hitting sets should not be confused with the neighborhood (of heavy
nodes) hitting sets that we used in Section 3.3. [UY91] argument as follows:
Consider any pair of nodes $u,v\in V$. If one samples $\Theta(\tfrac{n}{h}\log
n)$ nodes $S\subseteq V$ uniformly at random, then w.h.p. every shortest path
of length $h$ contains a sampled node. We maintain
$O(\tfrac{h}{\epsilon})$-bounded distances using algebraic distance data
structures. Additionally we maintain $(1+\epsilon)$-approximate MSSP with the
nodes in $S$ as the sources using our sparse emulator. In unweighted,
undirected graphs, this information suffices to retrieve
$(1+\epsilon)$-approximate distance estimates. Our final algorithm is a bit
more involved since we need to consider two types of bounded distances: 1) We
need to consider $\Theta(h/\epsilon)$-bounded distances for the parameter $h$
needed for the path hitting component of our data structure. 2) We need
$\Theta(\beta/\epsilon)$-bounded distances for turning the additive
approximation of our emulator into a multiplicative one. This also means we
need to consider more cases in our correctness analysis.

The $\Theta(h/\epsilon)$-bounded distances will be maintained using the
following dynamic algorithm.

######  Lemma A.4 ([BN19]).

Given an undirected and unweighted graph $G=(V,E)$, for any
$0<\tau,0<\epsilon,\mu_{1},\mu_{2}\leq 1$, we can maintain a randomized Monte-
Carlo data structure against an adaptive adversary with worst-case update time
of
$O((n^{\omega(1,\tau+\mu_{1},1)-\mu_{1}}\epsilon^{-1}+n^{\omega(1,\mu_{2},1)+\tau-\mu_{2}}+n^{1+\mu_{2}+\tau})\log
n)$ that can query $(1+\epsilon)$-approximate $n^{\tau}$-bounded pairwise
distances for any set of nodes $S,T\subseteq V$ in
$O(n^{\omega(\log_{n}|S|,\mu_{1}+\tau,\log_{n}|T|)}\epsilon^{-1}\log n)$ time.
The preprocessing time is $O(n^{\omega+\tau}\log n)$.

For current $\omega$, the best choice for minimizing the update time is
roughly $\mu_{2}\approx 0.529$, implying
$O(n^{\omega(1,\mu_{2},1)+\tau-\mu_{2}}+n^{1+\mu_{2}+\tau})=O(n^{1.529+\tau})$.

Let us continue the description of our algorithm. The algorithm has a main
parameter $h$ and does the following. At all times, it internally uses the
following dynamic algorithms:

  1. 1.

An instance of the dynamic algorithm of Lemma 1.4 for maintaining a
$(1+\tfrac{\epsilon}{6},\beta)$-emulator $H$, where
$\beta=O(\tfrac{1}{\epsilon})^{k}$, for
$k=\sqrt{\frac{\log_{1/\epsilon}n}{2}}$.

  2. 2.

An instance $\mathcal{D}_{1}$ of the algebraic data structure of Lemma A.4 for
maintaining $h_{1}$-bounded distances for $h_{1}=\tfrac{6h}{\epsilon}$
(internally setting $\tau=\log_{n}h_{1}$), for some parameter $h$ to be chosen
later

  3. 3.

An instance $\mathcal{D}_{2}$ of the algebraic data structure of Lemma A.2 for
maintaining $h_{2}$-bounded distances for $h_{2}=\tfrac{6\beta}{\epsilon})$.

Additionally, after each update to the input graph our algorithm performs the
following steps:

  1. 1.

Sample a set of $\Theta(\tfrac{n}{h}\log n)$ sources $S$ uniformly at random,
which we call centers.

  2. 2.

Compute (exact) MSSP from all nodes in $S$ on $H$ statically.

  3. 3.

For every node $u$, find the closest center among $S$ in $H$, denoted by
$p(u)$.

  4. 4.

Query the $h_{2}$-bounded distances $d_{G}^{h_{2}}(x,u)$ from
$\mathcal{D}_{2}$ for every $x\in S$ and every $v\in V$ (where
$d_{G}^{h_{2}}(u,v)=d_{G}(u,v)$ if $d_{G}^{h_{2}}(u,v)<h_{2}$ and
$d_{G}^{h_{2}}(u,v)=\infty$ otherwise).

Each query for the approximate distance between two nodes $u$ and $v$ is now
answered by performing the following steps:

  1. 1.

Query the $h_{1}$-bounded distance $d_{G}^{h_{1}}(u,v)$ from $\mathcal{D}_{1}$
(where $d_{G}^{h_{1}}(u,v)=d_{G}(u,v)$ if $d_{G}^{h_{1}}(u,v)<h$ and
$d_{G}^{h_{1}}(u,v)=\infty$ otherwise).

  2. 2.

Set
$\hat{d}(u,v)=\min(d^{h_{2}}_{G}(p(u),u),d_{H}(p(u),u))+\min(d^{h_{2}}_{G}(p(u),v),d_{H}(p(u),v))$

  3. 3.

Return $\min(d_{G}^{h_{1}}(u,v),\hat{d}(u,v))$

We will now show that this algorithm has the desired guarantees.

###### Proof of Corollary A.3.

We first argue that the algorithm returns a $(1+\epsilon)$-approximation of
the true distance $d_{G}(u,v)$ at query time. Clearly, the returned distance
estimate never under-estimates the true distance. If $d_{G}(u,v)<h_{1}$, then
$d_{G}^{h_{1}}(u,v)=d_{G}(u,v)$ provides the correct answer.

If $d_{G}(u,v)\geq h_{1}$, then consider the first
$\tfrac{\epsilon}{6}h_{1}=h$ nodes on the shortest path from $u$ to $v$. This
set of nodes contains a center $x\in S$ with high probability. We thus know
that

$d_{G}(u,p(u))\leq
d_{G}(u,x)\leq\frac{\epsilon}{6}h_{1}\leq\frac{\epsilon}{6}d_{G}(u,v)\,.$

By the triangle inequality we now get

$\displaystyle d_{G}(p(u),u)+d_{G}(p(u),v)$ $\displaystyle\leq
d_{G}(p(u),u)+d_{G}(p(u),u)+d_{G}(u,v)$
$\displaystyle=d_{G}(u,v)+2d_{G}(p(u),u)$
$\displaystyle\leq\left(1+\frac{\epsilon}{3}\right)d_{G}(u,v)\,.$

By the stretch guarantee of the emulator $H$ we have
$d_{H}(p(u),u)\leq(1+\tfrac{\epsilon}{6})d_{G}(p(u),u)+\beta$ and
$d_{H}(p(u),v)\leq(1+\tfrac{\epsilon}{6})d_{G}(p(u),v)+\beta$. If
$d_{G}(p(u),u)\geq\tfrac{6\beta}{\epsilon}$, then
$d_{H}(p(u),u)\leq(1+\tfrac{\epsilon}{3})d_{G}(p(u),u)$, and if
$d_{G}(p(u),u)<\tfrac{6\beta}{\epsilon}=h_{2}$, then
$d^{h_{2}}_{G}(p(u),u)=d_{G}(p(u),u)$.

Thus,
$\min(d^{h_{2}}_{G}(p(u),u),d_{H}(p(u),u))\leq(1+\tfrac{\epsilon}{3})d_{G}(p(u),u)$.
We can argue in the same manner that
$\min(d^{h_{2}}_{G}(p(u),v),d_{H}(p(u),v))\leq(1+\tfrac{\epsilon}{3})d_{G}(p(u),v)$.
Overall, this gives us

$\displaystyle\hat{d}(u,v)$
$\displaystyle\leq\left(1+\frac{\epsilon}{3}\right)d_{G}(p(u),u)+\left(1+\frac{\epsilon}{3}\right)d_{G}(p(u),v)$
$\displaystyle=\left(1+\frac{\epsilon}{3}\right)(d_{G}(p(u),u)+d_{G}(p(u),v))$
$\displaystyle\leq\left(1+\frac{\epsilon}{3}\right)^{2}d_{G}(u,v)$
$\displaystyle\leq(1+\epsilon)d_{G}(u,v)\,.$

We proceed with the running time analysis. Data structure $\mathcal{D}_{1}$
has, for any chosen $\mu_{1}$, an update time of
$O((n^{\omega(1,\mu_{1}+\log_{n}h_{1},1)-\mu_{1}}\epsilon^{-1}+O(n^{1.529+\log_{n}h_{1}})\log
n)=\tilde{O}(n^{\omega(1,\mu_{1}+\log_{n}h,1)-\mu_{1}}\epsilon^{-2}+O(n^{1.529+\log_{n}h}\epsilon^{-1})$.161616Here
we use that
$\omega(\alpha,\beta+\beta^{\prime},\gamma)=O(\omega(\alpha,\beta,\gamma)n^{\beta^{\prime}})$.
We will also use this bound later in the proof. Data structure
$\mathcal{D}_{2}$ has, for any chosen $\mu_{2}$, an update time of
$O((n^{\omega(1,1,\mu_{2})-\mu_{2}}+n^{1+\mu_{2}})h_{2}\log
h_{2})=\tilde{O}((n^{\omega(1,1,\mu_{2})-\mu_{2}}+n^{1+\mu_{2}}))\cdot
O(\tfrac{1}{\epsilon})^{k}$.171717Note that these simplifications assume that
$\epsilon\geq\tfrac{1}{n}$ as a smaller value of $\epsilon$ would allow for
rounding to exact distances. We will also use this bound later in the proof.

The update time of the algorithm maintaining the emulator $H$ is
$O(n^{1.477})$ (which is clearly dominated by the update time of
$\mathcal{D}_{1}$) as in any case we can reduce $\epsilon$ to a value that
gives $k\geq 8$. Sampling the set $S$ takes time $\tilde{O}(n)$.

Computing MSSP from $S$ on $H$ takes time
$\tilde{O}(|S|n^{1+1/k})=\tilde{O}(\tfrac{n^{2+1/k}}{h})$. Computing the
closest node among $S$ for each node takes time
$O(n|S|)=\tilde{O}(\tfrac{n^{2}}{h})$.

The time for querying the $h_{2}$-bounded $S\times V$ distances from data
structure $\mathcal{D}_{2}$ is bounded by
$O(n^{\omega(\log_{n}|S|,\mu_{2},1)}h_{2}\log
h_{2})=\tilde{O}(n^{\omega(1-\log_{n}h,\mu,1)})\cdot
O(\tfrac{1}{\epsilon})^{k}$. The running time of the remaining steps performed
during an update is dominated by
$\tilde{O}(|S|n^{1+1/k})=\tilde{O}(\tfrac{n^{2+1/k}}{h})$.

In the query algorithm, we first query data structure $\mathcal{D}_{1}$ for
one pair of nodes, which takes time
$O(n^{\omega(0,\mu_{1}+\log_{n}h_{1},0)}\epsilon^{-1}\log
n)=\tilde{O}(n^{\mu_{1}}h\epsilon^{-2})$. The remaining steps in the query
algorithm are clearly dominated by this term.

The preprocessing time of $\mathcal{D}_{1}$ is $O(n^{\omega+\log_{n}h_{1}}\log
n)=\tilde{O}(n^{\omega}h\epsilon^{-1})$ and the preprocessing time of
$\mathcal{D}_{2}$ is $O(n^{\omega}h_{2}\log h_{2})=\tilde{O}(n^{\omega})\cdot
O(\tfrac{1}{\epsilon})^{k}$.

Our approach for setting the parameters is to consider
$n^{\omega(1,\mu_{1}+\log_{n}h,1)-\mu_{1}}$ and $\tfrac{n^{2}}{h}$ as the
dominant terms and set $h$ and $\mu_{1}$ in such a way that
$n^{\mu_{1}+\log_{n}h}=n^{0.45}$. The latter is equivalent to
$\mu_{1}+\log_{n}h=0.45$, which yields the simplification
$n^{\omega(1,\mu_{1}+\log_{n}h,1)-\mu_{1}}=n^{\omega(1,0.45,1)-\mu_{1}}$. We
now balance the terms $n^{\omega(1,0.45,1)-\mu_{1}}$ and $\tfrac{n^{2}}{h}$
under the constraint $n^{\mu_{1}+\log_{n}h}<n^{0.45}$.

By setting $\mu_{1}=0.2374$ and $h=n^{0.2125}$ we get
$\tilde{O}(n^{\omega(1,\mu_{1}+\log_{n}h,1)-\mu_{1}})=n^{1.788}$,
$\tilde{O}(\tfrac{n^{2}}{h})=n^{1.788}$, and
$\tilde{O}(n^{\mu_{1}}h)=O(n^{0.45})$ . Now by setting $\mu_{2}=0.24$ we get
$\tilde{O}((n^{\omega(1,1,\mu_{2})-\mu_{2}}+n^{1+\mu_{2}}))=O(n^{1.76})$ and
$\tilde{O}(n^{\omega(1-\log_{n}h,\mu,1)})=n^{1.788}$. Finally, setting
$k=\sqrt{\frac{\log_{1/\epsilon}n}{2}}$ balances $(\tfrac{1}{\epsilon})^{k}$
and $n^{1/k}$ in the update time.

Overall, we obtain an update time of $O(n^{1.788})\cdot
O(\tfrac{1}{\epsilon})^{\sqrt{2\log_{1/\epsilon}n}}$, a query time of
$O(n^{0.45}\epsilon^{-2})$, and a preprocessing time of $O(n^{2.585})\cdot
O(\tfrac{1}{\epsilon})^{\sqrt{2\log_{1/\epsilon}n}}$. ∎

##  Appendix B Comparison to Algebraic Algorithms with Batch-Queries

In Section 2.1 we remarked that the emulator construction with low recourse
hitting sets is needed for our upper bounds to match conditional lower bounds
from [BNS19]. Here we state the complexity that could be achieved if one were
to use a new hitting set in each iteration instead.

The bottleneck is maintaining the submatrix $\mM^{-1}_{S,T}$ of some dynamic
matrix inverse. Lemma 5.1 is able to maintain such a submatrix efficiently, if
sets $S$ and $T$ are slowly changing. If the sets, however, were changing
arbitrarily from one iteration to the next (e.g. by using a new hitting set in
our emulator construction after each update), then we would have to use
previous algorithms [San04, BNS19] instead with the following complexities.

######  Lemma B.1 ([San04]).

For any $0\leq\nu\leq 1$ there exists a dynamic matrix inverse algorithm that
initializes in $O(n^{\omega})$ operations and supports entry updates to $\mA$
in $O(n^{\omega(1,1,\nu)-\nu}+n^{1+\nu})$ operations. Querying
$\mA^{-1}_{S,T}$ for any $|S|=n^{\sigma}$, $|T|=n^{\tau}$ takes
$O(n^{\omega(\sigma,\nu,\tau)})$ operations.

In comparison, our Lemma 5.1 (when picking $\mu=1$) replaces the
$O(n^{\omega(\sigma,\nu,\tau)})$ query complexity of Lemma B.1 by a smaller
additive $O(|S\times T|)=O(n^{\omega(\sigma,0,\tau)})$ in the update
complexity.

For the emulator construction for $(1+\epsilon)$-SSSP we pick $|S|=n$ and
$T=\tilde{O}(\sqrt{n})$. So for current $\omega$ and constant $\epsilon$,
Lemma B.1 would only imply $O(n^{1.596})$ for single source distances
($\sigma=1,\tau=0.5,\nu\approx 0.42$) opposed to our deterministic
$O(n^{1.529})$ upper bound (which was also achieved by [BHGW+21] with
randomization against oblivious adversaries).

For the emulators used in the $st$-case one could use the following lemma.

######  Lemma B.2 ([BNS19]).

For any $0\leq\nu\leq\mu\leq 1$ there exists a dynamic matrix inverse
algorithm that initializes in $O(n^{\omega})$ operations and supports entry
updates to $\mA$ in
$O(n^{\omega(1,1,\mu)-\mu}+n^{\omega(1,\mu,\nu)-\nu}+n^{\mu+\nu})$ operations.
Querying $\mA^{-1}_{S,T}$ for any $|S|=n^{\sigma}$, $|T|=n^{\tau}$ takes
$O(n^{\omega(\sigma,\mu,\nu)}+n^{\omega(\tau,\mu,\nu)}+n^{\omega(\sigma,\nu,\tau)})$
operations.

In comparison, our Lemma 5.1 replaces all terms in the query complexity of
Lemma B.2 by a much smaller additive $O(|S\times
T|)=O(n^{\omega(\sigma,0,\tau)})$ in the update complexity.

We use $|S|=|T|=\tilde{O}(n^{2/3})$ in our emulator construction for
$(1+\epsilon)$-approximate $st$-distances. For current $\omega$ and constant
$\epsilon$, Lemma B.2 would imply $O(n^{1.438})$ update time for
$st$-distances ($\mu\approx 0.747,\nu\approx 0.323,\sigma=\tau=2/3$) opposed
to our $O(n^{1.407})$ bound.

##  Appendix C Improved Randomized Bounds for Exact $st$-Distances

We remark that our new dynamic algorithm for maintaining bounded distances
(Corollary 5.5) can also be used to speed up dynamic exact $st$-distances in
directed graphs, if we allow for randomization. The algorithm is randomized
and works on directed graphs. We obtain an update time of $O(n^{1.7035})$,
improving upon the previous best $O(n^{1.7643})$ [San05, BNS19].

See 1.7

###### Proof.

Given graph $G$, we sample a random hitting set $H$ of size $\tilde{O}(n/h)$
and add $s,t$ to this set. With high probability, this set partitions the
shortest $st$-path into paths $v\to v^{\prime}$ (with $v,v^{\prime}\in H$) of
length $\leq h$. We maintain the pairwise $h$-bounded distances for $H\times
H$ via the data structure of Corollary 5.5. After each update, we construct a
graph $G^{\prime}=(H,E^{\prime})$ on vertex set $H$ with edges whose weight
matches the maintained $h$-bounded distances. The $st$-distance in $G$ can now
be computed by running Dijkstra’s algorithm on $G^{\prime}$ in
$\tilde{O}((n/h)^{2})$ time. This complexity is subsumed by the time required
by Corollary 5.5 to maintain the $H\times H$ distances (i.e. the weights to be
used to construct $G^{\prime}$.

As the result is w.h.p. correct and exact, no information about the random
choices is leaked to the adversary. ∎