# Deterministic Fully Dynamic SSSP and More

Jan van den Brand School of Computer Science, Georgia Institute of Technology,
USA<EMAIL_ADDRESS>Adam Karczmarz University of Warsaw and IDEAS NCBR,
Poland<EMAIL_ADDRESS>Partially supported by the ERC CoG grant
TUgbOAT no 772346 and the National Science Centre (NCN) grant no.
2022/47/D/ST6/02184.

###### Abstract

We present the first non-trivial fully dynamic algorithm maintaining exact
single-source distances in unweighted graphs. This resolves an open problem
stated in [San05, BN19]. Previous fully dynamic single-source distances data
structures were all approximate, but so far, non-trivial dynamic algorithms
for the exact setting could only be ruled out for polynomially weighted graphs
[AW14]. The exact unweighted case remained the main case for which neither a
subquadratic dynamic algorithm nor a quadratic lower bound was known.

Our dynamic algorithm works on directed graphs and is deterministic, and can
report a single-source shortest paths tree in subquadratic time as well. Thus
we also obtain the first deterministic fully dynamic data structure for
reachability (transitive closure) with subquadratic update and query time.
This answers an open problem from [BNS19].

Finally, using the same framework we obtain the first fully dynamic data
structure maintaining all-pairs $(1+\epsilon)$-approximate distances within
non-trivial sub-$n^{\omega}$ worst-case update time while supporting optimal-
time approximate shortest path reporting at the same time. This data structure
is also deterministic and therefore implies the first known non-trivial
_deterministic worst-case_ bound for recomputing the transitive closure of a
digraph.

###### Contents

  1. 1 Introduction
    1. 1.1 Our results
    2. 1.2 Further related work
    3. 1.3 Technical ideas
    4. 1.4 Organization
  2. 2 Preliminaries
  3. 3 Technical outline
    1. 3.1 Algebraic toolbox and previous approaches
    2. 3.2 Combinatorial plug-ins to the algebraic data structure
    3. 3.3 Maintaining most $h$-bounded shortest paths under deletions
    4. 3.4 Maintaining $h$-bounded distances beyond the preprocessed pairs
    5. 3.5 Speeding up queries by hitting set-based sparsification
    6. 3.6 Fully dynamic $(1+\epsilon)$-approximate APSP with non-trivial worst-case update bound and optimal path-reporting
    7. 3.7 Deterministic fully-dynamic transitive closure with an unconditional sub-$n^{\omega}$ update bound
    8. 3.8 Randomized improvements
  4. 4 Reporting paths via grouping into blocks
  5. 5 Maintaining most $h$-bounded shortest paths under deletions
  6. 6 Fully dynamic single-source shortest paths
  7. 7 Fully dynamic path-reporting transitive closure and approximate APSP
  8. 8 Deterministic fully dynamic transitive closure faster than $O(n^{\omega})$ for all $\omega>2$
  9. 9 Randomized improvements
    1. 9.1 Path-reporting transitive closure
    2. 9.2 SSSP
  10. A Algebraic data structure (Theorem 3.1)
  11. B Omitted proofs

##  1 Introduction

The dynamic shortest path problem is a classic problem in graph algorithms
that seeks to maintain the shortest path distances between pairs of vertices
in a graph as the graph is subject to updates such as edge insertions,
deletions, or weight changes. This problem and its variants have been
extensively studied in the theoretical computer science literature, and
different algorithmic approaches have been proposed and analyzed depending on
the nature of the updates (incremental [AIMN91, GWW20, HKN13, KMS22, KMG22,
CZ21], decremental [BHS07, EFGW21, ES81, BC16, BGS20, BGW20, BR11, Ber16,
CS21] or fully dynamic [Kin99, DI01, Tho04, Tho05, HK95, BFN22, BHG+21, San05,
AvdB23, ACG12]) and the type of queries ($st$ [BNS19, HKNS15, AW14], single-
source [BN19, BC17, Ber17, CK19, Chu21, HKN14, GW20a, BGS21] or all-pairs
[DI04, ACK17, GW20b, CZ23, Mao23, DI02, HKN16, Ber09, RZ12, ACT14]). Here,
’’incremental‘‘ refers to the setting with only edge insertions,
’’decremental‘‘ to only edge deletions, and ’’fully dynamic‘‘ to the general
setting where a graph undergoes both insertions and deletions.

Among these different variants, single-source is one of the most well-studied.
It offers a good trade-off between generality and speed, as it maintains
several distances at once while allowing much faster update times than the
all-pairs variant. It also has a simple trivial solution by recomputing the
shortest paths tree in $O(m)$ time ($O(n^{2})$ time for dense graphs) via
Dijkstra‘s algorithm after each update, which serves as a natural benchmark
for all improvements. As a result, dynamic single-source shortest paths is one
of the most prolific problems in the dynamic graphs area with major results
for different variants such as incremental [GWW20, CZ21, HKN13, KMG22],
decremental [HKN14, GW20a, ES81, BC16, BC17, Ber17, BGS20, BGW20, BGS21, BR11,
CK19], and fully dynamic [RZ11, BN19, BFN22, BHG+21, AvdB23]. Yet, despite
being one of the most studied variants of dynamic shortest paths, the case of
_exact_ fully dynamic single source shortest paths – even in dense graphs with
$\Theta(n^{2})$ edges – has still remained open and withstood all attempts to
construct efficient data structures. Even in the weakest graph model, i.e.
undirected and unweighted graphs, no exact fully dynamic dynamic algorithm is
known other than trivial recomputation of the shortest paths after each update
via Dijkstra‘s algorithm. Previously, progress has only been made for the
$st$-case [San05, BNS19, BFN22, KS23] where an exact fully dynamic distance
can be maintained on unweighted graphs in $O(n^{1.673})$ time (i.e.,
subquadratic in $n$ and sublinear in the number of edges for a sufficiently
large density), but that approach does not extend to the single-source case.
It has been asked repeatedly to find a dynamic algorithm for dynamic single
source shortest paths since almost two decades ago; see, e.g., [DI04, Tho04].
One reason why an efficient data structure has been elusive is that on
weighted graphs (with sufficiently large positive integer weights allowed), it
is impossible to obtain a dynamic algorithm with subquadratic update time
unless the APSP conjecture is false [RZ11, AW14]. So a natural research
direction is to find an exact algorithm for the unweighted case (and any
density) which was also explicitly stated as an open problem in [San04, BN19].

######  Open Problem 1 ([DI04, Tho04, San04, BN19]).

Can one maintain fully dynamic exact shortest paths in subquadratic time (in
the number of vertices $n$) on unweighted graphs?

It was shown by Abboud and Vassilevska Williams [AW14] that dynamic
$st$-reachability and $st$-shortest path require algebraic techniques (i.e.,
fast matrix multiplication) if one hopes to beat the naive $O(n^{2})$ update
time algorithm of running BFS/Dijkstra after each update. So, an affirmative
answer to open problem 1 is only possible if we rely on algebraic techniques.
In previous work, the algebraic perspective requires dynamic algorithms to
perform calculations involving very large numbers, and to reduce the bit-
length of the numbers involved, past work relied on the randomized Schwartz-
Zippel lemma (i.e., randomized polynomial identity testing) [San04, BNS19,
BS19] or performing all arithmetic modulo a random prime [KS02, DI05]. As a
result, the vast majority of algebraic data structures for dynamic graph
problems is randomized [San04, San05, San07, SM10, BHG+21, BNS19, BN19, BS19,
GR21].

Deterministic algorithms would be preferable because they allow for greater
confidence in their correctness and efficiency, as opposed to randomized
algorithms which may only offer probabilistic guarantees on correctness or
running time that do not hold in all cases. Moreover, randomized algorithms
may restrict the ’’adversary‘‘ creating the sequence of updates from being
adaptive. In contrast, deterministic algorithms avoid these issues and allow
for more predictable behavior.

For algebraic data structures, only in the case of shortest paths in the
incremental setting [KMS22] or on undirected graphs in the approximate setting
[BFN22] has derandomization been possible, which naturally excludes fully
dynamic reachability or fully dynamic shortest paths on directed graphs.
Finding a way to derandomize fully dynamic reachability has been asked in
[BNS19].

######  Open Problem 2 ([BNS19]).

Can fully dynamic $st$-reachability be solved _deterministically_ in
subquadratic time?

In other dynamic graph settings, derandomization has received a lot of
attention [CZ23, BFN22, Lac11, BGS21, BGS20, Ber17, BC17, BC16, Chu21, ACK17,
CS21, HKN16, KMS22], but for fully dynamic reachability with subquadratic
update time the question has remained open.

In this work, we answer both open problems 1 and 2. We construct a fully
dynamic algorithm that maintains _exact_ single-source shortest paths in
subquadratic update time, thus providing an answer to open problem 1. This
dynamic algorithm is deterministic and works on directed graphs, and can thus
solve fully dynamic $st$-reachability deterministically, solving open problem
2.

Finally, the framework that we use is powerful and flexible enough to also
yield new worst-case update bounds for fully dynamic
$(1+\epsilon)$-approximate all-pairs shortest paths.

###  1.1 Our results

#### SSSP

We present the first fully dynamic algorithm that can maintain _exact_ single
source distances, answering open problem 1.

######  Theorem 1.1.

Let $G=(V,E)$ be unweighted digraph. There exist the following data structures
supporting fully dynamic single-edge updates to $G$ and answering queries
about exact distances from an arbitrary query source vertex $s\in V$ to all
other vertices in $G$.

  * •

A deterministic data structure with $O(n^{1.969})$ worst-case update and query
time. (Cf. Theorem 6.3)

  * •

A Monte Carlo randomized data structure with $O(n^{1.933})$ worst-case update
and query time. (Cf. Theorem 9.3)

The algorithm works on unweighted directed graphs but could also be easily
generalized to handle small (e.g., sufficiently low-polynomial) integer
weights $[1,W]$ at the cost of a $\operatorname{poly}(W)$ multiplicative time
overhead.111Just like other algebraic data structures for exact distances
[BFN22, San05, KS23]. See e.g. [KS23]. Recall that an exact algorithm with
subquadratic update time for graphs with integer weights in $[1,n^{c}]$, where
$c>0$ is a sufficiently large constant, is impossible under the APSP
conjecture [AW14].

Previous results could maintain single-source shortest paths (or single-source
distances) only in the approximate setting [BN19, BHG+21, BFN22], or in the
partially dynamic setting [HKN14, GWW20, GW20a, HK95, HKN13, ES81, BC16, BC17,
Ber17, BGS20, BGW20, BGS21, BR11].

The data structures behind Theorem 1.1 are algebraic, i.e., make use of fast
matrix multiplication. Algebraic techniques are inevitable to obtain a non-
trivial update time [AW14]. That being said, using any subcubic matrix
multiplication algorithm (e.g., Strassen‘s) would yield subquadratic bounds in
Theorem 1.1. If $\omega=2$ (here $n^{\omega}$ is the number of operations
required to multiply two $n\times n$ matrices; currently it is known that
$\omega\leq 2.372$ [DWZ22, WXXZ23]), the deterministic update bound becomes
$\widetilde{O}(n^{2-1/30})$ and the randomized one becomes
$\widetilde{O}(n^{2-1/14})$.

Both variants can be extended, deterministically in a black-box way, to
support _SSSP tree_ reporting queries within slightly larger, albeit still
subquadaratic time (the latter one against an adaptive adversary). Concretely,
if $\omega=2$, the tree-reporting bounds are $\widetilde{O}(n^{2-1/60})$ and
$\widetilde{O}(n^{2-1/28})$, respectively, while for current bounds on
$\omega$ [AW21, GU18, DWZ22] they are $O(n^{1.985})$ and $O(n^{1.967})$,
respectively. Note our dynamic algorithms work on directed graphs, so they can
be also used to solve fully dynamic $st$-reachability deterministically. This
answers open problem 2, asked in [BNS19].

#### All-pairs problems

By reusing and extending the framework used for fully dynamic single-source
data structures, we also obtain a new data structure for fully dynamic
approximate all-pairs shortest paths, captured by the following Theorem 1.2.

######  Theorem 1.2.

Let $G=(V,E)$ be an unweighted directed graph. Let $\epsilon\in(0,1)$. There
exists a deterministic data structure explicitly maintaining all-pairs
$(1+\epsilon)$-approximate distances in $G$ under vertex updates in
$O(n^{2.293}/\epsilon)$ worst-case time per update.

The data structure can be extended to:

  * •

enable reporting a $(1+\epsilon)$-approximately shortest path $P=s\to t$ in
$G$ for query vertices $s,t\in V$ in optimal $O(|P|)$ time.

  * •

explicitly maintain _reachability trees_ from all the sources $s\in V$ within
the same update bound.

As is typically the case for fully dynamic data structures maintaining all-
pairs information explicitly (e.g., [San04, DI04, Tho04, ACK17, GW20b, CZ23,
Mao23]), the data structure supports more general _vertex updates_ that can
insert/delete any number of edges incident to a single vertex.

To the best of our knowledge, ours is the first fully dynamic APSP data
structure for _directed_ graphs allowing optimal path reporting whose worst-
case update time breaks through the
$\widetilde{O}(n^{\omega}/\epsilon)\approx\widetilde{O}(n^{2.372})$ static
$(1+\epsilon)$-approximate APSP bound of [Zwi02]. In fact, this is the case
regardless of whether randomization is used. Previous results breaking the
$\widetilde{O}(n^{\omega})$-barrier [BN19] could not report the path. Optimal
path reporting is supported by the purely-combinatorial data structures [DI04,
Tho04, ACK17, GW20b, CZ23, Mao23] but their worst-case update time is at least
$\Omega(n^{2.5})$. Better worst-case update bounds for path-reporting APSP
have been obtained using algebraic techniques [BHG+21, AvdB23] but with
_superlinear_ (in $n$, let alone in the distance between the queried vertices)
query time and necessarily under less general single-edge updates.222This is
also achieved by our SSSP data structures. Thus, prior to our work, no non-
trivial worst-case bound for fully dynamic APSP (in directed graphs) with
optimal-time path reporting has been known and recompute-from-scratch [Zwi02]
could be considered the state-of-the-art solution (indeed, the static
$(1+\epsilon)$-approximate APSP algorithm of [Zwi02] can efficiently
reconstruct paths).

The data structure of Theorem 1.2 is deterministic. Consequently, it also
constitutes the first _deterministic_ APSP data structure for _directed
graphs_ with sub-$n^{\omega}$ worst-case update time maintaining all-pairs
distance estimates _explicitly_. The fully dynamic APSP data structure of
[DI04, Tho04] is deterministic and has near-optimal $\widetilde{O}(n^{2})$
amortized update bound, but the worst-case update bound is cubic. Using
randomization, a matrix of $(1+\epsilon)$-approximate distances can be
maintained in $O(n^{2.045}/\epsilon^{2})$ worst-case time per update [BN19].
As deterministic variants of [ACK17, GW20b] have $\Omega(n^{2.5})$ update
bound, again, recompute-from-scratch [Zwi02] has been the state-of-the-art in
the deterministic regime.

The above remains true even for the easier problem of explicitly maintaining
the transitive closure under fully dynamic updates. Whereas an optimal
$O(n^{2})$ randomized worst-case update bound has been known [San04], no
_deterministic_ data structure with _worst-case_ update time beyond the
$O(n^{\omega})$-time recompute-from-scratch [Mun71] has been found. Only
_amortized_ deterministic $O(n^{2})$ update bounds have been known [DI08,
Kin99, Rod08]. Theorem 1.2 implies that the transitive closure can be
recomputed deterministically in $O(n^{2.293})$ time (worst-case) after a
vertex update. Additionally, within that bound, all-pairs reachability trees –
providing an explicit representation of paths between all pairs of vertices –
can also be constructed.

Perhaps surprisingly, for a sufficiently large improvement to $\omega$
(concretely, if $\omega\leq 2.12$), the update time of the data structure of
Theorem 1.2 (depending on the value of $\omega$) may become polynomially
smaller than $O(n^{\omega})$, i.e., slower than recomputing from scratch. It
is interesting to ask whether it is possible to reproduce any of the
accomplishments of that data structure _unconditionally_ , that is, within
sub-$n^{\omega}$ time as long as $\omega>2$.333Note that if $\omega=2$, then
all-pairs reachability can be recomputed from scratch in $O(n^{2})$ time
[Mun71] which is already the output size, so in that case no non-trivial
dynamic algorithm can exist. Using an entirely different approach, we show
this is indeed possible for deterministic fully dynamic transitive closure.

######  Theorem 1.3.

Let $G=(V,E)$. Unless $\omega=2$, there exists a constant $\epsilon_{\omega}$,
$0<\epsilon_{\omega}<\omega-2$, dependent on $\omega$, such that one can
deterministically and explicitly maintain the transitive closure of $G$ under
fully dynamic vertex updates in $O(n^{\omega-\epsilon_{\omega}})$ worst-case
time per update.

The drawback of the above data structure is that it cannot report paths in
optimal time (in their length) but merely in $O(n)$ time per query.

###  1.2 Further related work

All-pairs shortest paths (in directed graphs) and transitive closure have also
been studied extensively in partially dynamic settings [BHS07, Ber16, EFGW21,
FMNZ01, Ita86, KL19, KL20, DFNV22]. Other variants related to distances are
dynamic diameter and extreme distances [AHR+19, BN19]. There also exists work
with much larger approximation ratio, e.g. [FGNS23, ACT14, FGH21]. In addition
to upper bounds, dynamic distance problems have also been studied from a
(conditional) lower bound perspective, see e.g. [AW14, HKNS15, ABF23, ABKZ22,
AHR+19, BNS19, GWW20, JX22, RZ11].

###  1.3 Technical ideas

Our results are obtained via a combination of (inevitable) algebraic methods
and a wide range of purely combinatorial techniques. The fully dynamic single-
source shortest distances data structures follow the high-level approach of
the data structures for obtaining worst-case update bounds for exact fully
dynamic _all-pairs shortest paths_ [ACK17, GW20b, Tho05, CZ23, Mao23]. These
purely combinatorial data structures are, however, super-quadratic in many
different aspects and in fact seem to not be able to break through the
$\Omega(n^{2.5})$ barrier for the problem they solve.

We observe that a majority of computational bottlenecks therein can be
delegated to the algebraic data structures based on dynamic matrix inverse
[BNS19, San04] – again, with a few purely combinatorial extensions applied on
top, such as the recent path-reporting techniques [KMS22]. The power of
algebraic data structures is also exploited to a greater extent than before.
Previous work relied on maintaining either the entire matrix inverse (e.g.
[San04]), querying single cells or rows ([BN19, BNS19, San04]) or maintaining
well-structured (e.g., square) submatrices [San05, BFN22]. On the other hand,
we crucially need maintaining _unstructured and dynamic_ subsets of cells of
the inverse of subquadratic size and adapt the algebraic tools to this
scenario.

Finally, a common theme of all our deterministic algorithms is using weaker
notions of hitting sets of ’’long‘‘ shortest paths between pairs of vertices
whose distance exceeds some threshold $h$. In previous dynamic shortest paths
data structures, $\widetilde{O}(n/h)$-sized hitting sets are typically
randomly sampled (once) or deterministically recomputed (after an update) to
hit paths in the _current graph_.

Our single-source distances data structure, on the other hand, only employs a
(deterministically computed) hitting set to sparsify an explicit _static_
collection of $\Theta(n^{2})$ paths that is reinitialized not very often. As a
result, we completely avoid the bottleneck of all previous dynamic algebraic
distance data structures for directed graphs: maintaining the _current_ exact
$h$-bounded distances between all pairs of vertices from the hitting set. For
example, it is not clear how this component can be derandomized while keeping
the update time subquadratic.

In the data structure of Theorem 1.3, a different relaxation of hitting sets
(specific to reachability, where hitting _shortest paths_ is not required for
vertices far apart) is exploited. In particular, we describe a deterministic
trade-off between the size of such a relaxed hitting set and the time needed
to compute it, which we believe may be of independent interest.

###  1.4 Organization

We start by giving preliminaries in Section 2 and then give a more detailed
technical outline of our algorithms in Section 3. Our algorithms rely on
constructing hitting sets that require low-hop shortest paths. We describe in
Section 4 how to extract these required paths from a dynamic bounded-distances
algorithm. Next, in Section 5 we describe a subcubic preprocessing step that,
using the algebraic path-reporting data structures, finds a collection of
paths that is robust (in a sense) in the decremental setting. Finally, we
employ that preprocessing of Section 6 to obtain our fully dynamic SSSP data
structure (Theorem 1.1). The extension to fully-dynamic path-reporting APSP
(Theorem 1.2) is described in Section 7. The deterministic fully dynamic
transitive closure data structure beating the $n^{\omega}$-barrier for all
$\omega>2$ (Theorem 1.3) is given in Section 8.

##  2 Preliminaries

Let $G=(V,E)$ be a directed graph. For $D\subseteq V$, we denote by $G-D$ the
graph $G$ with all edges incident to the vertices $D$ removed.

For any $s,t\in V$ and $k\geq 0$, $\delta_{G}^{k}(s,t)$ is the minimum length
of an $s\to t$ path in $G$ with at most $k$ edges (hops). If no such path
exists, $\delta_{G}^{k}(s,t)=\infty$. A  _shortest $k$-bounded_ $s\to t$ path
in $G$ is an $s\to t$ path with at most $k$ hops and length
$\delta_{G}^{k}(s,t)$. The $s,t$-distance $\delta_{G}(s,t)$ is defined as
$\delta_{G}^{n}(s,t)$.

##  3 Technical outline

This section focuses, in the first place, on giving a technical overview of
the deterministic fully dynamic SSSP data structure. We then briefly describe
the changes needed for path-reporting $(1+\epsilon)$-approximate APSP, and the
possible improvements using randomization.

###  3.1 Algebraic toolbox and previous approaches

Recall that by the conditional lower bound of [AW14], using algebraic fast
matrix multiplication-based techniques is inevitable even for fully dynamic
$st$-reachability. In the following we review how the state-of-the art
randomized data structures for $st$-distances and reachability use algebraic
techniques, explain the limitations of their approaches, and introduce the
algebraic data structure that we use.

Let $h\in[1,n]$ be a threshold parameter setting the boundary between
’’short‘‘ shortest paths with at most $h$ edges, and ’’long‘‘ shortest paths
with more than $h$ edges. Just like all previously described algebraic data
structures maintaining shortest paths, we leverage dynamic matrix inverse data
structures for maintaining the $h$-bounded distances between certain pairs of
vertices.

#### Path counting

The main idea behind algebraic $h$-bounded distances data structures is
counting (possibly implicitly) paths of given lengths $0,\ldots,h$ for all
source-target pairs. Note that the number of length-$k$ paths between a given
pair of vertices of an unweighted graph is no more than $n^{k}$, i.e., could
take $\widetilde{O}(k)$ bits to be represented. As a result, storing the
required path counts for a given pair might require up to
$\widetilde{O}(h^{2})$ bits. It is the most convenient to represent the counts
as a degree-$h$-polynomial matrix, where the coefficient of $x^{k}$ of the
polynomial in the cell $(s,t)$ equals the count of $s\to t$ paths of length
$k$. As originally observed by [San05], such a matrix equals the inverse of
the matrix $I-x\cdot A$ modulo $x^{h+1}$, where $A$ is the adjacency matrix of
$G$. Since the single-edge updates to $G$ correspond to single-element updates
to $I-x\cdot A$, maintaining the required path counts reduces to maintaining
matrix inverse under single-element updates. This enables using dynamic matrix
inverse data structures [San04, BNS19, BFN22] with $\widetilde{O}(h^{2})$
arithmetic operation cost incurred by working with $h$-degree polynomials with
$\widetilde{O}(h)$-bit coefficients.

For deciding whether a path of a given length exists, it is enough to be able
to test whether a path count is non-zero. By operating modulo a random
$\Theta(\log{n})$-bit prime number, whether the individual counts are non-zero
can be maintained by operating on $\widetilde{O}(1)$-bit polynomial
coefficients instead (see, e.g., [KS02, DI05]). This saves a factor of $h$ in
the time cost, but inevitably leads to a Monte Carlo randomized algorithm
correct with high probability. The previous fully dynamic reachability data
structures in DAGs [KS02, DI05] and exact $st$-distances [San05, BFN22]
crucially relied on this idea. In particular, the data structures tailored to
reachability [KS02, DI05] do not keep track of path lengths and do not
differentiate between short and long paths; they do apply path counting though
(with counts of order $n^{n}$) and thus this trick saves a factor $n$ there.

#### Previous dynamic distances data structures

The fully dynamic $st$-distances data structures [San05, BFN22] apply path
counting in combination with the well-known hitting set trick [UY91]. If one
samples a subset $H\subseteq V$ of size $\Theta((n/h)\log{n})$, then for all
$u,v\in V$ with $\delta_{G}(u,v)\geq h$, some shortest $u\to v$ path contains
a vertex of $H$ w.h.p. Another view on this property is that for any $s,t\in
V$, some shortest $s\to t$ path in $G$ can be decomposed into subpaths of
length at most $h$ with both endpoints in $H\cup\\{s,t\\}$. Therefore, given
$\delta^{h}_{G}(u,v)$ for all $u,v\in H\cup\\{s,t\\}$, we can find a shortest
$s\to t$ path in $G$ using Dijkstra‘s algorithm on a digraph on
$H\cup\\{s,t\\}$ with $O(|H|^{2})=\widetilde{O}((n/h)^{2})$ edges. Maintaining
the $\widetilde{O}((n/h)^{2})$ pairwise $h$-bounded distances between the
vertices $H\cup\\{s,t\\}$ requires at least $\widetilde{O}((n/h)^{2}\cdot
h)=\widetilde{O}(n^{2}/h)$ bits when using path counting modulo a prime.

This simple approach seems hopeless if we either wanted to make it work for
the more general single-source distances maintenance, or to have a
deterministic dynamic $st$-distance data structure. In the former case, we
would need to maintain $h$-bounded distances between $O(n^{2}/h)$ pairs
${(H\cup\\{s\\})\times V}$. But the current path counting techniques assume at
least $\Theta(h)$ ’’arithmetic‘‘ overhead for maintaining one value
$\delta^{h}_{G}(u,v)$ even when counting modulo a random prime. This makes the
single-source case inherently quadratic using this approach. Similarly,
deterministic maintenance of a single value $\delta^{h}_{G}(u,v)$ has
$\widetilde{\Theta}(h^{2})$ ’’arithmetic‘‘ overhead, which makes the approach
of [San05, BFN22] inapplicable not only for maintaining $st$-distance
deterministically, but also for fully dynamic deterministic $st$-reachability
which is likely an easier problem.

#### Our $h$-bounded distances data structure

At the end of the day, we do not overcome the aforementioned inherent
arithmetic overheads of either $\widetilde{\Theta}(h)$ (randomized) and
$\widetilde{\Theta}(h^{2})$ (deterministic). Instead, we rely, in a crucial
way, on the ability of the dynamic matrix inverse data structure [San04] to
maintain an arbitrary _dynamic_ $k$-cell _submatrix of interest_ of the
inverse, possibly with no structure whatsoever, using a subquadratic number of
field operations, unless $k=n^{2-o(1)}$ or significantly more than $\Theta(n)$
cells of interest are added per element update. Specifically, we show the
following:

######  Theorem 3.1 (Modification to [San05], proof in Appendix A).

Let $G=(V,E)$ be a fully dynamic unweighted digraph. Let $h\in[1,n]$. Let
${Y\subseteq V\times V}$ be a dynamic set. For any $\mu,\delta\in[0,1]$, there
exists a deterministic data structure maintaining the values
$\delta_{G}^{h}(s,t)$ for all $(s,t)\in Y$ and supporting:

  * •

single-edge updates to $G$ in
$\widetilde{O}(h^{2}\cdot(n^{\omega(1,\mu,1)-\mu}+n^{1+\mu}+|Y|))$ worst-case
time,

  * •

batches of at most $n^{\delta}$ _vertex updates_ to $G$ in
$\widetilde{O}(h^{2}n^{\omega(1,\delta,1)})$ worst-case time,

  * •

single-element insertions to $Y$ in $\widetilde{O}(h^{2}n^{\mu})$ time,

  * •

removing elements from $Y$ in $O(1)$ time.

Crucially, for small-polynomial values of $h$, sets $Y$ of size
$n^{2-O(1)}/h^{2}$, and appropriately chosen $\mu$, say $\mu=1/2$, the single-
edge update time bound of this data structure is subquadratic in $n$.

To the best of our knowledge, previous algebraic dynamic graph data structures
required only very structured submatrices $Y$ of the inverse to operate. For
example, the aforementioned $st$-distance data structures [San05, BFN22] use a
square submatrix with rows and columns ${H\cup\\{s,t\\}}$. In fact, [BFN22]
show a more efficient (than Theorem 3.1) data structure for square inverse
submatrix maintenance: the dependence on $n$ in the single-edge update bound
of Theorem 3.1 is at least $n^{1.529}$ ($n^{1.5}$ if $\omega=2$), whereas
[BFN22] achieve the dependence of $n^{1.406}$ ($n^{1.25}$ if $\omega=2$).

###  3.2 Combinatorial plug-ins to the algebraic data structure

On top of the data structure Theorem 3.1, we apply two crucial black-box
enhancements.

#### Induced subgraph operations or vertex switching

First, we will need to maintain $h$-bounded distances not only in the graph
$G$, but also in an _induced subgraph_ $G[W]$, where the set $W\subseteq V$ is
also subject to updates. This functionality models temporarily switching some
vertices off, or, equivalently, removing all their incident edges.

A very simple but powerful observation is that in directed graphs, switching
vertices can be modeled using single-edge updates. This follows by applying a
standard reduction of splitting a vertex $v$ into an in-copy $v^{+}$ and an
out-copy $v^{-}$, connected by an edge $v^{+}v^{-}$ switched on iff $v\in W$.
As a result, even though switching a vertex off forbids using up to $n$ edges,
modeling it costs no more than a single-edge update to the data structure
maintaining the graph. Recall that the single-edge update cost in Theorem 3.1
is subquadratic if the parameters are appropriately set.

#### Path reporting via grouping into blocks

A well-known shortcoming of path-counting $h$-bounded distances data
structures is that they do not allow, out-of-the-box, reporting the shortest
$h$-bounded paths. The data structures we develop internally require the path-
reporting functionality (against an adaptive adversary) even for maintaining
the single-source distances only.

To this end, we make use of a recent technique of [KMS22] used therein for
DAGs to convert a fully dynamic single-source reachability data structure into
a fully dynamic single-source _reachability tree_ reporting data structure. We
apply this technique in the case of $h$-bounded distances.

The overall idea is as follows. Having fixed a parameter $b\in[1,n]$, the
_block size_ , the vertex set $V$ is split into $\ell\leq\lceil n/b\rceil$
blocks $V_{1},\ldots,V_{\ell}$ of no more than $b$ vertices. Via vertex-
splitting, we can construct $\ell$ related graphs $G_{1},\ldots,G_{\ell}$ such
that a shortest $h$-bounded $s\to t$ path in $G$ is preserved in $G_{i}$ iff
the penultimate vertex is in the blocks $V_{1}$ through $V_{i}$.

Suppose we maintain the $h$-bounded distances data structures (of Theorem 3.1)
on the graphs $G_{1},\ldots,G_{\ell}$. Then, given a source $s\in V$ and
single-source $h$-bounded distances $\delta^{h}_{G_{i}}(s,\cdot)$ for all $i$,
we can identify, for each $t\in T$, at most $b$ potential predecessors $p$ for
which some shortest $h$-bounded $s\to t$ path has a penultimate vertex $p$.
Given those, the single-source shortest $h$-bounded paths tree can be
constructed in $O(nb)$ time by simply running BFS on an $O(nb)$-sized subgraph
of $G$.

Overall, if the dynamic $h$-bounded distances data structure has update time
$U(n,h)$ and can compute single-source $h$-bounded distances in $Q(n,h)$ time,
then grouping into blocks yields a data structure with update time
$O\left(\frac{n}{b}\cdot U(n,h)\right)$ reporting single-source $h$-bounded
shortest paths in $O\left((n/b)Q(n,h)+nb\right)$ time. In Section 4 we also
describe a refinement of this reduction that can produce better running times;
see Lemma 4.2.

Although we need path reporting even internally for the sole purpose of
maintaining single-source distances, note that grouping into blocks allows for
converting – in a _deterministic_ and black-box way – any _truly subquadratic_
single-source distances data structure into a SSSP-tree reporting data
structure. For example, if the single-source distances data structure (i.e.,
$h=n$) has $U(n,h),Q(n,h)\in O(n^{1.98})$, it is enough to set $h=n$ and
$b=n^{0.99}$ to get $O(n^{1.99})$-time SSSP tree reporting. Therefore, in the
remaining part of this outline we only discuss maintaining single-source
distances deterministically.

###  3.3 Maintaining most $h$-bounded shortest paths under deletions

Overall, our fully dynamic single-source distances data structure follows the
high-level idea of the known _combinatorial_ fully dynamic APSP data
structures with subcubic _worst-case_ update time, first shown by [Tho05] and
subsequently developed in [ACK17, CZ23, GW20b, Mao23].

The data structure operates in phases of $\Delta=n^{\delta}$ updates, where
$\delta\in(0,1)$. At any moment of time, let $G$ denote the current graph
(with all updates issued so far applied), and let $G_{0}$ reflect how $G$
looked like when the current phase started. While the phase proceeds, let $D$
denote the set of $\leq 2\Delta$ _affected vertices_ , i.e., those
constituting the endpoints of all the edges inserted or deleted in the current
phase. Note that we have $G-D=G_{0}-D\subseteq G$ at any time.

Each phase starts with a relatively costly preprocessing step whose purpose is
to find a certain collection of $O(n^{2})$ paths $\Pi$ in $G_{0}$
accomplishing the following informal goals:

  1. (a)

$\Pi$ contains all-pairs $h$-bounded shortest paths in a _large_ subgraph of
$G_{0}-D$.

  2. (b)

removing $D$ from $G$ keeps _most_ of the paths in $\Pi$ intact.

More precisely, we use the following lemma inspired by the preprocessing in
[GW20b].

######  Lemma 3.2.

Let $G=(V,E)$ be a directed graph. Let $h,\tau\in[1,n]$. Assume one has
constructed a _deterministic_ data structure storing $G$ and a subset
$W\subseteq V$ initially equal to $V$, and supporting:

  1. (1)

updates removing a vertex from $W$,

  2. (2)

queries computing shortest $h$-bounded paths in $G[W]$ from a query vertex $s$
to _all_ $v\in V$.

Suppose one can perform updates in $U(n,h)$ _worst-case_ time, and queries in
$Q(n,h)$ time.

In $O(n^{2}h+(n/\tau)\cdot U(n,h)+n\cdot Q(n,h))$ time one can compute a set
$C\subseteq V$ of size $O(n/\tau)$, and a collection of paths $\Pi$ in $G$,
containing at most one path $\pi_{s,t}$ for all $s,t\in V$, such that:

  1. (a)

For any $s,t\in V$, if $\delta_{G-C}^{h}(s,t)\neq\infty$, then
$\pi_{s,t}\in\Pi$ exists and is an $s\to t$ path in $G$ of length at most
$\delta_{G-C}^{h}(s,t)$.

  2. (b)

For any $u\in V$, there exist at most $O(hn\cdot\tau)$ paths $\pi_{s,t}\in\Pi$
with $u\in V(\pi_{s,t})$.

After the algorithm completes, the assumed data structure is reverted back to
the state when $W=V$.

We call $\tau$ and $C$ in Lemma 3.2 the _congestion threshold_ and the
_congested subset_ , respectively. The preprocessing of Lemma 3.2, applied to
$G_{0}$ with a small-polynomial $\tau$ and $h$, achieves the goal (a) since
the obtained collection $\Pi$ contains paths at least as short as shortest
$h$-bounded paths in $G_{0}-(C\cup D)$. Note that $G_{0}-(C\cup D)$ forms a
_large_ subgraph of $G_{0}-D$ because the obtained set of congested vertices
$C$ has sublinear size. It also achieves the goal (b) since the
$O(hn\cdot\tau\cdot\Delta)$ paths in $\Pi$ containing a vertex from $D$ (let
us denote them by $\Pi_{D}$) constitute a relatively small portion of the
entire collection $\Pi$ containing typically $\Theta(n^{2})$ paths.

Using purely combinatorial data structures, the preprocessing of Lemma 3.2
takes $\Theta(n^{3})$ time for dense graphs, which is prohibitive in our case
since it is meant to be applied once per $\Delta$ updates. However, by
plugging in the data structure $\mathcal{T}$ of Theorem 3.1, extended with
induced subgraph operations and path-reporting capabilities (with an
appropriately chosen block size $b\in[1,n]$, as explained in Section 3.2), we
can manage to compute the pair $(\Pi,C)$ in subcubic time upon the start of
the phase. For large enough $\Delta$, this incurs a subquadratic _amortized_
update cost. However, we remark that the heavy super-quadratic preprocessing
(which constitutes the only source of amortization here) is scheduled
precisely every $\Delta$ updates and consequently the data structure can be
deamortized using a standard technique; see, e.g., [ACK17, BNS19, Tho05].

###  3.4 Maintaining $h$-bounded distances beyond the preprocessed pairs

The preprocessing of Lemma 3.2 applied at the beginning of a phase guarantees
that $h$-bounded distances in $G_{0}-(C\cup D)=G-(C\cup D)$ are maintained for
all $(s,t)$ such that either $\delta_{G_{0}-C}(s,t)=\infty$ holds, or
$\pi_{s,t}\in\Pi\setminus\Pi_{D}$, that is, we have $\delta_{G_{0}-(C\cup
D)}^{h}(s,t)=|\pi_{s,t}|$.

We delegate maintaining $h$-bounded distances (in $G$) either corresponding to
paths going _through_ $C\cup D$ and/or for the _affected pairs_ $(s,t)$ such
that $\pi_{s,t}\in\Pi_{D}$ to a separate data structure $\mathcal{A}$ of
Theorem 3.1 maintaining the current graph $G$. More specifically, we define
the set $Y\subseteq V\times V$ (identified with the submatrix $Y$ of interest
in $\mathcal{A}$, see Theorem 3.1) to contain, at any time:

  * •

all pairs $((C\cup D)\times V)\cup(V\times(C\cup D))$,

  * •

all pairs $(s,t)$ such that $\pi_{s,t}\in\Pi_{D}$.

Note that the size of $Y$ is bounded by $O(n^{2}/\tau+n\Delta+\Delta hn\tau)$
at all times, which incurs a per-update cost of $O(h^{2}n^{2}/\tau+\Delta
h^{3}n\tau)$ for maintaining $\delta_{G}^{h}(s,t)$ for all $(s,t)\in Y$ in the
data structure $\mathcal{A}$. Moreover, we crucially rely on the low-recourse
property of the set $Y$: it grows by at most $O(hn\tau)$ elements (worst-case)
per update, as $D$ grows by at most two elements per update. This allows to
augment the submatrix of interest in $\mathcal{A}$ in $O(h^{3}n^{1+\mu}\tau)$
time per update. We point out that it is the affected pairs that cause the
submatrix of interest $Y$ to be of a rather arbitrary shape beyond our
control; the remaining part of $Y$ is composed of some $O(n/\tau+\Delta)$ full
rows and columns.

###  3.5 Speeding up queries by hitting set-based sparsification

Let $s\in V$ be some query vertex. Suppose we want to compute single-source
distances from $s$ in $G$. First of all, using the data structure
$\mathcal{A}$ we can temporarily add all pairs $(s,t)$, $t\in V$, to the set
$Y$ so that we can also access single-source $h$-bounded distances from $s$.
This costs $\widetilde{O}(h^{3}n^{1+\mu})$ time.

With such an augmented set $Y$, one can prove (see Lemma 6.2) that for each
$t$, there exists a shortest path $P=s\to t$ in $G$ obtained by stitching
paths of one of the following kinds:

  1. (i)

a shortest $h$-bounded path $u\to v$, where $(u,v)\in Y$,

  2. (ii)

a path $\pi_{u,v}\in\Pi\setminus\Pi_{D}$ such that $|\pi_{u,v}|\geq h/2$.

Consequently, we could build a graph $X$ with edges $(u,v)\in Y$ of weight
$\delta_{G}^{h}(u,v)$ (maintained by $\mathcal{A}$) and edges $(u,v)$ for all
non-affected pairs with $\pi_{u,v}\in\Pi\setminus\Pi_{D}$, and run Dijkstra‘s
algorithm on $X$ to obtain single-source distances from $s$ in $G$. The number
of edges of the former kind is $O(n^{2}/\tau+hn\Delta\tau)$, i.e.,
subquadratic. However, the number of edges of the latter kind can be still
$\Theta(n^{2})$. Fortunately, these edges represent relatively long
$\Theta(h)$-hop paths, and this can be exploited as follows. During the
preprocessing at the beginning of a phase, after computing the collection
$\Pi$, we compute an $\widetilde{O}(n/h)$-sized hitting set $H$ of the paths
in $\Pi$ composed of at least $h/2$ edges. This can be done deterministically
in $\widetilde{O}(n^{2}h)$ time using a folklore greedy algorithm. For each of
these paths $\pi_{u,v}$, we pick one $z_{u,v}\in H\cap V(\pi_{u,v})$ as a
representative of the hitting set for that path.

To be able to efficiently compute single-source distances upon query, we
sparsify the lengths of the $O(n^{2})$ paths of type (ii) using only
$\widetilde{O}(n^{2}/h)$ edges. For each $(z,v)\in H\times V$, we use an edge
$zv$ of weight equal to the minimum length of the $z\to v$ suffix of a path
$\pi_{u,v}\in\Pi\setminus\Pi_{D}$ such that $z_{u,v}=z$. Similarly, for each
$(u,z)\in V\times H$, we use an edge $uz$ of weight equal to the minimum
length of the $u\to z$ prefix of a path $\pi_{u,v}\in\Pi\setminus\Pi_{D}$ with
$z_{u,v}=z$. These auxiliary edges can be efficiently maintained subject to
insertions to $D$ (equivalently, deletions from $\Pi\setminus\Pi_{D}$). Using
the auxiliary edges in place of explicit edges for all the non-affected paths
decreases the size of the graph $X$ to $O(n^{2}/\tau+hn\Delta\tau+n^{2}/h)$
which is subquadratic for a proper choice of parameters.

We remark that our usage of hitting sets is conceptually different compared to
previous dynamic shortest paths algorithms. There, hitting sets are typically
used to hit long-hop paths in the _current_ graph, most commonly by using
randomization to ensure a once-sampled hitting set is valid for
$\operatorname{poly}(n)$ (future) versions of the graph (e.g., in [ACK17,
San05, BFN22]). In our case, we use it merely for the sake of sparsification
of some statically precomputed set of paths and do not require maintaining the
current all-pairs $h$-bounded distances between the vertices of the hitting
set.

###  3.6 Fully dynamic $(1+\epsilon)$-approximate APSP with non-trivial worst-
case update bound and optimal path-reporting

In order to obtain the deterministic all-pairs data structures supporting
optimal-time path reporting, we build upon the framework that we have used for
single-source distances. First of all, to be competitive with the known all-
pairs reachability and APSP data structures, we need to support more complex
_vertex updates_. Fortunately, the SSSP framework can be seen to allow
decremental vertex updates within a phase, and only relies on the single-edge
updates assumption (i.e., that every updated edge has _both_ endpoints in $D$)
in the query procedure. Moreover, the data structure of Theorem 3.1 supports
batch-vertex updates, which we leverage when advancing to the next phase.

In our all-pairs data structures, the single-source query procedure is
replaced by _explicitly rebuilding_ a collection $\Pi^{\prime}$ (containing,
in particular, the unaffected paths $\Pi\setminus\Pi_{D}$) of $h$-bounded
paths $\pi^{\prime}_{u,v}$ for the $O(hn\Delta\tau)$ affected pairs $(u,v)$
(with $\pi_{u,v}\in\Pi_{D}$) satisfying similar guarantees wrt. the
$h$-bounded distances in $G-(C\cup D)$. This is achieved via another
application of the data structure of Theorem 3.1, enhanced as described in
Section 3.2. Importantly, this allows for optimal-time reporting of
$h$-bounded paths in $G$ that are at least as short as those appearing in
$G-(C\cup D)$.

With the shortest $h$-bounded paths $\Pi^{\prime}$ improving upon those in
$G-(C\cup D)$ rebuilt, we deterministically compute an
$\widetilde{O}(n/h)$-sized hitting set $H$ of the $\Theta(h)$-hop paths in
$\Pi^{\prime}$. One can show that for every pair $(s,t)$, either
$\pi^{\prime}_{s,t}\in\Pi^{\prime}$ is a shortest $s\to t$ path in $G$, or
there is a shortest path $P=s\to t$ in $G$ with a vertex in $C\cup D\cup H$
appearing on each $h$-hop segment of $P$. If $|C\cup D\cup H|\leq n^{\alpha}$,
for some $\alpha<1$, then this allows computing all-pairs shortest paths of
the latter kind using $O(\log{n})$ min-plus products of matrices whose at
least one dimension is bounded by $O(n^{\alpha})$. Such products can be
computed polynomially faster than products of full $n\times n$ matrices, even
without resorting to non-trivial rectangular matrix multiplication algorithms
[GU18, HP98]. Sadly, in our case, using exact min-plus product for this task
does not yield an improved worst-case update bound over the known exact APSP
data structures [ACK17, GW20b] with subcubic worst-case update bounds.

However, if we use the $(1+\epsilon)$-approximate min-plus product [Zwi02]
(where $\epsilon\in(0,1]$) we can perform this computation approximately in
sub-$n^{\omega}$ time $\widetilde{O}(n^{\omega(1,\alpha,1)}/\epsilon)$. The
approximate min-plus product can also produce matrix multiplication witnesses
within the same bound deterministically. Those, in turn, can be used to
recover, for any query pair $(s,t)$, some $s\to t$ path of length at most
$(1+\epsilon)\cdot\delta_{G}(s,t)$ in optimal $O(\delta_{G}(s,t))$ time.

For the special case of all-pairs reachability (i.e., any finite approximation
of shortest paths), another application of matrix multiplication witnesses can
yield a stronger path-reporting interface. Namely, within
$O(n^{\omega(1,\alpha,1)})$ time we can also explicitly recompute all-pairs
reachability trees.

Finally, we remark that, at the end of the day, due to the overheads of the
preprocessing and rebuilding short-hop paths, the worst-case update time of
this data structure is faster than the recompute-from-scratch bound
$\widetilde{O}(n^{\omega}/\epsilon)$ only conditionally, if $\omega\geq 2.12$.

###  3.7 Deterministic fully-dynamic transitive closure with an unconditional
sub-$n^{\omega}$ update bound

For the fully dynamic transitive closure problem, we show that the
deterministic sub-$n^{\omega}$ worst-case update time can be attained unless
$\omega=2$. We achieve that using a different and simpler approach.

Recall that a randomly sampled hitting set of size $\widetilde{O}(n/h)$ hits
some polynomial number of fixed $\geq h$-hop _shortest paths_ with high
probability. Roughly speaking, given any such hitting set $H$ of size at most
$n^{\alpha}$, $\alpha<1$, we can separately compute reachability through $H$
using rectangular matrix multiplication in $O(n^{\omega(1,\alpha,1)})$ time,
and delegate maintaining all-pairs $h$-bounded distances to the deterministic
data structure of Theorem 3.1 with $\widetilde{O}(h^{2}n^{2})$ worst-case
update time per vertex update. However, whereas such a hitting set $H$ is
trivial to obtain using randomization, it is not clear whether it can be
computed deterministically even in $O(n^{\omega})$ time.

Our main idea is to use a weaker – both qualitatively and quantitatively –
notion of a hitting set of $\geq h$-hop paths. First of all, for the purposes
of reachability, it is enough that for any $s,t\in V$ with
$\delta_{G}(s,t)\geq h$, the hitting set $H$ hits an $h$-edge prefix of _some_
(not necessarily shortest) $s\to t$ path. Such a qualitatively weaker hitting
set of size $\widetilde{O}(n/h)$ can be computed based on all-pairs
reachability trees, computable in $\widetilde{O}(n^{\omega})$ deterministic
time [AGMN92].

Second, a larger (but still sublinear) hitting set with the same guarantee can
be computed more efficiently. Specifically, we show that if we are willing to
accept a hitting set of size $\widetilde{O}((n/d)\cdot(n/h))$, for a parameter
$d\in[1,n]$, where $d\cdot h=\Omega(n)$, then it can be constructed
deterministically in $\widetilde{O}(n^{2}+nd^{\omega-1})$ time. We show that
for any value of $\omega>2$, the parameters $h$ and $d$ can be set so that the
worst-case update time of the data structure is polynomially smaller than
$n^{\omega}$.

A drawback of this data structure is that it cannot report $s\to t$ paths in
time linear in the length of the reported path, let alone in optimal
$O(\delta_{G}(s,t))$ time. That being said, paths can still be reported in
$O(n)$ time using a path reporting procedure of [KMS22].

###  3.8 Randomized improvements

Using randomization, we can slightly improve the update bounds of both the
SSSP data structure and the $(1+\epsilon)$-approximate APSP data structure.
First of all, in both cases, using path counting modulo a prime shaves an
$h$-factor from most of the terms in the update bounds. Then, the obtained
data structures become Monte Carlo randomized (correct with high probability)
but can still work against an adaptive adversary since the path counts are
never revealed.

With randomization, the update/query bound of the fully dynamic SSSP data
structure can be improved even further. Using standard
$\widetilde{O}(n/h)$-sized randomly sampled hitting sets, one can replace the
$O(n^{2})$-sized path collection of Lemma 3.2 with a different
$O(n^{2}/h)$-sized collection as used in the fully dynamic APSP data structure
of [ACK17] (see Lemma 9.1). Overall, the powerful sampled hitting set makes it
possible to avoid two components crucial in the deterministic data structure:
(a) the explicit sublinear congested subset, and (b) sparsifying the surviving
paths from the collection (since the collection has subquadratic size). It is
worth noting that since the distances output by the data structure are exact
(and thus uniquely determined by the graph), the data structure still works
against an adaptive adversary. See Section 9 for details.

##  4 Reporting paths via grouping into blocks

In this section we state a reduction, based on a technique of [KMS22] (with
some adjustments and refinements of ours), for converting data structures
maintaining distances into path-reporting algorithms. The reduction is based
on grouping vertices into blocks of size $b$, where $b$ is a parameter in
$[1,n]$. [KMS22] used this technique for converting a subquadratic dynamic
single-source reachability data structure [San04] into a subquadratic (albeit
polynomially slower) fully-dynamic single-source _reachability tree reporting_
data structure against an adaptive adversary. We apply the technique to
$h$-bounded shortest paths instead. Moreover, by using vertex blocks in a
slightly different way, we obtain a generalization (Lemma 4.2) that is
tailored to our use cases. The proofs from this section can be found in
Appendix B.

Let $G=(V,E)$ be a directed graph. Let $h\in[1,n]$. Suppose in
$I_{\mathrm{source}}(n,h)$ time one can construct a data structure
$\mathcal{D}(G)$ maintaining a graph $G$ under some type of updates (say,
single-edge or vertex updates) and supporting single-source queries computing
$\delta^{h}_{G}(s,t)$ for a given query source $s$ and all ${t\in V}$. Suppose
$\mathcal{D}(G)$ has $U_{\mathrm{source}}(n,h)$ _worst-case_ update time and
$Q_{\mathrm{source}}(n,h)=\Omega(n)$ query time, for some non-decreasing
functions $I_{\mathrm{source}},U_{\mathrm{source}},Q_{\mathrm{source}}\in
O(\operatorname{poly}(n,h))$.

Our goal is to have a data structure capable of handling the following
_submatrix predecessor queries_. Given query sets $S\subseteq V$ and
$Y\subseteq S\times V$, compute for each $(s,t)\in Y$ the predecessor vertex
on some shortest $h$-bounded $s\to t$ path (if one exists).

Observe that an immediate application of a submatrix predecessor query
$(S,S\times V)$ is computing single-source $h$-bounded shortest paths from $s$
to $v$ for all $s\in S$ and $v\in V$ such that $\delta_{G}(s,v)\leq h$.

######  Lemma 4.1.

For any $b\in[1,n]$, there exists a dynamic data structure maintaining $G$ and
supporting submatrix predecessor queries $(S,Y)$ in

$O\left(\frac{n}{b}\cdot|S|\cdot Q_{\mathrm{source}}(n,h)+|Y|\cdot b\right)$

time. The update and initialization times are $O\left(\frac{n}{b}\cdot
U_{\mathrm{source}}(n,h)\right)$ and $O\left(\frac{n}{b}\cdot
I_{\mathrm{source}}(n,h)\right)$ resp.

Now suppose that in addition to $\mathcal{D}(G)$, there is a data structure
$\mathcal{D}^{\prime}(G)$ supporting queries about $\delta^{h}_{G}(s,t)$ for
arbitrary pairs $s,t\in V$ in $Q_{\mathrm{pair}}(n,h)$ time and maintaining a
graph $G$ subject to the same type of updates as $\mathcal{D}(G)$ with worst-
case update time $U_{\mathrm{pair}}(n,h)$ and initialization time
$I_{\mathrm{pair}}(n,h)$. We can then improve the bound of Lemma 4.1.

######  Lemma 4.2.

For any $b\in[1,n]$, there exists a dynamic data structure maintaining $G$ and
supporting submatrix predecessor queries $(S,Y)$ in

$O\left(|S|\cdot Q_{\mathrm{source}}(n,h)+|Y|\cdot
Q_{\mathrm{pair}}(n,h)\cdot\log{n}+|Y|\cdot b\right)$

time. The update and initialization times are
$O\left(U_{\mathrm{source}}(n,h)+\frac{n}{b}\cdot
U_{\mathrm{pair}}(n,h)\right)$ and
$O\left(I_{\mathrm{source}}(n,h)+\frac{n}{b}\cdot
I_{\mathrm{pair}}(n,h)\right)$ respectively.

######  Remark 4.3.

The data structures of Lemmas 4.1 and 4.2 are deterministic if the assumed
data structures $\mathcal{D}(G)$ and $\mathcal{D}^{\prime}(G)$ are
deterministic. More generally, if the data structures $\mathcal{D}(G)$ and
$\mathcal{D}^{\prime}(G)$ produce correct answers within the assumed bounds
against an adaptive adversary, so do the obtained submatrix predecessor data
structures.

#### Supporting induced subgraph queries.

Later on we will also require reporting shortest $h$-bounded paths in an
induced subgraph $G[W]$ of a fully dynamic $G$, where $W\subseteq V$ is also
dynamic. This can be achieved via a simple yet powerful reduction described in
the following.

######  Lemma 4.4.

Let $h\in[1,n]$. Let $\mathcal{D}(G)$ be a data structure maintaining a fully
dynamic unweighted digraph $G=(V,E)$ subject to single-edge updates in
$U(n,h)$ time per update, and possibly also vertex updates, and supporting
submatrix predecessor queries $(S,Y)$ in $Q(|S|,|Y|)$ time.

Let $W\subseteq V$ be a dynamic subset. Then there exists a data structure
$\mathcal{D}^{\prime}$ supporting the same set of updates to $G$ and
supporting submatrix predecessor queries $(S,Y)$ in the induced subgraph
$G[W]$ in $O(Q(|S|,|Y|))$ time. $\mathcal{D}^{\prime}(G)$ processes updates to
$G$ within asymptotically the same time that $\mathcal{D}(G)$ needs for
processing the respective updates to $G$. Moreover, a single-element update to
$W$ can be performed in $O(U(n,h))$ time.

The details of the reduction can be found in Appendix B.

##  5 Maintaining most $h$-bounded shortest paths under deletions

In this section we show that with the help of algebraic fully dynamic distance
data structures storing $G$, one can preprocess $G$ in subcubic time so that
most of the $h$-bounded shortest paths in a very large subgraph of $G$ are
intact by any sufficiently small adversarially chosen set of deleted vertices.

We start with the following lemma inspired by the construction of the fully
dynamic APSP algorithms of [GW20b].

See 3.2

###### Proof.

Initially we put $C=\emptyset$ and $\Pi=\emptyset$. We will gradually extend
$C$ and $\Pi$ to make the condition (a) satisfied for more and more pairs
$(s,t)$. We maintain the invariant that the set $W$ in the assumed data
structure equals $V\setminus C$. That is, whenever a new element is added to
$C$, this is reflected in the data structure by a deletion to $W$.

Moreover, let $\alpha(v):=|\\{\pi\in\Pi:v\in V(\pi)\\}|$. Initially all values
$\alpha(\cdot)$ are zero. We maintain an invariant that $\alpha(v)\leq
2nh\tau$ for all $v\in V$. By this invariant, (b) will follow when we are
done.

We process the sources $s\in V$ one by one. For a fixed source $s$, we start
by moving to $C$ all the vertices $v\in V$ not yet in $C$ such that
$\alpha(v)>nh\tau$. Next, we compute shortest $h$-bounded paths from $s$ to
all $v\in V$ in $G[V\setminus C]$ in $Q(n,h)$ time and add them as the
respective paths $\pi_{s,t}$ (if they exist) to $\Pi$. We also update the
counters $\alpha(\cdot)$. Every $\alpha(v)$, for $v\in V\setminus C$, grows by
at most $n$ when processing the source $s$, and thus afterwards we have
$\alpha(v)\leq nh\tau+n\leq 2nh\tau$, so the invariant is satisfied. Since the
set $C$ may only grow in the process, and thus the values
$\delta_{G-C}^{h}(\cdot,\cdot)$ may only increase, the paths already in $\Pi$
satisfy (a). Moreover, after processing the source $s$, we ensure that the
condition (a) is satisfied also for all pairs $(s,t)$, $t\in V$.

Finally, to see that $|C|=O(n/\tau)$, observe that for every source
$\sum_{v\in V}\alpha(v)$ grows by at most $n(h+1)$, as each path added to
$\Pi$ has at most $h+1$ vertices. As a result, at the end $\sum_{v\in
V}\alpha(v)\leq n^{2}(h+1)\leq 2n^{2}h$. Since each $c\in C$ satisfies
$\alpha(c)>nh\tau$, we obtain $|C|\leq 2n/\tau$.

Once we have completed computing $(C,\Pi)$, we revert all the changes to the
assumed data structure, so that $W$ is again equal to $V$. This can be done
within the same bound as the the described computation since the assumed
update/query bounds are worst-case. ∎

We will repeatedly use the following deterministic algebraic data structure
maintaining $h$-bounded distances of a fully dynamic graph $G$ subject to
single-edge updates and/or vertex updates. This data structure encapsulates
and extends various earlier developments of [San04, San05, BFN22]. The full
proof is given in Appendix A.

See 3.1

#### The path-reporting data structure $\mathcal{T}$.

Let us apply the construction of Lemma 4.2 on top of the the data structure of
Theorem 3.1, and subsequently augment it with induced subgraph operations as
described in Lemma 4.4. This way, we obtain a data structure $\mathcal{T}$
required by Theorem 3.2.

More specifically, in terms of Lemma 4.2, the data structure of Theorem 3.1
satisfies

$\displaystyle Q_{\mathrm{source}}(n,h)$
$\displaystyle=\widetilde{O}(h^{2}n^{1+\mu}),$ $\displaystyle
Q_{\mathrm{pair}}(n,h)$ $\displaystyle=\widetilde{O}(h^{2}n^{\mu}),$
$\displaystyle U_{\mathrm{source}}(n,h)=U_{\mathrm{pair}}(n,h)$
$\displaystyle=\widetilde{O}(h^{2}(n^{1+\omega(1,\mu,1)-\mu}+n^{1+\mu})).$

Consequently, for any chosen $b\in[1,n]$, the data structure $\mathcal{T}$
supports single-edge updates to $G$ and switching off a vertex (via its
removal from $W\subseteq V$) in worst-case time

$U(n,h)=O\left(\frac{h^{2}n^{1+\omega(1,\mu,1)-\mu}}{b}+\frac{h^{2}n^{2+\mu}}{b}\right).$

It also supports reporting $h$-bounded shortest path from any single source
$s\in V$ in

$Q(n,h)=O\left(h^{2}n^{1+\mu}\log{n}+nb\right)$

time, by issuing a submatrix predecessor query $(\\{s\\},\\{(s,v):v\in V\\})$.
By plugging these bounds in Lemma 3.2 and noting that $n\cdot
Q(n,h)=\Omega(n^{2}h)$, we conclude with the following theorem which formally
captures what we mean by preserving _most_ $h$-bounded shortest paths in a
large subgraph of $G$ under a bounded number of deletions.

######  Theorem 5.1.

Let $h,\tau,b\in[1,n]$ and $\mu\in[0,1]$. Assume $G$ is maintained in a data
structure $\mathcal{T}$ of Theorem 3.1 extended as described in Lemmas 4.2 and
4.4 (for the given $b$). Then, in time

$\widetilde{O}\left(\frac{h^{2}n^{2+\omega(1,\mu,1)-\mu}}{b\tau}+\frac{h^{2}n^{3+\mu}}{b\tau}+n^{2}b\right),$

one can deterministically compute a pair $(C,\Pi)$, where $C\subseteq V$ is of
size $O(n/\tau)$, and $\Pi$ is a collection of paths in $G$, containing at
most one path $\pi_{s,t}$ for all $s,t\in V$, such that:

  1. (a)

For any $i=1,\ldots,k$ and $s,t\in V$, if $\delta_{G-C}^{h}(s,t)\neq\infty$,
then $\pi_{s,t}\in\Pi$ exists and is an $s\to t$ path in $G$ of length at most
$\delta_{G-C}^{h}(s,t)$.

  2. (b)

For any $u\in V$, there exist at most $O(hn\cdot\tau)$ paths $\pi_{s,t}\in\Pi$
with $u\in V(\pi_{s,t})$.

In our concrete applications, we will set $b$ to be slightly sublinear and
both $h$ and $\tau$ to be small-polynomial so that $n-o(n)$ vertices of $G$
remain after removing the set $C$, and a small-polynomial $\Delta$ adversarial
vertex deletions can destroy at most $O(\Delta h\tau n)=o(n^{2})$ paths in
$\Pi$.

##  6 Fully dynamic single-source shortest paths

In this section we describe our deterministic fully dynamic SSSP data
structure for unweighted graphs with truly subquadratic update and query time.

#### Phases and global data structures.

Let $h,\tau,\Delta,b\in[1,n]$ and $\mu,\nu\in[0,1]$ be parameters to be set
later. The data structure operates in phases of $\Delta$ _single-edge_
updates. It also maintains two _global_ dynamic data structures shared between
the phases:

  * •

A data structure $\mathcal{A}$ of Theorem 3.1 with $\mu:=\nu$ always storing
the current graph $G$. Every edge update issued to $G$ is immediately passed
to $\mathcal{A}$. The dynamic set $Y\subseteq V\times V$ of vertex pairs of
interest in $\mathcal{A}$, to be defined later, is initialized at the
beginning of a phase. Moreover, the set $Y$ grows by at most $O(\tau hn)$
pairs per update in the worst-case. However, we will guarantee that the size
of $Y$ is bounded by $O(n^{2}/\tau+\Delta\tau hn)$ at all times. By Theorem
3.1, the worst-case update time of $\mathcal{A}$ is:

$\widetilde{O}(h^{2}\cdot(n^{\omega(1,\nu,1)-\nu}+n^{1+\nu}+|Y|)+h^{2}\cdot\tau
hn^{1+\nu})=\widetilde{O}\left(h^{2}n^{\omega(1,\nu,1)-\nu}+\frac{h^{2}n^{2}}{\tau}+h^{3}\tau
n\cdot(\Delta+n^{\nu})\right).$

  * •

A data structure $\mathcal{T}$, as required by Theorem 5.1 and described in
Section 5, with parameters $h,b,\mu$. Every edge update issued to $G$ is
immediately passed to $\mathcal{T}$. Recall that the cost of updating
$\mathcal{T}$ incurred by a single update to $G$ is:

$U(n,h)=O\left(\frac{h^{2}n^{1+\omega(1,\mu,1)-\mu}}{b}+\frac{h^{2}n^{2+\mu}}{b}\right).$

While the phase proceeds, the set $W$ in the data structure $\mathcal{T}$
(describing the induced subgraph of interest) equals $V$ and it is only
manipulated when a phase initializes. Similarly, queries to $\mathcal{T}$ will
only be issued at the beginning of a phase.

#### Initializing a phase.

For a fixed current phase, let $G_{0}$ denote the graph $G$ at the beginning
of that phase. We always use $G$ to refer to the _current graph_ , i.e., with
all updates issued so far applied. Moreover, when a phase proceeds, let
$D\subseteq V$ be the set of endpoints of the edges affected in the current
phase, that is, the edges that have been inserted or deleted during the
current phase. Note that by the definition of $D$, we have $|D|\leq\Delta$ and
$G_{0}-D=G-D\subseteq G$ at all times.

At the beginning of a phase, we apply Theorem 5.1 to obtain a pair $(C,\Pi)$,
where $C\subseteq V$ is a ’’congested subset‘‘ of size $O(n/\tau)$, and $\Pi$
is a collection of paths in $G_{0}$. By Theorem 5.1, the amortized cost of
such a preprocessing step, happening once per $\Delta$ updates, is:

$\widetilde{O}\left(\frac{n^{2}h}{\Delta}+\frac{h^{2}n^{2+\omega(1,\mu,1)-\mu}}{b\tau\Delta}+\frac{h^{2}n^{3+\mu}}{b\tau\Delta}+\frac{n^{2}b}{\Delta}\right).$
(1)

We next deterministically compute an $\widetilde{O}(n/h)$-sized hitting set
$H$ of those paths $\pi_{s,t}\in\Pi$ _that have at least $\lfloor h/2\rfloor$
edges_. For this, we use the following folklore result (see, e.g., [Zwi02]).

######  Lemma 6.1.

Let $X$ be a ground set of size $n$ and let $\mathcal{Z}$ be a family of
subsets of $X$, each with at least $k$ elements. Then, in
$O\left(\sum_{Z\in\mathcal{Z}}|Z|\right)$ time one can deterministically
compute a _hitting set_ $R\subseteq X$ of size $O((n/k)\cdot\log{n})$ such
that $R\cap Z\neq\emptyset$ for all $Z\in\mathcal{Z}$.

The total size of $\Pi$ is $O(n^{2}h)$ and each path in $\Pi$ is a simple
path; therefore, a desired set $H$ can be computed in $O(n^{2}h)$ time. Again,
this incurs an amortized cost of $O(n^{2}h/\Delta)$ per update. which is
asymptotically the same as the first term in (1).

With the hitting set $H$ in hand, for each $\pi_{s,t}$ with
$|\pi_{s,t}|\geq\lfloor h/2\rfloor$, we arbitrarily pick a single
representative vertex $\beta(\pi_{s,t})\in H\cap V(\pi_{s,t})$. If
$|\pi_{s,t}|<\lfloor h/2\rfloor$, we put $\beta(\pi_{s,t}):=\perp$.

Let $\Pi_{D}$ denote the subset of paths $\pi_{s,t}\in\Pi$ such that
$V(\pi_{s,t})\cap D\neq\emptyset$. Recall that at the beginning of the phase
$D=\emptyset$, so $\Pi_{D}$ equals $\emptyset$ initially. The set $\Pi_{D}$
(seen as pointers to the paths in $\Pi$) can be easily extended upon
insertions to $D$ (caused by updates to $G$) in optimal time if additional
$O(n^{2}h)$ vertex-path pointers are stored for the preprocessed collection
$\Pi$.

For a simple path $p$ and $a,b\in V(p)$ let $p[a,b]$ denote the $a\to b$
subpath of $p$. Throughout a phase, for each $z\in H$ and $v\in V$, we
maintain two multisets:

$\displaystyle{\Psi^{\mathrm{to}}_{z}}(v)$
$\displaystyle=\\{|\pi_{s,v}[z,v]|:s\in V\text{ such that
}\pi_{s,v}\in\Pi\setminus\Pi_{D}\text{ and }\beta(\pi_{s,v})=z\\},$
$\displaystyle{\Psi^{\mathrm{from}}_{z}}(v)$
$\displaystyle=\\{|\pi_{v,t}[v,z]|:t\in V\text{ such that
}\pi_{v,t}\in\Pi\setminus\Pi_{D}\text{ and }\beta(\pi_{v,t})=z\\}.$

There are $O(|H|n)=\widetilde{O}(n^{2}/h)$ multisets
${\Psi^{\mathrm{to}}_{z}}(v),{\Psi^{\mathrm{from}}_{z}}(v)$ and their total
size is bounded by $2|\Pi|$, i.e., $O(n^{2})$. At the beginning of the phase,
these multisets can be initialized in $O(n^{2})$ time, which, again, is
negligible (amortized) to the cost (1). We store them in data structures
allowing polylogarithmic deletions and minimum maintenance, for example
balanced binary search trees.

Finally, we are ready to define the set $Y$ of pair $(s,t)$ for which we
maintain values $\delta^{h}_{G}(s,t)$ in the data structure $\mathcal{A}$.
After the initialization step of a phase completes, at all times $Y$ contains:

  * •

all pairs $(u,v)\in(D\times V)\cup(V\times D)$,

  * •

all pairs $(u,v)\in(C\times V)\cup(V\times C)$,

  * •

all pairs $(s,t)\in V\times V$ such that $\pi_{s,t}\in\Pi_{D}$.

Since $D=\emptyset$ and $\Pi_{D}=\emptyset$ at the beginning of the phase, a
phase‘s initialization only potentially empties $Y$ in $\mathcal{A}$ and
subsequently inserts all $O(n^{2}/\tau)$ pairs $(C\times V)\cup(V\times C)$
into $Y$. By Theorem 3.1, this incurs an additional amortized update cost of

$\widetilde{O}\left(\frac{h^{2}n^{2+\nu}}{\tau\Delta}\right).$

#### Performing updates.

While the phase proceeds, the sets $D$ and $\Pi_{D}$, and thus also $Y$, grow.
However, recall from Theorem 5.1 that $|D|\leq\Delta$ implies that at all
times we have:

$|\Pi_{D}|=O(\Delta\cdot h\tau n),$

which also yields the promised $O(n\Delta+\Delta h\tau
n+n^{2}/\tau)=O(n^{2}/\tau+\Delta h\tau n)$ bound on the size of the set $Y$.
Also, more specifically, at most $O(h\tau n)$ new paths may be inserted to
$\Pi_{D}$ per update, which is also why $Y$ may grow by at most $O(h\tau n)$
pairs per update in the worst-case. The changes to the set $Y$ are immediately
passed to the data structure $\mathcal{A}$.

When a new path $\pi_{s,t}$ is added to $\Pi_{D}$, and $\beta(\pi_{s,t})=z$,
the two multisets ${\Psi^{\mathrm{to}}_{z}}(t)$ and
${\Psi^{\mathrm{from}}_{z}}(s)$ have to be updated by issuing a single-element
deletion. Therefore, maintaining the multisets costs $\widetilde{O}(hn\tau)$
worst-case time per update, which is dominated by the update cost of the data
structure $\mathcal{A}$.

We are now ready to state the summarized amortized update cost of the data
structure:

$\begin{split}\widetilde{O}\left(\frac{n^{2}h}{\Delta}+\frac{h^{2}n(n^{\omega(1,\mu,1)-\mu}+n^{1+\mu})}{b}\cdot\left(1+\frac{n}{\tau\Delta}\right)+\frac{n^{2}b}{\Delta}+h^{2}n^{\omega(1,\nu,1)-\nu}+\frac{h^{2}n^{2}}{\tau}\right.\\\
\left.+h^{3}\tau
n\cdot(\Delta+n^{\nu})+\frac{h^{2}n^{2+\nu}}{\tau\Delta}\right).\end{split}$

#### Answering queries.

Suppose a query for distances from a source vertex $s\in V$ is issued. We
first temporarily add all pairs $(s,t)$, where $t\in V$, to the set $Y$ so
that this change is reflected in the data structure $\mathcal{A}$. Let $Y_{s}$
be the set $Y$ augmented this way. Recall that the augmentation of $Y$ takes
$\widetilde{O}(h^{2}n^{1+\nu})$ time, and the change can be reverted within
the same bound.

Next, we build an auxiliary graph $X=(V,F)$ with the following edges:

  * •

an edge $uv$ of weight $\delta_{G}^{h}(u,v)$ for all $(u,v)\in Y_{s}$,

  * •

an edge $zt$ of weight $\min({\Psi^{\mathrm{to}}_{z}}(t))$ for all $(z,t)\in
H\times V$,

  * •

an edge $sz$ of weight $\min({\Psi^{\mathrm{from}}_{z}}(s))$ for all $(s,z)\in
V\times H$.

Recall that the weights of edges of the former type are maintained in the data
structure $\mathcal{A}$. The graph $X$ has
$O(|H|n+|Y|)=\widetilde{O}(n^{2}/h+\Delta h\tau n+n^{2}/\tau)$ edges. The
query procedure is to simply run near-linear time Dijkstra‘s algorithm on the
graph $X$. The following lemma establishes correctness.

######  Lemma 6.2.

For all $t\in V$, $\delta_{G}(s,t)=\delta_{X}(s,t)$.

###### Proof.

First of all, note that for all $uv\in E(X)$, the weight of an edge $uv$ in
$X$ equals the weight of some $u\to v$ path in $G$. As a result,
$\delta_{G}(u,v)\leq w_{X}(uv)$, which establishes
$\delta_{G}(s,t)\leq\delta_{X}(s,t)$ easily.

Let us now prove that $\delta_{X}(s,t)\leq\delta_{G}(s,t)$. Consider any
shortest $s\to t$ path $P$ in $G$. First, split $P$ into maximal segments
$P_{1}\cdot\ldots\cdot P_{k}$ not passing through any of the vertices $C\cup
D$ as intermediate vertices. In other words, for each $P_{i}=u_{i}\to v_{i}$,
we have $V(P_{i})\cap(C\cup D)\subseteq\\{u_{i},v_{i}\\}$ and $u_{i}\in C\cup
D\cup\\{s\\}$. We will prove that
$\delta_{X}(u_{i},v_{i})\leq\delta_{G}(u_{i},v_{i})$. By summing through $i$,
$\delta_{X}(s,t)\leq\delta_{G}(s,t)$ will follow easily.

Consider some $P_{i}$. We have $|P_{i}|=\delta_{G}(u_{i},v_{i})$. If
$|P_{i}|\leq h$, then $\delta_{G}(u_{i},v_{i})=\delta_{G}^{h}(u_{i},v_{i})$
and by $u_{i}\in C\cup D\cup\\{s\\}$, $(u_{i},v_{i})\in Y_{s}$. As a result,
there is an edge $u_{i}v_{i}$ of weight $\delta_{G}(u_{i},v_{i})$ in $X$.

Suppose $|P_{i}|>h$. Split $P_{i}$ arbitrarily into subpaths
$Q_{1},\ldots,Q_{l}$ such that $\lfloor h/2\rfloor\leq|Q_{j}|\leq h$ for all
$j=1,\ldots,l$. Consider some $j$ and let $Q_{j}$ be an $x_{j}\to y_{j}$ path.
We will prove that
$\delta_{X}(x_{j},y_{j})\leq|Q_{j}|=\delta_{G}^{h}(x_{j},y_{j})$. It will
follow that

$\delta_{X}(u_{i},v_{i})\leq\sum_{j}\delta_{X}(x_{i},y_{j})\leq\sum_{j}\delta_{G}^{h}(x_{j},y_{j})=\sum_{j}\delta_{G}(x_{j},y_{j})=\delta_{G}(u_{i},v_{i}),$

as desired.

If $(x_{j},y_{j})\in Y_{s}$, then there is an edge $x_{j}y_{j}$ of weight
$\delta_{G}^{h}(x_{j},y_{j})=\delta_{G}(x_{j},y_{j})$ in $X$ which immediately
implies $\delta_{X}(x_{j},y_{j})\leq\delta_{G}^{h}(x_{j},y_{j})$. Otherwise,
we have $(x_{j},y_{j})\notin Y_{s}$. Then by the definition of $P_{i}$ and
$Y_{s}$, we obtain that $V(Q_{j})\cap(C\cup D)=\emptyset$. This means that
$Q_{j}\subseteq G-(C\cup D)\subseteq G_{0}-C$ and thus
$\delta_{G_{0}-C}^{h}(x_{j},y_{j})\leq\delta_{G}(x_{j},y_{j})$ as $Q_{j}$ is a
shortest path in $G$. Moreover, since $(x_{j},y_{j})\notin Y_{s}$ and
$\delta_{G_{0}-C}^{h}(x_{j},y_{j})<\infty$,
$\pi_{x_{j},y_{j}}\in\Pi\setminus\Pi_{D}$, i.e., $\pi_{x_{j},y_{j}}$ exists
and does not contain a vertex from $D$. As a result,
$\pi_{x_{j},y_{j}}\subseteq G$, i.e.,
$\delta_{G}(x_{j},y_{j})\leq|\pi_{x_{j},y_{j}}|$. But we also have
$|\pi_{x_{j},y_{j}}|\leq\delta_{G_{0}-C}^{h}(x_{j},y_{j})$ by Theorem 3.2, so
we obtain:

$\delta_{G}(x_{j},y_{j})\leq|\pi_{x_{j},y_{j}}|\leq\delta_{G_{0}-C}^{h}(x_{j},y_{j})\leq\delta_{G}(x_{j},y_{j}).$

All the inequalities above have to be in fact equalities. This proves that
$\pi_{x_{j},y_{j}}$ is a shortest $x_{j}\to y_{j}$ path in $G$. Finally,
recall that $|\pi_{x_{j},y_{j}}|=\delta_{G}(x_{j},y_{j})\geq\lfloor
h/2\rfloor$. Consequently, there exists a vertex
${z=\beta(\pi_{x_{j},y_{j}})\in H}$ on the path
$\pi_{x_{j},y_{j}}\in\Pi\setminus\Pi_{D}$. We conclude
$\delta_{G}(x_{j},y_{j})=|\pi_{x_{j},y_{j}}[x_{j},z]|+|\pi_{x_{j},y_{j}}[z,y_{j}]|$.
By the definition of the multisets ${\Psi^{\mathrm{from}}_{z}}(x_{j})$ and
${\Psi^{\mathrm{to}}_{z}}(y_{j})$,
$|\pi_{x_{j},y_{j}}[x_{j},z]|\in{\Psi^{\mathrm{from}}_{z}}(x_{j})$ and
$|\pi_{x_{j},y_{j}}[z,y_{j}]|\in{\Psi^{\mathrm{to}}_{z}}(y_{j})$.
Consequently, $w_{X}(x_{j},z)\leq|\pi_{x_{j},y_{j}}[x_{j},z]|$ and
$w_{X}(z,y_{j})\leq|\pi_{x_{j},y_{j}}[z,y_{j}]|$, and thus there is a path
$x_{j}\to y_{j}$ of weight
$w_{X}(x_{j},z)+w_{X}(z,y_{j})\leq\delta_{G}(x_{j},y_{j})$ in $X$. ∎

#### Setting the parameters.

Let us now try to set the parameters so that the maximum of the update and
query time is minimized. The only term incurred by the query procedure that is
not dominated by the terms of the previously obtained update bound is
$\widetilde{O}(n^{2}/h)$. Moreover, it can be easily verified that it is best
to set $\mu:=\rho$, where $\rho\approx 0.529$ is the unique value such that
$\omega(1,\rho,1)=1+\rho$.

This way, we obtain the following combined updated/query bound:

$O\left(\frac{n^{2}h}{\Delta}+\frac{h^{2}n^{2+\rho}}{b}\cdot\left(1+\frac{n}{\tau\Delta}\right)+\frac{n^{2}b}{\Delta}+h^{2}n^{\omega(1,\nu,1)-\nu}+\frac{h^{2}n^{2}}{\tau}+h^{3}\tau
n\cdot(\Delta+n^{\nu})+\frac{h^{2}n^{2+\nu}}{\tau\Delta}+\frac{n^{2}}{h}\right).$

By setting the parameters $h=n^{0.031}$, $\Delta=n^{0.78}$, $t=n^{0.093}$,
$b=n^{0.749}$, $\nu=\rho$ obtained using the online balancing tool [Bra], we
get an $O(n^{1.969})$ worst-case update and query bounds.

It is also interesting to see what is the exact dependence on $\omega$ we can
get. One can prove that for large enough $\Delta$ it is optimal to set
$\nu:=\rho$ so that $n^{\nu}<\Delta$, and also $b:=\Delta/h$, and
$\tau:=h^{3}$. Then, we get the bound

$\widetilde{O}\left(\frac{hn^{2+\rho}}{\Delta}+\frac{n^{3+\rho}}{\Delta^{2}}+\Delta
h^{6}n+\frac{n^{2}}{h}\right)$

By balancing the two last terms, we get $\Delta=n/h^{7}$. Then the first term
($h^{8}n^{1+\rho}$) becomes dominated by the second ($h^{14}n^{1+\rho}$). By
further balancing the latter with $n^{2}/h$ we get $h=n^{(1-\rho)/15}$. The
final bound becomes (by $\rho\leq\frac{1}{4-\omega}$):

$\widetilde{O}\left(n^{2-\frac{1-\rho}{15}}\right)\subseteq\widetilde{O}\left(n^{2-\frac{3-\omega}{60-15\omega}}\right).$

This bound is subquadratic assuming any truly subcubic matrix multiplication
algorithm is used and equals $\widetilde{O}(n^{2-1/30})$ if $\omega=2$ (then,
$\rho=0.5$).

#### Deamortization.

The heavy super-quadratic preprocessing invoking Theorem 5.1, initializing the
set $Y$, and constructing the hitting set (which are the only source of
amortization here) happens in a coordinated way, once every $\Delta$ updates.
Consequently, the data structure can be deamortized using a standard technique
of running two copies of the data structure in parallel and spreading out the
reset computation over several updates. While one copy of the algorithm is
performing the reset, the other copy is used to answer the queries. For
details, we refer to e.g., [ACK17, BNS19, Tho05].

We have thus proved:

######  Theorem 6.3.

Let $G=(V,E)$ be unweighted digraph. There exists a deterministic data
structure supporting fully dynamic single-edge updates to $G$ and computing
exact distances from an arbitrary query source $s\in V$ to all other vertices
in $G$ in $O(n^{1.969})$ worst-case time.

If $\omega=2$, the bound becomes $\widetilde{O}(n^{2-1/30})$.

#### SSSP tree reporting.

We now explain how the data structure of Theorem 6.3 can be extended to also
output a single-source shortest paths tree in subquadratic time, albeit at the
cost of an additional polynomial overhead.

We apply Lemma 4.1 with $h:=n$ on top of the obtained data structure
maintaining single-source distances. In terms of Lemma 4.1, we have
$Q_{\mathrm{source}}(n,n)=O(n^{1.969})$ by Theorem 6.3, and we want to support
queries of the form $S=\\{s\\}$, $Y=\\{s\\}\times V$, for a query source $s\in
V$. As a result, for any $b\in[1,n]$, there exists a data structure supporting
single-edge updates to $G$ in $O(n^{2.969}/b)$ time and reporting predecessors
of shortest $n$-bounded paths from any source vertex $s$ in
$O(n^{2.969}/b+nb)$ time. Clearly, the predecessors yield an SSSP tree from
$s$. By setting $b=0.985$, we obtain a deterministic tree-reporting SSSP data
structure with $O(n^{1.985})$ worst-case update and query time.

##  7 Fully dynamic path-reporting transitive closure and approximate APSP

In this section, we consider the fully dynamic transitive closure and
$(1+\epsilon)$-approximate APSP problems (in unweighted digraphs) under
_vertex updates_ to $G$. Under the assumption that $\omega\geq 2.12$, we
describe a deterministic data structure with $O(n^{\omega-\gamma})$ worst-case
update time, for some $\gamma>0$ dependent on $\omega$, that explicitly
maintains the transitive closure of a matrix of distance estimates. In the
case of approximate distances, the data structure also supports reporting any
$s\to t$ path of length at most $(1+\epsilon)\cdot\delta_{G}(s,t)$ in optimal
$O(\delta_{G}(s,t))$ time. For reachability, an even stronger reporting
interface is achieved: reachability trees in $G$ from all possible sources
$s\in V$ are explicitly stored after each update. Clearly, this also allows
for reporting paths in $G$ between arbitrary pairs of vertices in optimal
time.

The overall approach is similar as in the fully dynamic SSSP data structure
from Section 6. Namely, we will operate in phases of length $\Delta$ and use
analogous global data structures shared among the phases. Every phase starts
by computing a pair $(C,\Pi)$ as given by Theorem 5.1.

#### The data structure $\mathcal{T}$.

Recall that the global data structures $\mathcal{A}$ and $\mathcal{T}$ in
Section 6, both implemented as data structures of Theorem 3.1 (with possibly
some extensions of Section 4), rely only on _single-edge_ updates (so that
they reflect $G$ at all times) and vertex switch-offs. Here, we will use the
data structure $\mathcal{T}$ from Section 6, required by Theorem 5.1, in a
slightly different way.

Instead of passing the updates to $G$ to $\mathcal{T}$ immediately, we will
only do so at the end of a phase, that is, in a batch of at most $\Delta$
updates. This is done with the vertex batch-update operation of Theorem 3.1.
To see that this is sufficient, recall that the only purpose of $\mathcal{T}$
was to construct the set $C$ and a collection of paths $\Pi$. For this task,
$\mathcal{T}$ only required supporting switching vertices off interleaved with
$h$-bounded-shortest paths queries from a single source. We thus require
$\mathcal{T}$ to reflect the current graph $G$ only once per $\Delta$ updates.
Since a batch update is performed on $\mathcal{T}$ only once per
$\Delta=n^{\delta}$ updates, this incurs an
$\widetilde{O}\left(h^{2}n^{\omega(1,\delta,1)+1}/(\Delta b)\right)$ worst-
case cost per update. As a result, the total per-update cost of initializing a
phase is now:

$O\left(\frac{h^{2}n^{\omega(1,\delta,1)+1}}{\Delta
b}+\frac{h^{2}n^{2+\rho}}{b}\cdot\left(1+\frac{n}{\Delta\tau}\right)+\frac{n^{2}b}{\Delta}\right).$

#### The set $Y$.

We also redefine the set $Y\subseteq V\times V$, for a fixed phase, to only
contain the pairs $(s,t)$ such that $\pi_{s,t}\in\Pi_{D}$. As a result, by
Theorem 5.1, we have $|Y|=O(\Delta h\tau n)$ at all times.

#### The predecessor reporting data structure $\mathcal{B}$.

Let $\mathcal{S}$ and $\mathcal{P}$ be two data structures of Theorem 3.1, for
the parameter $\mu$ to be set later, responsible for maintaining $h$-bounded
distances in $G$. While the phase proceeds, these data structures will not
accept edge/vertex updates. Only at the end of the phase they are updated with
a batch of $\Delta$ vertex updates from the current phase.

The data structures $\mathcal{S}$ and $\mathcal{P}$ have different purposes.
$\mathcal{S}$ is initialized so that it can maintain $\delta_{G}^{h}(s,t)$
_explicitly_ for all $n^{2}$ pairs $s,t\in V$ (i.e., $Y:=V\times V$ in terms
of Theorem 3.1), whereas $\mathcal{P}$ is capable of answering arbitrary
$\delta_{G}^{h}(s,t)$ queries in $\widetilde{O}(h^{2}n^{\mu})$ time. This way,
$\mathcal{S}$ allows very fast queries at the cost of
$\widetilde{O}(h^{2}n^{2})$ worst-case update time, whereas $\mathcal{P}$
answers queries slower, but can handle updates more efficiently, in
$\widetilde{O}(h^{2}(n^{\omega(1,\mu,1)-\mu}+n^{\mu}))$ worst-case time.

We use data structures $\mathcal{S}$ and $\mathcal{P}$ to construct a
predecessor reporting data structure $\mathcal{B}$ of Lemma 4.2 storing the
graph $G-D$, for $b:=\beta$, where $\beta\in[1,n]$ is a parameter to be set
later. Specifically, we first apply Lemma 4.2, and then also Lemma 4.4 on top
of that to enable cheap insertions to $D$ (we model $G-D$ as the induced
subgraph $G[W]$ with $W:=V\setminus D$). The general purpose of $\mathcal{B}$
is to reconstruct $h$-bounded shortest paths in $G-D$. Note that in terms of
the quantities used in Lemma 4.2, we have $Q_{\mathrm{source}}(n,h)=O(n)$,
$U_{\mathrm{source}}(n,h)=\widetilde{O}(h^{2}n^{2})$,
$Q_{\mathrm{pair}}(n,h)=\widetilde{O}(h^{2}n^{\mu})$ and
$U_{\mathrm{pair}}(n,h)=\widetilde{O}(h^{2}(n^{\omega(1,\mu,1)-\mu}+n^{1+\mu}))$.
Therefore, by issuing a query with $S=V$ (which trivially guarantees
$Y\subseteq S\times V$), $\mathcal{B}$ can compute a predecessor vertex
$q_{s,t}$ on some shortest $h$-bounded $s\to t$ paths for all $(s,t)\in Y$
such that $\delta_{G-D}^{h}(s,t)<\infty$ in time

$\widetilde{O}(n^{2}+(h^{2}n^{\mu}+\beta)\cdot|Y|).$

Adding new vertices to $D$ corresponds to removal of a vertex from the subset
$W$ issued to the data structure $\mathcal{B}$, and thus costs

$\widetilde{O}(h^{2}n^{2}+(n/\beta)\cdot
h^{2}(n^{\omega(1,\mu,1)-\mu}+n^{1+\mu}))$

time. Similarly, the batch-vertex update to $\mathcal{B}$ at the end of a
phase costs
$\widetilde{O}\left(\frac{h^{2}n^{\omega(1,\delta,1)+1}}{\beta\Delta}\right)$
amortized time per update.

#### Computing all-pairs distance estimates upon update.

After an update, we compute the respective predecessors $q_{s,t}$ for all
$(s,t)\in Y$ using $\mathcal{B}$. We now introduce a certain collection of
paths $\Pi^{\prime}=(\pi^{\prime})_{s,t\in V}$ derived from $\Pi$, $D$, and
the computed predecessors. For each $s,t\in V$, $\pi^{\prime}_{s,t}$ is either
a path in $G-D$, or is left undefined (set to $\perp$). Specifically, we set:

$\pi^{\prime}_{s,t}=\begin{cases}\pi_{s,t}&\text{ if
}\pi_{s,t}\in\Pi\setminus\Pi_{D},\\\ \pi^{\prime}_{s,q_{s,t}}\cdot
q_{s,t}t&\text{ if }\pi_{s,t}\in\Pi_{D}\text{ and
}\delta_{G-D}^{h}(s,t)\neq\infty\text{ and
}\pi^{\prime}_{s,q_{s,t}}\neq\perp,\\\ \perp&\text{ otherwise. }\end{cases}$

The definition is valid since $\pi_{s,t}\in\Pi_{D}$ and
$\delta_{G-D}^{h}(s,t)\neq\infty$ implies that $(s,t)\in Y$ and thus
$\delta^{h}_{G-D}(s,q_{s,t})=\delta^{h}_{G-D}(s,t)-1$. Note that the
collection $\Pi^{\prime}$ can be explicitly constructed from the definition in
$O(n^{2}h)$ time once the predecessors $q_{s,t}$ are computed. For simplicity,
define $|\perp|=\infty$.

######  Lemma 7.1.

For any $s,t\in V$ such that no shortest $h$-bounded $s\to t$ path in $G$ goes
through $C\cup D$, we have $|\pi_{s,t}^{\prime}|=\delta_{G}^{h}(s,t)$.

###### Proof.

Recall that we denote by $G_{0}$ the graph at the beginning of the current
phase.

First consider the case $\delta_{G}^{h}(s,t)=\infty$. Then either
$\pi_{s,t}\notin\Pi$ which implies $\pi^{\prime}_{s,t}=\perp$, or
$\delta_{G_{0}-C}^{h}(s,t)<\infty$ and thus $\pi_{s,t}\in\Pi_{D}$ by
$\delta_{G-D}^{h}(s,t)=\infty$. However, in such a case we set
$\pi^{\prime}_{s,t}:=\perp$ as well.

Now let us assume that $\delta_{G}^{h}(s,t)$ is finite. We prove the claim by
induction on $\delta_{G}^{h}(s,t)$. Since no shortest $s\to t$ path goes
through $C\cup D$, $\delta_{G}^{h}(s,t)=\delta_{G-D}^{h}(s,t)=\delta_{G-(C\cup
D)}^{h}(s,t)\geq\delta_{G_{0}-C}^{h}(s,t)$. Hence, we obtain that
$\pi_{s,t}\in\Pi$ exists and has length at most
$\delta_{G_{0}-C}^{h}(s,t)\leq\delta_{G}^{h}(s,t)$. If
$\pi_{s,t}\in\Pi\setminus\Pi_{D}$, then $\pi^{\prime}_{s,t}=\pi_{s,t}\subseteq
G-D\subseteq G$, so indeed we have $|\pi^{\prime}_{s,t}|=\delta_{G}^{h}(s,t)$.
Otherwise, $\pi_{s,t}\in\Pi_{D}$. By $\delta_{G-D}^{h}(s,t)<\infty$, $q_{s,t}$
exists and $\delta_{G}^{h}(s,q_{s,t})=\delta_{G}^{h}(s,t)-1$. Since no
shortest $h$-bounded $s\to t$ path in $G$ goes through $C\cup D$, neither does
any shortest $h$-bounded $s\to q_{s,t}$ path in $G$. By the inductive
assumption we have that
$|\pi^{\prime}_{s,q_{s,t}}|=\delta_{G}^{h}(s,q_{s,t})$. As a result, the path
$\pi^{\prime}_{s,t}=\pi^{\prime}_{s,q_{s,t}}\cdot q_{s,t}t$ indeed has length
$\delta_{G}^{h}(s,t)$. ∎

With the collection $\Pi^{\prime}$ in hand, in $O(n^{2}h)$ time we can
deterministically compute an $\widetilde{O}(n/h)$-sized hitting set
$H\subseteq V$ of all $\pi^{\prime}_{s,t}$ satisfying $|\pi_{s,t}^{\prime}|=h$
using Lemma 6.1.

######  Lemma 7.2.

Let $s\in V\setminus(C\cup D\cup H)$ and $t\in V$ be such that
$\delta_{G}(s,t)<\infty$. Some shortest $s\to t$ path in $G$ either:

  1. (a)

is equal to $\pi^{\prime}_{s,t}$, or

  2. (b)

has a prefix $\pi^{\prime}_{s,q}\cdot qr$ for some $r\in C\cup D\cup H$, where
$q=r$ or $qr\in E(G)$ and $|\pi^{\prime}_{s,q}\cdot qr|\geq 1$.

###### Proof.

First suppose that $\delta_{G}(s,t)\leq h$, i.e.,
$\delta_{G}^{h}(s,t)\neq\infty$.

If no shortest $s\to t$ path in $G$ goes through $C\cup D$, then by Lemma 7.1,
$\pi^{\prime}_{s,t}$ is a shortest path, i.e., item (a) is satisfied.

Let us thus assume that some shortest $s\to t$ path goes through $C\cup D$.
There exists an $r\in C\cup D$ such that
$\delta_{G}(s,t)=\delta_{G}(s,r)+\delta_{G}(r,t)$; if there are many such $r$,
pick one with minimal $\delta_{G}(s,r)$. By $s\notin C\cup D$,
$\delta_{G}(s,r)\geq 1$. If $\delta_{G}(s,r)=1$, then some shortest $s\to t$
path starts with the edge $sr$, i.e., item (b) is satisfied with $q=s$.
Otherwise, if $\delta_{G}(s,r)\geq 2$, then by the choice of $r$, any $s\to r$
path has no vertices in $C\cup D$ except $r$. As a result, if $q\in
V\setminus(C\cup D)$ is the penultimate vertex on one such $s\to r$ path, we
obtain that no $s\to q$ path in $G$ contains a vertex from $C\cup D$. By
applying Lemma 7.1 to $(s,q)$, we obtain that $\pi^{\prime}_{s,q}$ is a
shortest $s\to q$ path in $G$. Therefore, we conclude that some shortest $s\to
t$ path in $G$ has a prefix $\pi^{\prime}_{s,q}\cdot qr$, where $r\in C\cup
D$, as desired.

Now consider the case $\delta_{G}(s,t)>h$. Let $x\in V$ be such that
$\delta_{G}(s,t)=\delta_{G}(s,x)+\delta_{G}(x,t)$ and $\delta_{G}(s,x)=h$. We
have already proved the lemma for the pair $(s,x)$. If there is a shortest
$s\to x$ path satisfying (b), there is also clearly a shortest $s\to t$ path
satisfying (b). It may also happen that $\pi^{\prime}_{s,x}$ is a shortest
$s\to x$ path in $G$. But then, there exists a vertex $u\in H$, $u\neq s$, on
$\pi^{\prime}_{s,x}$. By applying the lemma once again to the pair $(s,u)$
satisfying $\delta_{G}(s,u)\leq h$, we obtain that either (b) holds for
$(s,u)$ and thus also for $(s,t)$, or (a) holds for $(s,u)$, which together
with $s\notin H$ implies that $|\pi^{\prime}_{s,u}|\geq 1$ and thus (b) holds
for $(s,t)$ with $q=r=u\in H$. ∎

By proceeding symmetrically, one can prove a ’’suffix‘‘ version of Lemma 7.2:

######  Lemma 7.3.

Let $s\in V$ and $t\in V\setminus(C\cup D\cup H)$ be such that
$\delta_{G}(s,t)<\infty$. Some shortest $s\to t$ path in $G$ either:

  1. (a)

is equal to $\pi^{\prime}_{s,t}$, or

  2. (b)

has a suffix $rq\cdot\pi^{\prime}_{q,t}$ for some $r\in C\cup D\cup H$, where
$q=r$ or $rq\in E(G)$ and $|rq\cdot\pi^{\prime}_{q,t}|\geq 1$.

Let us now recall the definition of the min-plus product $\star$. If $A$ is an
$a\times b$ matrix and $B$ is an $b\times c$ matrix, then $A\star B$ is a
$a\times c$ matrix such that $(A\star
B)_{i,j}=\min_{k=1}^{b}\\{A_{i,k}+B_{k,j}\\}$.

Define a matrix $A\in\\{0,\ldots,h,\infty\\}^{n\times n}$ as follows:

$A_{u,v}=\begin{cases}0&\text{ if }u=v\\\ 1&\text{ if }u\neq v\text{ and
}uv\in E(G),\\\ |\pi^{\prime}_{u,v}|&\text{ if }u\neq v\text{ and }uv\notin
E(G)\text{ and }\pi^{\prime}_{u,v}\neq\perp,\\\ \infty&\text{ otherwise.
}\end{cases}$

Let $A[S,T]$ denote the submatrix of $A$ with rows $S$ and columns $T$, where
$S,T\subseteq V$. Let $X:=C\cup D\cup H$. Define the matrix $A^{*}$ as:

$A^{*}=\min\left(A,(A\star A[V,X])\star\left(A[X,V]\star A\star
A[V,X]\right)^{n}\star(A[X,V]\star A)\right),$ (2)

where the matrix powering is using the min-plus matrix product $\star$, and
the minimum is element-wise.

######  Lemma 7.4.

For any $s,t\in V$, $A^{*}_{s,t}=\delta_{G}(s,t)$.

###### Proof.

Note that $A_{u,v}\geq\delta_{G}(u,v)$ for all $u,v\in V$. Moreover, the min-
plus product of any two matrices with rows and columns in $V$ satisfying this
condition also satisfies this condition. This proves that
$A^{*}_{u,v}\geq\delta_{G}(u,v)$.

Let us now prove that $A^{*}_{s,t}\leq\delta_{G}(s,t)$. We first consider the
case $s,t\in X$. We proceed by induction on $d:=\delta_{G}(s,t)$ and prove
that if $B:=A[X,V]\star A\star A[V,X]$, then
$(B^{d})_{s,t}\leq\delta_{G}(s,t)$ (where the powering is using the min-plus
product $\star$). Let us first note that since $A$ has zeros on the diagonal,
$(B^{i+1})_{s,t}\leq(B^{i})_{s,t}$ for any $i\geq 0$ and $B_{s,t}\leq
A_{s,t}$.

The identity matrix $I$ for the min-plus product has zeros on the diagonal and
$\infty$ everywhere else. If $d=0$, then $s=t$ and $B^{0}=I$, so indeed
$(B^{d})_{s,t}=I_{s,s}=0$.

Suppose $d\geq 1$. Let $u\in V$ be any vertex such that $su\in E(G)$ and
$\delta_{G}(u,t)=d-1$. We have $A_{s,u}=1$ and thus also $B_{s,u}\leq 1$. If
$u\in X$, then both $B_{s,u}\leq 1$ and $(B^{d-1})_{u,t}\leq d-1$ hold by the
inductive assumption, and thus indeed $(B^{d})_{s,t}\leq d$.

Now assume $u\notin X$. By Lemma 7.2 applied to $(u,t)$, we have two cases. If
case (a) applies, $\pi^{\prime}_{u,t}\neq\perp$, so $B_{u,t}\leq
A_{u,t}\leq|\pi^{\prime}_{u,t}|=\delta_{G}(u,t)\leq d-1$ and thus again we
obtain $(B^{d-1})_{u,t}\leq d-1$ and consequently $(B^{d})_{s,t}\leq d$. If
case (b) applies, then for some $q,r$, where $q\in V$, $r\in X$ and
$\delta_{G}(r,t)\leq d-1$, we have
$\delta_{G}(s,r)=|su\cdot\pi^{\prime}_{u,q}\cdot qr|$, where possibly $q=r$ or
$s=q$. But this implies
$B_{s,r}\leq(A[X,V])_{s,u}+A_{u,q}+(A[V,X])_{q,r})\leq\delta_{G}(s,r)$. By the
inductive assumption, $(B^{d-1})_{r,t}\leq\delta_{G}(r,t)$, so
$(B^{d})_{s,t}\leq\delta_{G}(s,r)+\delta_{G}(r,t)=\delta_{G}(s,t)$ as well.

We have therefore proved that for any $s,t\in X$, $\delta_{G}(s,t)<\infty$
implies that $(B^{n})_{s,t}\leq\delta_{G}(s,t)$. This in turn implies
$A^{*}_{s,t}\leq\delta_{G}(s,t)$ for such pairs $(s,t)$.

If $s\notin X$ and $t\in X$, then by Lemma 7.2, either (a)
$\pi^{\prime}_{s,t}$ is a shortest $s\to t$ path, which implies
$A_{s,t}\leq\delta_{G}(s,t)$, or (b) for some $q\in V$ and $r\in X$ with
$\delta_{G}(r,t)<\delta_{G}(s,t)$, there is a shortest $s\to t$ path starting
with $\pi^{\prime}_{s,q}\cdot qr$, which implies
$\delta_{G}(s,t)=\delta_{G}(s,r)+\delta_{G}(r,t)$ and
$A_{s,q}+A_{q,r}\leq\delta_{G}(s,r)$. In both cases we conclude $\left((A\star
A[V,X])\star B^{n}\right)_{s,t}\leq\delta_{G}(s,t)$. By Lemma 7.3 we can
symmetrically prove that if $s\in X$ and $t\notin X$, then
$(B^{n}\star(A[X,V]\star A))_{s,t}\leq\delta_{G}(s,t)$.

Finally, if $s\notin X$ and $t\notin Y$, then we analogously argue that either
$A_{s,t}\leq\delta_{G}(s,t)$ or for some $r\in X$ we have
$\delta_{G}(s,t)=\delta_{G}(s,r)+\delta_{G}(r,t)$, $(A\star
A[V,X])_{s,r}\leq\delta_{G}(s,r)$ and $(B^{n}\star(A[X,V]\star
A))_{r,t}\leq\delta_{G}(r,t)$, which implies that $\left((A\star A[V,X])\star
B^{n}\star(A[X,V]\star A)\right)_{s,t}\leq\delta_{G}(s,t)$. Therefore, we
conclude that for the general case ${s,t\in V}$, we have either
$A_{s,t}\leq\delta_{G}(s,t)$ or $\left((A\star A[V,X])\star
B^{n}\star(A[X,V]\star A)\right)_{s,t}\leq\delta_{G}(s,t)$, as desired. ∎

Lemma 7.4 yields a way of computing exact all-pairs distances in $G$ based on
the collection $\Pi^{\prime}$ provided that an efficient algorithm computing
rectangular min-plus products is available. However, the known min-plus matrix
product algorithms are not efficient enough to give an improved fully dynamic
exact APSP algorithm this way. Nevertheless, we will argue that Lemma 7.4 is
enough for deterministically computing the matrix of
$(1+\epsilon)$-approximate distances in $G$ polynomially faster than in
$O(n^{\omega})$ time, for any $\omega>2$. To this end, we will need the
following $(1+\epsilon)$-approximate min-plus matrix product
$\star_{\epsilon}$ of Zwick [Zwi02, Section 8]:

######  Theorem 7.5.

[Zwi02] Let $A,B$ be two $n\times n$ matrices with elements from
$\\{0,\infty\\}\cup[1,N]$. Let $\epsilon>0$. Then, in
$\widetilde{O}(n^{\omega}\log(N)/\epsilon)$ deterministic time one can compute
a matrix $A\star_{\epsilon}B$ such that for all $i,j\in[n]$:

$(A\star B)_{i,j}\leq(A\star_{\epsilon}B)_{i,j}\leq(1+\epsilon)\cdot(A\star
B)_{i,j}.$

######  Remark 7.6.

[Zwi02] Theorem 7.5 can be easily generalized to the rectangular case, i.e.,
if $A$ and $B$ are $n^{a}\times n^{b}$ and $n^{b}\times n^{c}$ matrices, then
the approximate min-plus product can be computed in
$\widetilde{O}(n^{\omega(a,b,c)}\log(N)/\epsilon)$ time. Moreover, the
approximate min-plus product can be extended to deterministically produce
witnesses within a time bound that is a $\operatorname{polylog}(n)$ factor
away.

Let $\epsilon^{\prime}>0$. Suppose we evaluate the formula (2) by replacing
the min-plus product $\star$ with $(1+\epsilon^{\prime})$-approximate min-plus
product $\star_{\epsilon^{\prime}}$ of Theorem 7.5 (and Remark 7.6) and using
the folklore repeated-squaring algorithm for matrix powering. Then, only
$O(\log{n})$ matrix products will be performed and each of the products
involved will take
$\widetilde{O}(n^{\omega(1,\alpha,1)}\log(N)/\epsilon^{\prime})$ time, where
$\alpha\in[0,1]$ is such that $|C\cup D\cup H|\leq n^{\alpha}$, and $N$ is a
bound on the largest finite number arising in this computation. Indeed, in all
the matrix products involved, one of the matrix dimensions dimensions is
bounded by $n^{\alpha}$ (we will later set $\tau,h,\Delta$ so that
$\alpha<1$). Moreover, since there are $O(\log{n})$ matrix products, the
approximation error at the end is bounded by
$(1+\epsilon^{\prime})^{O(\log{n})}$. This also implies the bound $N\leq
n\cdot(1+\epsilon^{\prime})^{O(\log{n})}$. By using a sufficiently small
$\epsilon^{\prime}=\Theta(\epsilon/\log{n})$, we can guarantee that the entire
computation is $(1+\epsilon)$-approximate and $N=\widetilde{O}(n)$. We
conclude that the matrix of $(1+\epsilon)$-approximate distance estimates can
be computed based on $\Pi^{\prime}$ in
$\widetilde{O}(n^{\omega(1,\alpha,1)}/\epsilon)$ time.

It is worth noting that if we wanted to compute the transitive closure of $G$
(which can be seen as any finite approximation of APSP) instead, we could use
the standard boolean matrix product $\cdot$ instead of the approximate min-
plus product $\star_{\epsilon^{\prime}}$ here.

#### Approximate shortest path reporting.

We now turn to explaining how the data structure can be extended to enable
efficient reporting of approximately shortest $s,t$-paths while computing the
matrix $A^{*}$ approximately. Recall that, by Remark 7.6, the approximate min-
plus product of Theorem 7.5 can also produce witnesses, i.e., such indices
$w_{i,j}$ that

$A_{i,w_{i,j}}+B_{w_{i,j},j}\leq(1+\epsilon^{\prime})\cdot(A\star B)_{i,j}.$

Suppose we record the witnesses for all the $\ell=O(\log{n})$ approximate
products involved when computing $A^{*}$ approximately using Equation 2. More
concretely, let the subsequent matrices obtained be $L_{1},\ldots,L_{\ell}$,
where $\min(A,L_{\ell})$ is a $(1+\epsilon)$-approximation of $A^{*}$. By
Lemma 7.4, we have

$\min(A_{s,t},(L_{\ell})_{s,t})\leq(1+\epsilon)\delta_{G}(s,t).$

Put $L_{0}:=A$ and a define paths $P_{0,s,t}$ corresponding to the entries of
$A$:

$P_{0,s,t}=\begin{cases}\emptyset&\text{if }s=t,\\\ st&\text{if }st\in
E(G),\\\ \pi^{\prime}_{st}&\text{if }s\neq t,st\notin E(G),\text{and
}A_{s,t}\neq\infty,\\\ \perp&\text{otherwise.}\end{cases}$

Put $|\perp|=\infty$. When computing the matrix $L_{k}$ as a product of a
submatrix of $L_{i}$ and a submatrix of $L_{j}$ (along with witnesses
$w_{\cdot,\cdot}$), where $i,j<k$, for all $s,t$ such that $(L_{k})_{s,t}$ is
defined, we define the path $P_{k,s,t}$ as follows:

$P_{k,s,t}=\begin{cases}P_{i,s,w_{s,t}}\cdot P_{j,w_{s,t},t}&\text{if
}w_{s,t}\notin\\{s,t\\},\\\ P_{i,s,t}&\text{if }w_{s,t}=t,\\\
P_{j,s,t}&\text{if }w_{s,t}=s.\end{cases}$

In the implementation, we do not explicitly copy or concatenate the paths
define above, but rather store the pointers to the previously represented
paths. This costs only $\widetilde{O}(n^{2})$ additional time.

It is easy to prove inductively that for all $k,s,t$ such that
$(L_{k})_{s,t}\neq\infty$, $P_{k,s,t}$ is an $s\to t$ path in $G$ of length at
most $(L_{k})_{s,t}$. Consequently, for all $s,t$ such that
$\delta_{G}(s,t)\neq\infty$, we have
$\min(|P_{0,s,t}|,|P_{\ell,s,t}|)\leq(1+\epsilon)\delta_{G}(s,t)$. As a
result, using the stored pointers we can report an
$(1+\epsilon)$-approximately shortest $s\to t$ path for any $(s,t)\in V$ in
optimal $O(\delta_{G}(s,t))$ time.

#### Single-source reachability trees from all sources.

While in the case of approximately shortest paths and a fixed source $s\in V$,
we can report an $s\to t$ path of length $(1+\epsilon)\delta_{G}(s,t)$ for any
$t\in V$ efficiently, it is not clear how to organize such paths into a tree
of approximately shortest paths rooted at $s$. However, as we show next, this
is possible in the case of transitive closure. Specifically, we now show that
one can compute _reachability_ trees from all possible sources $s\in V$ in $G$
using the approximate matrix $A^{*}$, if any constant $\epsilon\in(0,1)$ is
used.

We first compute in $O(n^{2})$ time the strongly connected components (SCCs)
of $G$, using any classical linear-time algorithm, e.g., that of [Tar72].

######  Lemma 7.7.

A subgraph $G_{\mathrm{SCC}}\subseteq G$ with $O(n)$ edges such that
$G_{\mathrm{SCC}}$ preserves the strongly connected components of $G$ can be
computed in $O(n^{2})$ time.

###### Proof.

For any strongly connected component $S\subseteq V$ of $G$, include in
$G_{\mathrm{SCC}}$ a pair of trees in $G[S]$: a reachability tree from and to
any $s\in S$ in the subgraph $G[S]$. These trees can be computed via graph
search in time linear in the number of edges of $G[S]$. Since the subgraphs
$G[S]$ are clearly disjoint for distinct $S$, computing $G_{\mathrm{SCC}}$
takes $O(n^{2})$ time. ∎

Now let us define a matrix $A^{\prime}$ such that $A^{\prime}_{s,t}=0$ if the
vertices $s$ and $t$ are _not_ strongly connected in $G$ and either
$A_{s,t}\neq\infty$ or $(A[V,X]\star_{\epsilon}A[X,V])_{s,t}\neq\infty$ holds,
and $A^{\prime}_{s,t}=\infty$ otherwise.

Let us compute the matrix product
$F_{V}:=A^{*}[V,X]\star_{\epsilon}A^{\prime}[X,V]$ along with the matrix
$W_{V}$ of witnesses, that is, for every $u,v$ such that
$(F_{V})_{u,v}\neq\infty$, $(W_{V})_{u,v}$ is equal to some $z\in X$ such that
$A^{*}_{u,z}\neq\infty$ and $A^{\prime}_{z,v}\neq\infty$. Similarly, we
compute the matrix $W_{X}$ of witnesses of the product
$F_{X}:=A^{*}[V,V]\star_{\epsilon}A^{\prime}[V,X]$. Finally, let us compute
the matrix $L$ of the witnesses of the product $A[V,X]\star_{\epsilon}A[X,V]$.
Again, in all the additional matrix products here, one of the dimension is
bounded by $|X|\leq n^{\alpha}$, so computing the required information takes
$\widetilde{O}(n^{\omega(1,\alpha,1)}/\epsilon)$ time.

######  Lemma 7.8.

For any $a,b\in V$, define $\pi^{*}_{a,b}$ to be either the edge $ab$ if
$ab\in E(G)$ or the path $\pi^{\prime}_{a,b}$ if $\pi^{\prime}_{a,b}\neq\perp$
(if both exist, pick an arbitrary one). If none of these exist, set
$\pi^{*}_{a,b}:=\perp$.

Let $s\in V$. Let $G_{s}\subseteq G$ be a subgraph containing:

  * •

the path $\pi^{*}_{s,t}$ for all $t\in V$ such that $\pi^{*}_{s,t}\neq\perp$,

  * •

for each $t\in V$ such that $(F_{V})_{s,t}=1$, the paths $\pi^{*}_{x,w}$ and
$\pi^{*}_{w,t}$, where where $x=(W_{V})_{s,t}$ and $w=L_{x,t}$.

  * •

for each $x\in X$ such that $(F_{X})_{s,x}=1$, the path $\pi^{*}_{w,x}$, where
$w=W_{s,x}$.

  * •

the subgraph $G_{\mathrm{SCC}}$.

Then a vertex is reachable from $s$ in $G$ if and only if it is reachable from
$s$ in $G_{s}$.

###### Proof.

The ’’$\impliedby$‘‘ direction is trivial since $G_{s}$ is a subgraph of $G$.

We will prove the ’’$\implies$‘‘ part by showing that each SCC $S$ of $G$ that
$s$ can reach is also reachable from $s$ in $G_{s}$. Since the SCCs of $G$ are
preserved in $G$ by the inclusion of $G_{\mathrm{SCC}}$, this is clearly true
for the SCC $S_{s}$ containing the vertex $s$. Since the graph obtained from
$G_{s}$ by contracting the SCCs is a DAG, it is enough to argue that every
other SCC $S^{\prime}\neq S_{s}$ has in $G_{s}$ an edge coming from another
SCC $S^{\prime\prime}\neq S^{\prime}$ reachable from $s$.

Let $S\neq S_{s}$ be an SCC of $G$ such that $d=\min_{v\in
S}\delta_{G}(s,v)\geq 1$. Let $t\in S$ be such that $\delta_{G}(s,t)=d$. Since
every vertex $z$ strongly connected with $t$ has
$\delta_{G}(s,z)\geq\delta_{G}(s,t)=d$, every vertex $y\neq t$ satisfying
$\delta_{G}(s,t)=\delta_{G}(s,y)+\delta_{G}(y,t)$ is not strongly connected
with $t$, i.e., $y\notin S$.

If $t\in X$, then let $jt$ be an arbitrary edge lying on some shortest $s\to
t$ path in $G$. We have $\delta_{G}(s,j)=\delta_{G}(s,t)-1$,
$A^{*}[s,j]<\infty$ by Lemma 7.4, and $A^{\prime}[j,t]<\infty$ since $j\notin
S$. As a result, $(F_{X})_{s,t}\leq A^{*}[s,j]+A^{\prime}[j,t]<\infty$. We
conclude that there exists $g=(W_{X})_{s,t}$ such that
$A^{*}[s,g],A^{\prime}[g,t]<\infty$. It follows that $g$ is not strongly
connected with $t$ and $g$ is reachable from $s$. By the definition of
$G_{s}$, the $g\to t$ path $\pi^{*}_{g,t}$ (which exists by
$A^{\prime}[g,t]<\infty$) is included in $G_{s}$. This certifies that the SCC
$S$ has an incoming edge from another SCC reachable from $s$.

Finally, suppose $t\in V\setminus X$. If $st\in E(G)$ or
$\pi^{\prime}_{s,t}\neq\perp$, then the corresponding edge or path
$\pi^{*}_{s,t}$ is included in $G_{s}$. Since that edge/path originates in
$S_{s}$ and ends in a different SCC $S$, it has to include at least one edge
coming to $S$ from another SCC reachable from $s$. So suppose
$\pi^{*}_{s,t}=\perp$. By Lemma 7.3, we obtain that some shortest $s\to t$
path has a suffix $rq\cdot\pi^{\prime}_{q,t}$, where $r\in X$ and
${\delta_{G}(s,r)<d}$. By the definition of $t$, $r$ is in a different SCC
than $t$. Hence, we have $A^{\prime}[r,t]\leq A[r,q]+A[q,t]<\infty$. As a
result, since $r$ is reachable from $s$, we have $(F_{V})_{s,t}\leq
A^{*}[s,r]+A^{\prime}[r,t]<\infty$. Thus, there exists $x=(W_{V})_{s,t}\in X$
such that $A^{*}[s,x]<\infty$ and $A^{\prime}[x,t]<\infty$ which in turn
implies that $x$ and $t$ are not strongly connected and $x$ is reachable from
$s$. Moreover, $w=L_{x,t}$ exists such that $A[x,w]<\infty$ and
$A[w,t]<\infty$. Hence, there exist paths $\pi^{*}_{x,w}$ and $\pi^{*}_{w,t}$
in $G$. Their concatenation $\pi^{*}_{x,w}\cdot\pi^{*}_{w,t}$, included in
$G_{s}$, certifies that $S$ has an incoming edge from another SCC reachable
from $s$. ∎

######  Corollary 7.9.

Given the matrices $F_{X},W_{X},F_{V},W_{V},L$ and the graph
$G_{\mathrm{SCC}}$, one can compute reachability trees from all sources $s\in
V$ in $O(n^{2}h)$ additional time.

###### Proof.

Note that for any $s\in V$, the subgraph $G_{s}\subseteq G$ preserving
reachability from $s$ has $O(nh)$ edges since it consists of the $O(n)$-sized
subgraph $G_{\mathrm{SCC}}$ and $O(n)$ $\leq h$-hop paths $\pi^{*}_{a,b}$.
Thus, some reachability tree in $G_{s}$ (and thus in $G$) can be computed in
$O(nh)$ time. ∎

#### Update time analysis.

Let us now summarize the update time of the data structure. Recall that we set
$\alpha\in[0,1]$ to be the smallest number such that
$\max(|C|,|H|,|D|)=O(\max(n/\tau,n/h,\Delta))\leq O(n^{\alpha})$, and
$\Delta=n^{\delta}$. The amortized update time can be bounded by:

$\begin{split}\widetilde{O}\left(\frac{h^{2}n^{\omega(1,\delta,1)+1}}{\Delta
b}+\frac{h^{2}n^{2+\rho}}{b}\cdot\left(1+\frac{n}{\Delta\tau}\right)+\frac{n^{2}b}{\Delta}+\Delta
h\tau n(h^{2}n^{\mu}+\beta)+h^{2}n^{2}\right.\\\
\left.+\frac{h^{2}n(n^{\omega(1,\mu,1)-\mu}+n^{1+\mu})}{\beta}+\frac{h^{2}n^{\omega(1,\delta,1)+1}}{\beta\Delta}+n^{\omega(1,\alpha,1)}/\epsilon\right).\end{split}$

Using the online balancing tool
[Bra]444https://jvdbrand.com/complexity/?terms=2h%2Bomega(1%2Cdelta%2C1)%2B1-delta-b%0A2h%2B2%2B0.529-b%0A2h%2B2%2B0.529-b%2B1-delta-
tau%0A2%2Bb-
delta%0Adelta%2Bh%2Btau%2B1%2B2h%2Bmu%0Adelta%2Bh%2Btau%2B1%2Bbeta%0A2h%2B2%0A2h%2B1%2Bomega(1%2Cmu%2C1)-mu-
beta%0A2h%2B1%2B1%2Bmu-beta%0A2h%2Bomega(1%2Cdelta%2C1)%2B1-delta-
beta%0Aomega(1%2C1-tau%2C1)%0Aomega(1%2C1-h%2C1)%0Aomega(1%2Cdelta%2C1)&a=1,
we find that by setting $\mu=0.355$, $\beta=n^{0.562}$, $b=n^{0.816}$,
$\Delta=n^{0.523}$, $h=n^{0.1035}$ and $t=n^{0.104}$, the obtained bound is
$O(n^{2.293}/\epsilon)$.

It is also interesting to investigate for what values $\omega$ the obtained
bound is better than $n^{\omega}$. For this, let us again use the bound
$\omega(1,a,1)\leq 2+a\cdot(\omega-2)$ (which yields $\rho\leq 1/(4-\omega)$)
to remove the dependency on rectangular matrix multiplication.

Since the only term that is non-increasing in $h$ is
$n^{\omega(1,\alpha,1)}\leq n^{2+\alpha(\omega-2)}$, having arbitrary
$h=\operatorname{poly}{n}$ makes this term sub-$n^{\omega}$. If all other
terms with the $h$-terms skipped are also polynomially smaller $n^{\omega}$,
then sufficiently small polynomial $h$ makes all terms smaller than
$n^{\omega}$.

Via experiments one can obtain that $\tau=h$ and $\beta=h^{2}n^{\mu}$ is a
good choice, and that the terms involving $\omega(1,\delta,1)$ are not
bottlenecks if the parameters are chosen optimally. As a result, to find the
threshold for $\omega$, we need to pick $\mu,\Delta,b$ such that the terms:

$\frac{n^{2}b}{\Delta},\frac{n^{3+\frac{1}{4-\omega}}}{b\Delta},\Delta
n^{1+\mu},n^{3+\mu(\omega-4)}$

are all polynomially smaller than $n^{\omega}$. Observe that it is beneficial
to balance the first two terms, which leads to
$b=n^{\frac{5-\omega}{8-2\omega}}$. Then, balancing with the third term yields
$\Delta=n^{\frac{13-3\omega}{16-4\omega}-\mu/2}$. Finally, balancing that with
the fourth term yields $\mu=\frac{38-10\omega}{(16-4\omega)(9-2\omega)}$. The
final running time for $\omega>2$ after simplifications and taking into
account small-polynomial $h,\tau=n^{O(\gamma)}$ becomes:

$O\left(n^{2+\frac{\omega-1}{18-4\omega}+\gamma}+n^{\omega-\gamma}/\epsilon\right),$

for any sufficiently small $\gamma>0$. This bound is polynomially better than
$n^{\omega}$ if $\omega>2+\frac{9-\sqrt{65}}{8}\approx 2.12$.

Amortization can be removed in a standard way, as was done in Section 6. The
following theorem summarizes the data structure developed in this section. See
1.2

##  8 Deterministic fully dynamic transitive closure faster than
$O(n^{\omega})$ for all $\omega>2$

In this section we show a simple deterministic data structure maintaining the
transitive closure of a digraph under vertex updates polynomially faster than
within $n^{\omega}$ worst-case update time, unless $\omega=2$. Compared to the
data structure of Theorem 1.2, we do not support optimal-time path reporting
here. However, as opposed to the path-reporting data structure, we obtain a
non-trivial worst-case update time for the entire range of possible values of
$\omega>2$.

The bottleneck in the data structure of Theorem 1.2 lies in recomputing most
of the pairwise $h$-bounded shortest paths. These paths have also been used to
compute the hitting set $H$ deterministically. The set $H$ hit all the
$h$-bounded shortest paths in the graph $G-(C\cup D)$. For transitive closure,
we do not need to hit the shortest paths; hitting a $h$-hop prefix of any path
would also be enough. Computing an $\widetilde{O}(n/h)$-sized hitting set
achieving that deterministically is still challenging in sub-$n^{\omega}$
time, though. To deal with this problem, we will use slightly larger (but
still sublinear) hitting sets that are, at the same time, slightly less costly
to recompute. Using weaker (in terms of quality and size) hitting sets is the
main idea behind the data structure developed in this section.

Let $h,d\in[1,n]$ be parameters such that $d\cdot h\geq 6n$, to be chosen
later. First of all, we set up the data structure of Theorem 3.1 that
explicitly maintains the values $\delta^{h}_{G}(s,t)$ for all pairs $(s,t)\in
V$ under vertex updates to $G$ in $\widetilde{O}(h^{2}n^{2})$ worst-case time
per update.

The below lemma gives an algorithm to compute hitting sets of non-necessarily
shortest paths.

######  Lemma 8.1.

Let $G=(V,E)$ be any digraph. Then, for any $\ell\in[1,n]$, in
$\widetilde{O}(n^{\omega})$ time one can deterministically compute a hitting
set $H\subseteq V$ of size $\widetilde{O}(n/\ell)$ satisfying the following.
For any $s,t\in V$ with $\delta_{G}(s,t)<\infty$, either
$\delta_{G}(s,t)<\ell$ or there is such a vertex $v\in H$ that
$\delta_{G}(s,v)\leq\ell$ and $\delta_{G}(v,t)<\infty$. If $G$ is strongly
connected, then the running time can be improved to $\widetilde{O}(n^{2})$.

###### Proof.

Suppose for any $s\in V$ we have computed a reachability tree $T_{s}$ from $s$
in $G$. Let $T_{s,h}$ be the tree $T_{s}$ pruned of all the vertices at depth
more than $h$. Note that for all $t\in V(T_{s,h})$ at depth less than $h$, we
necessarily have $\delta_{G}(s,t)<h$.

For all other $t\in V$ either $\delta_{G}(s,t)=\infty$, or there exists a leaf
$l_{t}$ at depth $h$ in $T_{s,h}$ such that one can reach $t$ from $s$ through
$l_{t}$. As a result, if $H\subseteq V$ hits all the $h$-hop root-leaf paths
in $T_{s,h}$, then there exists $v\in H$ such that $\delta_{G}(s,v)\leq h$ and
there exists a path $s\to v\to l_{t}\to t$. Therefore, it is enough to compute
an $\widetilde{O}(n/h)$-sized hitting set $H$ of all the $h$-hop root-leaf
paths in all of the trees $T_{s,h}$, $s\in V$. King [Kin99, Lemma 5.2] gave a
variant of the deterministic algorithm behind Lemma 6.1 that accomplishes
precisely this task in $\widetilde{O}(n^{2})$ time.

Finally, the reachability trees from all the sources in a general graph can be
computed deterministically in $\widetilde{O}(n^{\omega})$ time [AGMN92]. If
$G$ is strongly connected, then the same can be achieved in $O(n^{2})$ time by
running a graph search from every $s\in V$ in the sparse subgraph
$G_{\mathrm{SCC}}\subseteq G$ from Lemma 7.7. ∎

Lemma 8.1 alone is not enough to deterministically break through the
$O(n^{\omega})$ worst-case update bound. To achieve that, proceed as follows
upon each update. First, compute in $O(n^{2})$ the strongly connected
components of $G$, and their topological order using any classical algorithm.
Let $S_{1},\ldots,S_{k}$ be the SCCs of $G$ in the topological order, that is,
any edge $uv$ such that $u\in S_{i}$ and $v\in S_{j}$, satisfies $i\leq j$.
Next, partition the sequence $S_{1},\ldots,S_{k}$ into at most $2n/d$ _blocks_
$\mathcal{B}$ of consecutive SCCs such that each block $B\in\mathcal{B}$
spanning $S_{a}\cup\ldots\cup S_{b}$ satisfies either $a=b$ or
$|S_{a}|+\ldots+|S_{b}|\leq d$. Such a partition into blocks can be computed
by repeatedly locating the longest prefix $S_{i},\ldots,S_{j}$ of the
remaining sequence $S_{i},\ldots,S_{k}$ such that $|S_{i}|+\ldots+|S_{j}|\leq
d$ (if it exists), and forming either a block $S_{i}\cup\ldots\cup S_{j}$ if
$|S_{i}|\leq d$, or a single-SCC block $S_{i}$ if $|S_{i}|>d$. Note that every
two consecutive blocks formed span more than $d$ vertices and this is why the
total number of blocks is at most $2n/d$.

We say that a block $S_{a}\cup\ldots\cup S_{b}=B\in\mathcal{B}$ is _small_ if
$|S_{a}|+\ldots+|S_{b}|\leq d$. Otherwise, we call the block _large_. Recall
that a large block necessarily consists of a single SCC of $G$.

Next, for each block $B\in\mathcal{B}$ we compute the hitting set $H_{B}$ of
Lemma 8.1 applied to the subgraph $G[B]$ for
$\ell:=\lfloor\frac{dh}{6n}\rfloor$. Note that we have
$|H_{B}|=\widetilde{O}\left(\frac{|B|n}{dh}\right)$. Set
$H^{*}:=\bigcup_{B\in\mathcal{B}}H_{B}$. We obtain that
$|H^{*}|=\widetilde{O}\left(\sum_{B\in\mathcal{B}}\frac{|B|n}{dh}\right)=\widetilde{O}\left(\frac{n}{dh}\cdot\sum_{B\in\mathcal{B}}|B|\right)=\widetilde{O}\left(\frac{n^{2}}{dh}\right)$.

Observe that the total time spent on computing hitting sets in small blocks
can be bounded by $\widetilde{O}((n/d)\cdot
d^{\omega})=\widetilde{O}(nd^{\omega-1})$ since $|\mathcal{B}|=O(n/d)$. Every
large block is strongly connected and thus the hitting sets of large blocks
can be computed in
$\widetilde{O}\left(\sum_{B\in\mathcal{B}}|B|^{2}\right)=\widetilde{O}(n^{2})$
time.

######  Lemma 8.2.

Let $s,t\in V$ be such that $\delta_{G}(s,t)<\infty$. Then either
$\delta_{G}(s,t)\leq h$ or there exists $v\in H^{*}$ such that
$\delta_{G}(s,v)\leq h$ and $\delta_{G}(v,t)<\infty$.

###### Proof.

Suppose $\delta_{G}(s,t)>h$. Let $p\in V$ be any vertex such that
$\delta_{G}(s,p)=h$ and $\delta_{G}(s,t)=\delta_{G}(s,p)+\delta_{G}(p,t)$.
Note that any shortest $s\to p$ path $P$ in $G$ can be expressed as
$P_{0}\cdot e_{1}\cdot P_{1}\cdot\ldots\cdot e_{q}\cdot P_{q}$, where each
$P_{i}$ is a (possibly $0$-hop) maximal subpath containing vertices of a
single block $B(P_{i})\in\mathcal{B}$, and $e_{i}$ is an edge between distinct
blocks $B(P_{i-1})$ and $B(P_{i})$. Recall that the partition of SCCs into
blocks respects the topological ordering so each $B(P_{i-1})$ is strictly
earlier than $B(P_{i})$ in the ordering. It follows that all the blocks
$B(P_{i})$ are distinct and thus $q\leq|\mathcal{B}|\leq 2n/d$. As a result,
we obtain that some path $P_{j}$ has at least

$\frac{\sum_{i=0}^{q}|P_{i}|}{q+1}=\frac{|P|-q}{q+1}=\frac{h-q}{q+1}\geq\frac{h}{q+1}-1\geq\frac{h}{2n/d+1}-1\geq\frac{dh}{3n}-1\geq\frac{dh}{3n}-\frac{dh}{6n}=\frac{dh}{6n}\geq\ell$

edges. Let $x,y$ be the endpoints of $P_{j}$, i.e., $P_{j}$ is an $x\to y$
path.

Note that $|P_{j}|=\delta_{G[B(P_{j})]}(x,y)=\delta_{G}(x,y)\geq\ell$ since
$P$ is a shortest path in $G$. As a result, by Lemma 8.1 we obtain that there
exists some vertex $v\in H_{B(P_{j})}\subseteq H^{*}$ such that
$\delta_{G[B(P_{j})]}(x,v)\leq\ell$ and $\delta_{G[B(P_{j})]}(v,y)<\infty$. By
that, we have:

$\displaystyle\delta_{G}(s,v)$
$\displaystyle\leq\delta_{G}(s,x)+\delta_{G}(x,v)$
$\displaystyle=\delta_{G}(s,x)+\delta_{G[B(P_{j})]}(x,v)$
$\displaystyle\leq\delta_{G}(s,x)+\ell$ $\displaystyle\leq|P_{0}\cdot
e_{1}\cdot P_{1}\cdot\ldots e_{j-1}\cdot P_{j-1}\cdot e_{j}|+|P_{j}|$
$\displaystyle\leq|P|=h.$

Above we have also used a fact that for two vertices inside a single block,
every path between them needs to be fully contained in the block. We also
have:

$\displaystyle\delta_{G}(v,t)$
$\displaystyle\leq\delta_{G}(v,y)+\delta_{G}(y,p)+\delta_{G}(p,t)$
$\displaystyle\leq\delta_{G[B(P_{j})]}(v,y)+\delta_{G}(y,p)+\delta_{G}(p,t)$
$\displaystyle<\infty.$

We conclude that indeed $\delta_{G}(s,t)>h$ implies that $\delta_{G}(s,v)\leq
h$ and $\delta_{G}(v,t)<\infty$. ∎

With the hitting set $H^{*}$ computed, we find the transitive closure of $G$
as follows. Let $A$ be a $V\times V$ boolean matrix such that $A_{u,v}=1$ iff
$\delta_{G}^{h}(u,v)\leq h$. Recall that the values $\delta_{G}^{h}(u,v)$ are
maintained explicitly under vertex updates by the data structure of Theorem
3.1. We define an analogous matrix $A^{*}$ as in Section 7:

$A^{*}=A\lor\left(A[V,H^{*}]\cdot(A[H^{*},H^{*}])^{n}\cdot A[H^{*},V]\right),$

where $\cdot$ denotes the boolean matrix product.

######  Lemma 8.3.

For any $s,t\in V$, there exists an $s\to t$ path in $G$ iff $A^{*}_{s,t}=1$.

Having proved Lemma 8.2, the proof of the above lemma proceeds completely
analogously to that of Lemma 7.4 so we skip it. To compute the transitive
closure of $G$, we simply compute the matrix $A^{*}$ from the definition
(similarly as in Section 7) via rectangular matrix multiplication.

Let us now analyze the update time. If $\alpha<1$ is such that
$|H^{*}|=\widetilde{O}(n^{2}/(dh))=\widetilde{O}(n^{\alpha})$, then the worst-
case update time of the data structure can be bounded by:

$\widetilde{O}\left(h^{2}n^{2}+nd^{\omega-1}+n^{\omega(1,\alpha,1)}\right)\subseteq\widetilde{O}\left(h^{2}n^{2}+nd^{\omega-1}+\frac{n^{2\omega-2}}{(dh)^{\omega-2}}\right).$

Note that for $d=n^{1-\epsilon}$, $h=n^{2\epsilon}$, the update bound is
$\widetilde{O}(n^{2+4\epsilon}+n^{\omega-\epsilon(\omega-1)}+n^{\omega-\epsilon(\omega-2)})$.
For any $0<\epsilon<\frac{\omega-2}{4}$ this bound is polynomially smaller
than $n^{\omega}$. Such an $\epsilon$ exists iff $\omega>2$. See 1.3
Interestingly, with the currently known upper bounds on the exponents of
(rectangular) matrix multiplication, it is best to set $h=0.15$, $d=0.945$
[Bra]. This yields an $O(n^{2.3})$ worst-case update bound that is slightly
worse then the bound obtained in Theorem 1.2.

#### Path reporting.

Finally, we remark that given an explicitly recomputed transitive closure
matrix, and by spending additional $O(n^{2})$-time preprocessing time per
update, reporting paths between arbitrary (reachable) pairs of vertices can be
supported in $O(n)$ time. We now sketch how this is achieved. [KMS22, Section
3.2] showed that given a topological order of an acyclic digraph $G^{\prime}$,
for any vertices $s,t$ such that $s$ can reach $t$ in $G^{\prime}$, some $s\to
t$ path can be constructed by issuing $O(n)$ reachability queries in
$G^{\prime}$. That is, if the transitive closure matrix of $G^{\prime}$ is
explicitly stored, a path can be constructed in $O(n)$ time. Since in our data
structure we spend $\Omega(n^{2})$ time per update anyway, after each update
in $O(n^{2})$ time we can construct a _condensation_ $G^{\prime}$ of $G$ by
contracting the SCCs of $G$ into single vertices. The condensation
$G^{\prime}$ is a DAG; hence, its topological order can be computed in
$O(n^{2})$ time. Moreover, the transitive closure of $G^{\prime}$ can be
easily read from the transitive closure of $G$ by taking a submatrix on
arbitrary representatives of the individual SCCs of $G$. Finally, observe that
an $s\to t$ path in $G$ can be found by (1) finding some path $P^{\prime}$
from the SCC of $s$ (in $G$) to the SCC of $t$ in the condensation
$G^{\prime}$ in $O(n)$ time, (2) subsequently finding any $s\to t$ path in the
$O(n)$-sized subgraph $P^{\prime}\cup G_{\mathrm{SCC}}$ via graph search.

##  9 Randomized improvements

In this section we show sketch how one can obtain sharper worst-case update
bounds for SSSP and transitive closure if randomization is used.

First of all, in all the components that use path counting, each $h^{2}$ term
in the update/query bounds can be replaced with a $h$ term in a standard way
(see, e.g., [San05]). This is because the used components only require testing
whether the maintained path counts are zero or non-zero. Hence, instead of
using $\widetilde{\Theta}(h)$-bit numbers for path counts, one can perform
counting modulo a random $\Theta(\log{n})$-bit prime number which is enough to
differentiate between zero and non-zero counts with high probability.
Arithmetic operations on numbers from such a range cost $\widetilde{O}(1)$
time as opposed to $\widetilde{O}(h)$ time required in the deterministic path
counting data structures.

###  9.1 Path-reporting transitive closure

In the case of path-reporting data structure of Section 7, it is not clear how
to exploit randomization further (beyond reducing the cost of path counting)
while still maintaining all-pairs single-source reachability trees against an
adaptive adversary. Hence, the obtained randomized worst-case update bound
becomes:

$\begin{split}\widetilde{O}\left(\frac{hn^{\omega(1,\delta,1)+1}}{\Delta
b}+\frac{hn^{2+\rho}}{b}\cdot\left(1+\frac{n}{\Delta\tau}\right)+\frac{n^{2}b}{\Delta}+\Delta
h\tau n(hn^{\mu}+\beta)+hn^{2}\right.\\\
\left.+\frac{hn(n^{\omega(1,\mu,1)-\mu}+n^{1+\mu})}{\beta}+\frac{hn^{\omega(1,\delta,1)+1}}{\beta\Delta}+n^{\omega(1,\alpha,1)}\right).\end{split}$

Using the online balancing tool [Bra], we find that by setting $\mu=0.368$,
$\beta=n^{0.503}$, $b=n^{0.764}$, $d=n^{0.495}$, $h=n^{0.135}$ and
$t=n^{0.136}$, the obtained bound is $O(n^{2.27})$. That being said, the used
improvement has no effect on the theoretical barrier of the approach: for
$\omega<2.12$, $\widetilde{O}(n^{\omega})$-time trivial recompute-from-scratch
approach is polynomially faster than the above.

###  9.2 SSSP

In the case of single-source shortest paths, we can exploit the standard
randomized hitting set argument [UY91], that a randomly sampled subset
$H\subseteq V$ of size $\Theta((n/h)\log{n})$ hits some shortest $s\to t$ path
in $G$ for all pairs $s,t$ with $\delta_{G}(s,t)\geq h$. Crucially, in the
dynamic setting, a sampled hitting set remains (w.h.p.) valid through
$\operatorname{poly}(n)$ versions of the evolving graph provided that it is
not revealed to the adversary. In the case of maintaining exact single-source
distances in dynamic unweighted digraphs, this assumption is indeed satisfied,
as the answers sought are unique.

The overall framework is the same as in Section 6: we operate in phases of
$\Delta$ edge updates, and maintain global data structures $\mathcal{T}$ and
$\mathcal{A}$, defined exactly as in Section 6, albeit now using the
aforementioned randomized path counting.

The main modification we make to the data structure of Section 6 is replacing
the preprocessing of Theorem 5.1 with the following variation due to [ACK17].

######  Lemma 9.1.

[ACK17] Let $G=(V,E)$ be a directed graph. Let $h\in[1,n]$.

Assume one has constructed a data structure storing $G$ and a subset
$W\subseteq V$ initially equal to $V$, and supporting:

  1. (1)

updates removing a vertex $v\in V$ from $W$,

  2. (2)

queries computing shortest $h$-bounded paths in $G[W]$ from a query vertex $s$
to _all_ $v\in V$.

Suppose one can perform updates in $U(n,h)$ _worst-case_ time, and queries in
$Q(n,h)$ worst-case time. These bounds have to hold w.h.p. against an
_adaptive_ adversary.

Let $C_{0}\subseteq V$. Then, in $O(|C_{0}|\cdot(nh+U(n,h)+Q(n,h)))$ time one
can compute a set ${C=\\{c_{1},\ldots,c_{k}\\}}$, where $C_{0}\subseteq
C\subseteq V$ and $k=O(|C_{0}|)$, and a collection of paths $\Pi$ in $G$,
containing at most one path $\pi_{s,t}$ for all $(s,t)\in C\times V$, such
that, with high probability:

  1. (a)

For any $i=1,\ldots,k$ and $t\in V$, $\pi_{c_{i},t}\in\Pi$ exists iff
$\delta_{G_{i}}^{h}(c_{i},t)\neq\infty$ and then $\pi_{c_{i},t}$ is a shortest
$h$-bounded $c_{i}\to t$ path in the graph
$G_{i}:=G-\\{c_{1},\ldots,c_{i-1}\\}$.

  2. (b)

For any $u\in V$, there exist at most $O(hn\log{n})$ paths $\pi_{s,t}\in\Pi$
with $u\in V(\pi_{s,t})$.

###### Proof sketch..

The preprocessing differs from that in Lemma 3.2 in the way how the subsequent
sources are picked. Whereas in Lemma 3.2 sources (from all of $V$) are picked
in arbitrary order, in the construction of [ACK17, Section 3.1], one
alternates between picking an arbitrary unprocessed element of $C_{0}$, and
the most-congested vertex (that is, lying on the maximum number of paths
picked so far) from $V\setminus C$. This way, only $O(|C_{0}|)$ vertices are
added to $W$ and $O(|C_{0}|)$ queries are issued. The $O(hn\log{n})$ bound in
item (b) follows via an analysis of a greedy load balancing technique [LO88].
This argument has been originally used in this context by [Tho05]. See [ACK17]
for details. ∎

More specifically, the congested set/paths collection pair $(C,\Pi)$ of
Theorem 5.1 is replaced with the corresponding pair $(C,\Pi)$ produced by
Lemma 9.1 with $C_{0}:=H$, where $H$ is the aforementioned randomly sampled
hitting set. Importantly, the obtained set $C$ has size $\widetilde{O}(n/h)$
this way, and the collection $\Pi$ has $\widetilde{O}(n^{2}/h)$ paths (as
opposed to $\Theta(n^{2})$ in Theorem 5.1).

For computing the pair $(C,\Pi)$, we use the data structure $\mathcal{T}$.
Consequently, the worst-case time cost (per update) incurred by the
construction of $(C,\Pi)$ is now:

$\widetilde{O}\left(\frac{1}{\Delta}\cdot\frac{n}{h}\cdot\left(\frac{hn^{1+\omega(1,\mu,1)-\mu}}{b}+\frac{hn^{2+\mu}}{b}+nb\right)\right).$

For $\mu=\rho$, this becomes:

$\widetilde{O}\left(\frac{n^{3+\rho}}{b\Delta}+\frac{n^{2}b}{h\Delta}\right).$

Recall that besides that, the cost of maintaining $\mathcal{T}$ under single-
edge updates to $G$ is $\widetilde{O}(hn^{2+\rho}/b)$ per update.

We also redefine the contents of the maintained set $Y$ throughout the phase.
Recall that the values $\delta^{h}_{G}(s,t)$ are maintained for all $(s,t)\in
Y$ by the data structure $\mathcal{A}$ with $\nu$ set to $\rho\approx 0.529$.
At all times, the set $Y$ contains:

  * •

all pairs $(s,t)\in C\times V$ such that $\pi_{s,t}\in\Pi_{D}$,

  * •

all pairs $(u,v)\in(D\times V)\cup(V\times D)$.

Observe that by Lemma 9.1, the set $Y$ grows by $\widetilde{O}(hn)$ new pairs
per update in the worst case, and thus can be appropriately extended in
$\widetilde{O}(hn^{1+\rho})$ time per update. Moreover,
$|Y|=\widetilde{O}(\Delta hn)$ at all times and thus $\mathcal{A}$ requires
$\widetilde{O}(\Delta h^{2}n)$ additional time per update to recompute the
values $\delta_{G}^{h}(s,t)$ for all $(s,t)\in Y$.

The summarized worst-case update time of all the components of the data
structure is:

$\widetilde{O}\left(\frac{hn^{2+\rho}}{b}+\Delta
h^{2}n+\frac{n^{3+\rho}}{b\Delta}+\frac{n^{2}b}{h\Delta}+h^{2}n^{1+\rho}\right).$

For answering single-source distance queries, we use a slightly simpler
auxiliary graph $X$, defined similarly as in Section 6. Suppose a query for
distances from a source vertex $s\in V$ is issued. Let $Y_{s}$ be the set $Y$
augmented with temporary pairs $(s,t)$ for all $t\in V$. The graph $X$
contains:

  * •

an edge $uv$ of weight $|\pi_{u,v}|$ for all
$\pi_{u,v}\in\Pi\setminus\Pi_{D}$,

  * •

an edge $uv$ of weight $\delta_{G}^{h}(u,v)$ for all $(u,v)\in Y_{s}$.

Again, the graph $X$ has $O(n^{2}/h+|Y|)=\widetilde{O}(n^{2}/h+\Delta hn)$
edges. The query procedure runs Dijkstra‘s algorithm from $s$ on the graph
$X$. This is correct by the following lemma.

######  Lemma 9.2.

With high probability, for any $t\in V$, $\delta_{G}(s,t)=\delta_{X}(s,t)$.

###### Proof.

Note that for all $uv\in E(X)$, $w_{X}(uv)\geq\delta_{G}(uv)$, which
establishes $\delta_{G}(s,t)\leq\delta_{X}(s,t)$ easily.

Let us now prove that $\delta_{X}(s,t)\leq\delta_{G}(s,t)$. First of all, let
$G_{0}$ be the graph at the beginning of the phase. Note that by the
definition of $D$, we have $G_{0}-D=G-D\subseteq G$.

Consider the shortest $s\to t$ path $P$ in $G$; if there are many, pick the
unique one that is lexicographically smallest. Split $P$ into maximal segments
$P_{1}\cdot\ldots\cdot P_{k}$ not passing through any of the vertices $C\cup
D$. In other words, for each $P_{i}=u_{i}\to v_{i}$, we have
$V(P_{i})\cap(C\cup D)\subseteq\\{u_{i},v_{i}\\}$ and $u_{i}\in C\cup
D\cup\\{s\\}$.