# Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time111A
preliminary version appeared in STOC 2021

Julia Chuzhoy Toyota Technological Institute at Chicago. Email:
<EMAIL_ADDRESS>Supported in part by NSF grants CCF-1616584 and CCF-2006464.

We study the decremental All-Pairs Shortest Paths (APSP) problem in undirected
edge-weighted graphs. The input to the problem is an undirected $n$-vertex
$m$-edge graph $G$ with non-negative lengths on edges, that undergoes an
online sequence of edge deletions. The goal is to support approximate
shortest-paths queries: given a pair $x,y$ of vertices of $G$, return a path
$P$ connecting $x$ to $y$, whose length is within factor $\alpha$ of the
length of the shortest $x$-$y$ path, in time $\tilde{O}(|E(P)|)$, where
$\alpha$ is the approximation factor of the algorithm. APSP is one of the most
basic and extensively studied dynamic graph problems. A long line of work
culminated in the algorithm of [Chechik, FOCS 2018] with near optimal
guarantees: for any constant $0<\epsilon\leq 1$ and parameter $k\geq 1$, the
algorithm achieves approximation factor $(2+\epsilon)k-1$, and total update
time $O(mn^{1/k+o(1)}\log(nL))$, where $L$ is the ratio of longest to shortest
edge lengths. Unfortunately, as much of prior work, the algorithm is
randomized and needs to assume an _oblivious adversary_ ; that is, the input
edge-deletion sequence is fixed in advance and may not depend on the
algorithm’s behavior.

In many real-world scenarios, and in applications of APSP to static graph
problems, it is crucial that the algorithm works against an _adaptive
adversary_ , where the edge deletion sequence may depend on the algorithm’s
past behavior arbitrarily; ideally, such an algorithm should be
_deterministic_. Unfortunately, unlike the oblivious-adversary setting, its
adaptive-adversary counterpart is still poorly understood. For unweighted
graphs, the algorithm of [Henzinger, Krinninger and Nanongkai, FOCS ’13,
SICOMP ’16] achieves a $(1+\epsilon)$-approximation with total update time
$\tilde{O}(mn/\epsilon)$; the best current total update time guarantee of
$n^{2.5+O(\epsilon)}$ is achieved by the recent deterministic algorithm of
[Chuzhoy, Saranurak, SODA’21], with $2^{O(1/\epsilon)}$-multiplicative and
$2^{O(\log^{3/4}n/\epsilon)}$-additive approximation. To the best of our
knowledge, for arbitrary non-negative edge weights, the fastest current
adaptive-update algorithm has total update time $O(n^{3}\log L/\epsilon)$,
achieving a $(1+\epsilon)$-approximation. Even if we are willing to settle for
any $o(n)$-approximation factor, no currently known algorithm has a better
than $\Theta(n^{3})$ total update time in weighted graphs and better than
$\Theta(n^{2.5})$ total update time in unweighted graphs. Several conditional
lower bounds suggest that no algorithm with a sufficiently small approximation
factor can achieve an $o(n^{3})$ total update time.

Our main result is a deterministic algorithm for decremental APSP in
undirected edge-weighted graphs, that, for any $\Omega(1/\log\log
m)\leq\epsilon<1$, achieves approximation factor $(\log
m)^{2^{O(1/\epsilon)}}$, with total update time
$O\left(m^{1+O(\epsilon)}\cdot(\log m)^{O(1/\epsilon^{2})}\cdot\log L\right)$.
In particular, we obtain a $(\operatorname{poly}\log m)$-approximation in time
$\widetilde{O}(m^{1+\epsilon})$ for any constant $\epsilon$, and, for any
slowly growing function $f(m)$, we obtain $(\log m)^{f(m)}$-approximation in
time $m^{1+o(1)}$. We also provide an algorithm with similar guarantees for
decremental Sparse Neighborhood Covers.

###### Contents

  1. 1 Introduction
    1. 1.1 Other Related Work
    2. 1.2 Our Results and Techniques
    3. 1.3 Organization
  2. 2 Preliminaries
  3. 3 Valid Input Structure, Valid Update Operations, Generalized Even-Shiloach Trees, and the Dynamic Recursive Neighborhood Cover Problem
    1. 3.1 Valid Input Structure and Valid Update Operations
    2. 3.2 Generalized Even-Shiloach Trees
    3. 3.3 The Recursive Dynamic Neighborhood Cover ($\mathsf{RecDynNC}$) Problem
    4. 3.4 A Faster Algorithm for $\mathsf{RecDynNC}$ and Proofs of Theorems 1.1 and 1.2
      1. 3.4.1 Completing the proof of Theorem 1.2
      2. 3.4.2 Completing the proof of Theorem 1.1
      3. 3.4.3 Proof of Theorem 3.4
  4. 4 First Set of Tools: Procedure $\mathsf{ProcCut}$, Initial Neighborhood-Cover Decomposition, and Reduction to $\mathsf{MaintainCluster}$ Problem
    1. 4.1 Basic Definition, Parameters and Notation
    2. 4.2 Procedure $\mathsf{ProcCut}$
    3. 4.3 Computing the Initial Neighborhood Cover – Procedure $\mathsf{InitNC}$
    4. 4.4 Algorithmic Framework for Maintaining Neighborhood Cover
    5. 4.5 $\mathsf{MaintainCluster}$ Problem and a Reduction from $\mathsf{RecDynNC}$ to $\mathsf{MaintainCluster}$
      1. 4.5.1 $\mathsf{MaintainCluster}$ Problem
      2. 4.5.2 Completing the Proof of Theorem 3.3
    6. 4.6 A Slow and Simple Algorithm for the $\mathsf{MaintainCluster}$ Problem
  5. 5 Second Main Tool: Balanced Pseudocuts, Expanders, and Their Embeddings
    1. 5.1 Balanced Pseudocuts
    2. 5.2 Expanders and Their Embeddings
    3. 5.3 Computing a Pseudocut, the Corresponding Expander, and its Embedding
    4. 5.4 APSP in Expanders
    5. 5.5 Maintaining the Expander
    6. 5.6 A Faster Algorithm for the $\mathsf{MaintainCluster}$ Problem
  6. 6 Third Main Tool: Good Clusters
    1. 6.1 Good Clusters and Witnesses
    2. 6.2 $\mathsf{MaintainGoodCluster}$ Problem and an Algorithm for It
  7. 7 Fourth Main Tool: Contracted Graph
    1. 7.1 Modified Graph $\tilde{H}$
    2. 7.2 Contracted Graph $\hat{H}$
    3. 7.3 Distance Preservation in the Contracted Graph
  8. 8 Putting Everything Together: Proof of Theorem 4.14
    1. 8.1 Phase 1
    2. 8.2 Phase 2
      1. 8.2.1 Maintaining the Modified Graph – Algorithm $\operatorname{Alg}_{1}$
      2. 8.2.2 Maintaining the Neighborhood Covers of $\tilde{H}$ and the Contracted Graph – Algorithm $\operatorname{Alg}_{2}$
      3. 8.2.3 Running $\mathsf{MaintainCluster}$ on the Contracted Graph – Algorithm $\operatorname{Alg}_{3}$
      4. 8.2.4 The ES-Tree: Algorithm $\operatorname{Alg}_{4}$
    3. 8.2.5 Running Time of Phase 2
    4. 8.3 Phase 3
    5. 8.4 Phase 4
    6. 8.5 Final Accounting of the Running Time
  9. 9 Parameters Used in Sections 6 – 8
  10. 10 Application: Fast Algorithm for Maximum Multicommodity Flow and Minimum Multicut
    1. 10.1 Implementing the Oracle
  11. 11 Acknowledgement
  12. A Proofs Omitted from Section 2
    1. A.1 Short Paths in Expanders – Proof of 2.1
    2. A.2 Expander Pruning – Proof of Theorem 2.2
  13. B Generalized Even-Shiloach Trees – Proof of Theorem 3.2
  14. C Recursive Composition of $\mathsf{RecDynNC}$ Instances – Proof of Lemma 3.5
  15. D Proofs Omitted from Section 4
    1. D.1 Proof of Claim 4.2
    2. D.2 Proof of 4.4
    3. D.3 Proof of Lemma 4.5
  16. E Proofs Omitted from Section 5
    1. E.1 Proof of Theorem 5.2
      1. E.1.1 Proof of Lemma E.1
      2. E.1.2 Proof of Theorem E.11
    2. E.2 Proof of Theorem 5.3
    3. E.2.1 Proof of Lemma E.13

##  1 Introduction

We study the decremental All-Pairs Shortest-Paths (APSP) problem in weighted
undirected graphs. In this problem, we are given as input an undirected graph
$G$ with lengths $\ell(e)\geq 1$ on its edges, that undergoes an online
sequence of edge deletions. The goal is to support (approximate) shortest-path
queries $\mbox{\sf{shortest-path-query}}(x,y)$: given a pair $x,y$ of vertices
of $G$, return a path connecting $x$ to $y$, whose length is within factor
$\alpha$ of the length of the shortest $x$-$y$ path in $G$, where $\alpha$ is
the _approximation factor_ of the algorithm. We also consider approximate
distance queries, $\mbox{\sf{dist-query}}(x,y)$: given a pair $x,y$ of
vertices of $G$, return an estimate $\mbox{\sf dist}^{\prime}(x,y)$ on the
distance $\mbox{\sf dist}_{G}(x,y)$ between $x$ and $y$ in graph $G$, such
that $\mbox{\sf dist}_{G}(x,y)\leq\mbox{\sf
dist}^{\prime}(x,y)\leq\alpha\cdot\mbox{\sf dist}_{G}(x,y)$. APSP is one of
the most basic and extensively studied problems in dynamic algorithms, and in
graph algorithms in general. Algorithms for this problem often serve as
building blocks in designing algorithms for other graph problems, in both the
classical static and the dynamic settings. Throughout, we denote by $m$ and
$n$ the number of edges and the number of vertices in the initial graph $G$,
respectively, and by $L$ the ratio of largest to smallest edge length. In
addition to the approximation factor of the algorithm, two other central
measures of its performance are: _query time_ – the time it takes to process a
single query; and _total update time_ – the total time that the algorithm
takes, over the course of the entire update sequence, to maintain its data
structures. Ideally, we would like the total update time of the algorithm to
be close to linear in $m$, and the query time for shortest-path-query to be
bounded by $\tilde{O}(|E(P)|)$, where $P$ is the path that the algorithm
returns.

A straightforward algorithm for the decremental APSP problem is the following:
every time a query $\mbox{\sf{shortest-path-query}}(x,y)$ arrives, compute the
shortest $x$-$y$ path in $G$ from scratch. This algorithm solves the problem
exactly, but it has query time $\Theta(m)$. Another approach is to rely on
_spanners_. A spanner of a dynamic graph $G$ is another dynamic graph
$H\subseteq G$, with $V(H)=V(G)$, such that the distances between the vertices
of $G$ are approximately preserved in $H$; ideally a spanner $H$ should be
very sparse. For example, a work of [BKS12] provides a randomized algorithm
that maintains a spanner of a fully dynamic $n$-vertex graph $G$ (that may
undergo both edge deletions and edge insertions), that, for any parameter $k$,
achieves approximation factor $(2k-1)$, has expected amortized update time
$O(k^{2}\log^{2}n)$ per update operation, and expected spanner size
$O(kn^{1+1/k}\log n)$. A recent work of [BBG+20] provides a randomized
algorithm for maintaining a spanner of a fully dynamic $n$-vertex graph $G$
with approximation factor $O(\operatorname{poly}\log n)$ and total update time
$\widetilde{O}(m^{*})$, where $m^{*}$ is the total number of edges ever
present in $G$; the number of edges in the spanner $H$ is always bounded by
$O(n\operatorname{poly}\log n)$. One significant advantage of this algorithm
over the algorithm of [BKS12] is that, unlike the algorithm of [BKS12], it can
withstand an adaptive adversary; we provide additional discussion of oblivious
versus adaptive adversary below. An algorithm for the APSP problem can
naturally build on such constructions of spanners: given a query
$\mbox{\sf{shortest-path-query}}(x,y)$ or $\mbox{\sf{dist-query}}(x,y)$, we
simply compute the shortest $x$-$y$ path in the spanner $H$. For example, the
algorithm for graph spanners of [BBG+20] implies a randomized
$\operatorname{poly}\log n$-approximation algorithm for APSP that has
$O(m\operatorname{poly}\log n)$ total update time. A recent work of [BHG+20]
provides additional spanner-based algorithms for APSP. Unfortunately, it seems
inevitable that this straightforward spanner-based approach to APSP must have
query time $\Omega(n)$ for both shortest-path-query and dist-query.

In this paper, our focus is on developing algorithms for the APSP problem,
whose query time is $\tilde{O}(|E(P)|)$ for shortest-path-query, where $P$ is
the path that the query returns, and $O(\operatorname{poly}\log(mL))$ for
dist-query. There are several reasons to strive for these faster query times.
First, we typically want responses to the queries to be computed as fast as
possible, and the above query times are close to the fastest possible. Second,
obtaining $\tilde{O}(|E(P)|)$ query time for shortest-path-query is often
crucial to obtaining fast algorithms for classical (static) graph problems
that use algorithms for APSP as a subroutine. We provide an example of such an
application to (static) Maximum Multicommodity Flow/ Minimum Multicut in
uncapacitated graphs in Section 10.

We distinguish between dynamic algorithms that work against an _oblivious
adversary_ , where the input sequence of edge deletions is fixed in advance
and may not depend on the algorithm’s past behavior, and algorithms that work
against an _adaptive adversary_ , where the input update sequence may depend
on the algorithm’s past responses and inner states arbitrarily. We refer to
the former as _oblivious-update_ and to the latter as _adaptive-update_
algorithms. We note that any deterministic algorithm for the APSP problem is
an adaptive-update algorithm by definition.

The classical data structure of Even and Shiloach [ES81, Din06, HK95], that we
refer to as ES-Tree throughout the paper, implies an exact deterministic
algorithm for decremental unweighted APSP with $O(mn^{2})$ total update time,
and the desired $O(|E(P)|)$ query time for shortest-path-query, where $P$ is
the returned path. Short of obtaining an exact algorithm for APSP, the best
possible approximation factor one may hope for is $(1+\epsilon)$, for any
$\epsilon$. A long line of work [BHS07, RZ12, HKN16, Ber16] is dedicated to
this direction. The fastest algorithms in this line of work, due to Henzinger,
Krinninger, and Nanongkai [HKN16], and due to Bernstein [Ber16] achieve total
update time $\tilde{O}(mn/\epsilon)$; the former algorithm is deterministic
but only works in unweighted undirected graphs, while the latter algorithm
works in directed weighted graphs, with an overhead of $\log L$ in the total
update time, but can only handle an oblivious adversary. Unfortunately, known
conditional lower bounds show that these algorithms are likely close to the
best possible. Specifically, Dor, Halperin and Zwick [DHZ00], and Roddity and
Zwick [RZ11] showed that, assuming the Boolean Matrix Multiplication (BMM)
conjecture222The conjecture states that there is no “combinatorial” algorithm
for multiplying two Boolean matrices of size $n\times n$ in time
$n^{3-\delta}$ for any constant $\delta>0$., for any $\alpha,\beta\geq 1$ with
$2\alpha+\beta<4$, no combinatorial algorithm for APSP achieves a
multiplicative $\alpha$ and additive $\beta$ approximation, with total update
time $O(n^{3-\delta})$ and query time $O(n^{1-\delta})$, for any constant
$0<\delta<1$. Henzinger et al. [HKNS15] generalized this result to show the
same lower bounds for all algorithms and not just combinatorial ones, assuming
the Online Boolean Matrix-Vector Multiplication (OMV) conjecture333The
conjecture assumes that there is no $n^{3-\delta}$-time algorithm, for any
constant $0<\delta<1$, for the OMV problem, in which the input is a Bollean
$(n\times n)$ matrix, with $n$ Boolean dimension-$n$ vectors
$v_{1},\ldots,v_{n}$ arriving online. The algorithm needs to output $Mv_{i}$
immediately after $v_{i}$ arrives.. The work of Vassilevska Williams and
Williams [WW18], combined with the work of Roddity and Zwick [RZ11], implies
that obtaining such an algorithm would lead to subcubic-time algorithms for a
number of important static problems on graphs and matrices.

Due to these negative results, much work on the APSP problem inevitably
focused on higher approximation factors. In this regime, the oblivious-update
setting is now reasonably well understood. A long line of work [BR11, HKN16,
ACT14, FHN14a] recently culminated with a randomized algorithm of Chechik
[Che18], that, for any integer $k\geq 1$ and parameter $0<\epsilon<1$, obtains
a $((2+\epsilon)k-1)$-approximation, with total update time
$O(mn^{1/k+o(1)}\log L)$, when the input graph is weighted and undirected.
This result is near-optimal, as all its parameters almost match the best
static algorithm of [TZ01]. We note that this result was recently slightly
improved by [ŁN20], who obtain total update time $O(mn^{1/k}\log L)$, and
improve query time for dist-query.

In contrast, progress in the adaptive-update setting has been much slower.
Until recently, the fastest adaptive-update algorithm for unweighted graphs,
due to Henzinger, Krinninger, and Nanongkai [HKN16], only achieved an
$\tilde{O}(mn/\epsilon)$ total update time (for approximation factor
$(1+\epsilon)$); the algorithm was recently significantly simplified by
Gutenberg and Wulff-Nilsen [GWN20]. A recent work of [CS21] provided a
deterministic algorithm for unweighted undirected graphs, that, for any
parameter $1\leq k\leq o(\log^{1/8}n)$, in response to query
$\mbox{\sf{shortest-path-query}}(x,y)$, returns a path of length at most
$3\cdot 2^{k}\cdot\mbox{\sf dist}_{G}(x,y)+2^{(O(k\log^{3/4}n)}$, with query
time $O(|E(P)|\cdot n^{o(1)})$ for shortest-path-query, and total update time
$n^{2.5+2/k+o(1)}$. To the best of our knowledge, the fastest current
adaptive-update algorithm for weighted graphs has total update time
$O(n^{3}\log L/\epsilon)$ and approximation factor $(1+\epsilon)$ (see
[KŁ19]).

Interestingly, even if we allow an $o(n)$-approximation factor, no adaptive-
update algorithms with better than $\Theta(n^{3})$ total update time and
better than $\Theta(n)$ query time for shortest-path-query and dist-query are
currently known for weighted undirected graphs, and no adaptive-update
algorithms with better than $\Theta(n^{2.5})$ total update time and better
than $\Theta(n)$ query time are currently known for unweighted undirected
graphs. Moreover, even for the seemingly simpler Single-Source Shortest Path
problem (SSSP), where all queries must be between a pre-specified source
vertex $s$ and another arbitrary vertex of $G$, no algorithms achieving a
better than $\Theta(n^{2})$ total update time, and better than $\Theta(n)$
query time for shortest-path-query are known. To summarize, ideally we would
like an algorithm for decremental APSP in weighted undirected graphs that
achieves the following properties:

  * •

it can withstand an adaptive adversary (and is ideally deterministic);

  * •

it has query time $\tilde{O}(|E(P)|)$ for shortest-path-query, where $P$ is
the returned path, and query time $\tilde{O}(1)$ for dist-query;

  * •

it has near-linear in $m$ total update time; and

  * •

it has a reasonably low approximation factor (ideally, polylogarithmic or
constant).

Our main result comes close to achieving all these properties. Specifically,
we provide a _deterministic_ algorithm for APSP in weighted undirected graphs.
For any precision parameter $\Omega(1/\log\log m)<\epsilon<1$, the algorithm
achieves approximation factor $(\log m)^{2^{O(1/\epsilon)}}$, with total
update time:

$O\left(m^{1+O(\epsilon)}\cdot(\log m)^{O(1/\epsilon^{2})}\cdot\log L\right).$

The query time for processing dist-query is $O(\log m\log\log L)$, and the
query time for shortest-path-query is $O(|E(P)|)+O(\log m\log\log L)$, where
$P$ is the returned path. In particular, by letting $\epsilon$ be a small
enough constant, we obtain a $O(\operatorname{poly}\log m)$-approximation with
total update time time $O(m^{1+\delta})$, for any constant $0<\delta<1$, and
by letting $1/\epsilon$ be a slowly growing function of $m$ (for example,
$1/\epsilon=O(\log(\log^{*}m))$), we obtain an approximation factor $(\log
m)^{O(\log^{*}m)}$, and total update time $O(m^{1+o(1)})$.

In fact we design an algorithm for a more general problem: _dynamic Sparse
Neighborhood Cover_. Given a graph $G$ with lengths on edges, a vertex $v\in
V(G)$, and a distance parameter $D$, we denote by $B_{G}(v,D)$ the _ball of
radius $D$ around $v$_, that is, the set of all vertices $u$ with $\mbox{\sf
dist}_{G}(v,u)\leq D$. Suppose we are given a static graph $G$ with non-
negative edge lengths, a distance parameter $D$ (that we call _target distance
threshold_), and a desired approximation factor $\alpha$. A $(D,\alpha\cdot
D)$-_neighborhood cover_ for $G$ is a collection ${\mathcal{C}}$ of vertex-
induced subgraphs of $G$ (that we call _clusters_), such that, for every
vertex $v\in V(G)$, there is some cluster $C\in{\mathcal{C}}$ with
$B_{G}(v,D)\subseteq V(C)$. Additionally, we require that for every cluster
$C\in{\mathcal{C}}$, for every pair $x,y\in V(C)$ of its vertices, $\mbox{\sf
dist}_{G}(x,y)\leq\alpha\cdot D$; if this property holds, then we say that
${\mathcal{C}}$ is a _weak_ $(D,\alpha\cdot D)$-neighborhood cover of $G$. If,
additionally, the diameter of every cluster $C\in{\mathcal{C}}$ is bounded by
$\alpha\cdot D$, then we say that ${\mathcal{C}}$ is a _strong_
$(D,\alpha\cdot D)$-neighborhood cover of $G$. Ideally, it is also desirable
that the neighborhood cover is _sparse_ , that is, every edge (or every
vertex) of $G$ only lies in a small number of clusters of ${\mathcal{C}}$. For
this static setting of the problem, the work of [AP90, ABCP98] provides a
deterministic algorithm that produces a strong $(D,O(D\log n))$-neighborhood
cover of graph $G$, where every edge lies in at most $O(\log n)$ clusters,
with running time $\widetilde{O}(|E(G)|+|V(G)|)$.

In this paper we consider a _decremental_ version of the problem, in which the
input graph $G$ undergoes an online sequence of edge deletions. We are
required to maintain a weak $(D,\alpha\cdot D)$-neighborhood cover
${\mathcal{C}}$ of the graph $G$, and we require that the clusters in
${\mathcal{C}}$ may only be updated in a specific fashion: once an initial
neighborhood cover ${\mathcal{C}}$ of $G$ is computed, we are only allowed to
delete edges or vertices from clusters that lie in ${\mathcal{C}}$, or to add
a new cluster $C$ to ${\mathcal{C}}$, which must be a subgraph of an existing
cluster of ${\mathcal{C}}$. Additionally, we require that the algorithm
supports queries $\mbox{\sf{short-path-query}}(C,v,v^{\prime})$: given two
vertices $v,v^{\prime}\in V$, and a cluster $C\in{\mathcal{C}}$ with
$v,v^{\prime}\in C$, return a path $P$ in the current graph $G$, of length at
most $\alpha\cdot D$ connecting $v$ to $v^{\prime}$ in $G$, in time
$O(|E(P)|)$. The algorithm must also maintain, for every vertex $v\in V(G)$, a
cluster $C=\mbox{\sf{CoveringCluster}}(v)$ in ${\mathcal{C}}$, with
$B_{G}(v,D)\subseteq V(C)$. Lastly, we require that the neighborhood cover is
_sparse_ , namely, for every vertex $v$ of $G$, the total number of clusters
of ${\mathcal{C}}$ to which $v$ may ever belong over the course of the
algorithm is small. It is not hard to verify that an algorithm for the
decremental Sparse Neighborhood Cover problem that we just defined immediately
implies an algorithm for decremental APSP with the same approximation factor,
and the same total update time (to within $O(\log L)$-factor). We provide a
deterministic algorithm for the dynamic Sparse Neighborhood Cover problem with
approximation factor $\alpha=O\left((\log m)^{2^{O(1/\epsilon)}}\right)$, and
total update time $O\left(m^{1+O(\epsilon)}\cdot(\log
m)^{O(1/\epsilon^{2})}\right)$. Our algorithm ensures that, for every vertex
$v\in V(G)$, the total number of clusters of ${\mathcal{C}}$ that $v$ ever
belongs to is bounded by $m^{O(1/\log\log m)}$. We note that algorithms for
static Sparse Neighborhood Covers have found many applications in the area of
graph algorithms, and so we believe that our algorithm for dynamic Sparse
Neighborhood Cover is interesting in its own right. A Sparse Neighborhood
Cover for a dynamic graph $G$ naturally provides an emulator for $G$. If graph
$G$ is decremental, then, while the edges may sometimes be inserted into the
emulator (when a new cluster is added to the neighborhood cover
${\mathcal{C}}$), due to the restrictions that we impose on the types of
allowed updates to the clusters of ${\mathcal{C}}$, such edge insertions are
limited to very specific types, and so they are relatively easy to deal with.
This allows us to compose emulators given by the neighborhood covers
recursively. We note that the idea of using clustering of a dynamic graph $G$
in order to construct an emulator was used before (see e.g. the constructions
of [FG19, CZ20, FGH20] of dynamic low-stretch spanning trees). In several of
these works, a family of clusters of a dynamic graph $G$ is constructed and
maintained, and the restrictions on the allowed updates to the cluster family
are similar to the ones that we impose; it is also observed in several of
these works that with such restrictions one can naturally compose the
resulting emulators recursively – an approach that we follow here as well.
However, neither of these algorithms provide neighborhood covers, and in fact
the clusters that are maintained for each distance scale are disjoint
(something that cannot be achieved by neighborhood covers). Additionally, all
the above-mentioned algorithms are randomized and assume an oblivious
adversary. On the other hand, the algorithms of [HKN16, GWN20] implicitly
provide a deterministic algorithm for maintaining a neighborhood cover of a
dynamic graph. However, these algorithms have a number of drawbacks: first,
the running time for maintaining the neighborhood cover is too prohibitive
(the total update time is $O(mn)$). Second, the neighborhood cover maintained
is not necessarily sparse; in fact a vertex may lie in a very large number of
resulting clusters. Lastly, clusters that join the neighborhood cover as the
algorithm progresses may be arbitrary. The restriction that, for every cluster
$C$ added to the neighborhood cover ${\mathcal{C}}$, there must be a cluster
$C^{\prime}$ containing $C$ that already belongs to ${\mathcal{C}}$, seems
crucial in order to allow an easy recursive composition of emulators obtained
from the neighborhood covers, and the requirement that the neighborhood cover
is sparse is essential for bounding the sizes of the graphs that arise as the
result of such recursive compositions.

We provide an application of our algorithm for the APSP problem: a
deterministic algorithm for Maximum Multicommodity Flow and Minimum Multicut
in unit-capacity graphs. In both problems, the input is an undirected
$n$-vertex $m$-edge graph $G$, and a collection
${\mathcal{M}}=\left\\{(s_{1},t_{1}),\ldots,(s_{k},t_{k})\right\\}$ of pairs
of its vertices, called _demand pairs_. In the Maximum Multicommodity Flow
problem, the goal is to send maximum amount of flow between the demand pairs,
such that the total amount of flow traversing each edge is at most $1$. We
denote by $\mathsf{OPT}_{\mathsf{MCF}}$ the value of the optimal solution to
this problem. In the Minimum Multicut problem, given a graph $G$ and a
collection ${\mathcal{M}}$ of demand pairs as before, the goal is to select a
minimum-cardinality subset $E^{\prime}\subseteq E(G)$ of edges, such that, for
all $1\leq i\leq k$, vertices $s_{i}$ and $t_{i}$ lie in different connected
components of $G\setminus E^{\prime}$. We use the standard primal-dual
technique-based algorithm of [GK98, Fle00], that can equivalently be viewed as
an application of the multiplicative weight update paradigm [AHK12], which
essentially reduces the Multicommodity Flow problem to decremental APSP; this
reduction was first discovered by [Mad10]. Plugging in our algorithm for APSP,
we obtain a deterministic algorithm for Maximum Multicommodity Flow, that, for
any $0<\epsilon<1$, achieves approximation factor $O\left((\log
m)^{2^{O(1/\epsilon)}}\right)$, and has running time
$\tilde{O}\left(m^{1+O(\epsilon)}(\log
m)^{2^{O(1/\epsilon)}}+k/\epsilon\right)$. The algorithm also provides an
integral solution to the Maximum Multicommodity Flow problem with congestion
$O(\log n)$, and a fractional solution to the standard LP-relaxation for
Minimum Multicut. Using the standard ball-growing technique of [LR99, GVY95],
we then obtain an algorithm for Minimum Multicut, with the same asymptotic
running time, and similar approximation factor. The fastest previous
approximation algorithms for Maximum Multicommodity Flow, achieving
$(1+\epsilon)$-approximation, have running times $O(k^{O(1)}\cdot
m^{4/3}/\epsilon^{O(1)})$ [KMP12] and $\widetilde{O}(mn/\epsilon^{2})$
[Mad10]; we are not aware of any algorithms that achieve a faster running time
with possibly worse approximation factors, and we are not aware of any fast
algorithms for the Minimum Multicut problem. The best polynomial-time
algorithm for Minimum Multicut, due to [LR99, GVY95], achieves an $O(\log
n)$-approximation.

Before we discuss our results and techniques in more detail, we provide some
additional background on related work.

###  1.1 Other Related Work

#####  APSP on Expanders.

A very interesting special case of the APSP problem is APSP on expanders. In
this problem, we are given an initial graph $G$ that is a $\varphi$-expander.
Graph $G$ undergoes a sequence of edge deletions and isolated vertex
deletions, that arrive in batches. We are guaranteed that, after each such
batch of updates, the resulting graph $G$ remains an
$\Omega(\varphi)$-expander. As in the general APSP problem, the goal is to
support approximate shortest-path-query in graph $G$. This problem is
especially interesting for several reasons. First, it seems to be a relatively
simple special case of the APSP problem, and, if our goal is to obtain better
algorithms for general APSP, solving the problem in expander graphs is a
natural starting step. Second, this problem arises in various algorithms for
_static_ cut and flow problems, and seems to be intimately connected to
efficient implementations of the Cut-Matching game of [KRV09], which is a
central tool in the design of fast algorithms for cut and flow problems (see,
e.g. [CGL+19]). Third, expander graphs are increasingly becoming a central
tool for designing algorithms for various dynamic graph problems, and
obtaining good algorithms for APSP on expanders will likely become a powerful
tool in the toolkit of algorithmic techniques in this area. A recent work of
[CS21], building on [CGL+19], implies a deterministic algorithm for APSP in
expanders with approximation factor $O\left(\Delta^{2}(\log
n)^{O(1/\epsilon^{2})}/\varphi\right)$, query time $O(|E(P)|)$ for shortest-
path-query, where $P$ is the returned path, and total update time
$O\left(n^{1+O(\epsilon)}\Delta^{7}(\log
n)^{O(1/\epsilon^{2})}/\varphi^{5}\right)$; here, $\Delta$ is the maximum
vertex degree of $G$, $\varphi$ is its expansion, and $\epsilon$ is a given
precision parameter444The work of [CS21] only explicitly provides such an
algorithm for a specific setting of the parameter $\epsilon$, but it is easy
to see that the same algorithm works for the whole range of values of
$\epsilon$. We prove this in Theorem 5.3 for completeness.. In fact,
algorithms in this paper also use this algorithm for APSP in expanders as a
subroutine.

##### Single-Source Shortest Paths.

Single-Source Shortest Paths (SSSP) is a special case of APSP, where all
queries must be between a fixed source vertex $s$ and arbitrary other vertices
in the graph $G$. This problem has also been studied extensively. Algorithms
for decremental SSSP are a well-established tool in the design of fast
algorithms for various variants of maximum $s$-$t$ flow and minimum $s$-$t$
cut problems (see, e.g. [Mad10, CK19, CS21]).

In the oblivious-adversary setting, our understanding of the problem is almost
complete: a sequence of works [FHN14b, BR11, FHN14a] has led to a
$(1+\epsilon)$-approximation algorithm, that achieves total update time
$O(m^{1+o(1)}\log L)$, which is close to the best possible. The query time of
the algorithm is also near optimal: query time for dist-query is
$\operatorname{poly}\log n$, and query time for shortest-path-query is
$\tilde{O}(|E(P)|)$, where $P$ is the returned path. Conditional lower bounds
of [DHZ00, RZ11] (that are based on the Boolean Matrix Multiplication
conjecture) and of [HKNS15] (based on the Online Matrix-vector Multiplication
conjecture), show that no algorithm that solves the problem exactly can
simultaneously achieve an $O(n^{1-\delta})$ query time, and $O(n^{3-\delta})$
total update time, for any constant $\delta>0$, in graphs with
$m=\Theta(n^{2})$. The work of Vassilevska Williams and Williams [WW18],
combined with the work of Roddity and Zwick [RZ11], implies that obtaining an
exact algorithm with similar total update time and query time would lead to
subcubic-time algorithms for a number of important static problems on graphs
and matrices. This shows that the above oblivious-update algorithm is likely
close to the best possible.

For the adaptive-update setting, the progress has been slower. It is well
known that the classical ES-Tree data structure of Even and Shiloach [ES81,
Din06, HK95], combined with the standard weight rounding technique (e.g.
[Zwi98, Ber16]) gives a $(1+\epsilon)$-approximate deterministic algorithm for
SSSP with $\tilde{O}(mn\log L)$ total update time and near-optimal query time.
Recently, Bernstein and Chechik [BC16, Ber17, BC17], provided algorithms with
total update time $\tilde{O}(n^{2}\log L)$ and
$\tilde{O}(n^{5/4}\sqrt{m})\leq\tilde{O}(mn^{3/4})$, while Gutenberg and
Wulff-Nielsen [GWN20] showed an algorithm with $O(m^{1+o(1)}\sqrt{n})$ total
update time. Unfortunately, all these algorithms only support distance
queries, and they cannot handle shortest-path queries. This problem was
recently addressed by [CK19, CS21], leading to a deterministic algorithm with
total update time $O(n^{2+o(1)}\log L/\epsilon^{2})$, that achieves a
$(1+\epsilon)$-approximation factor, and has query time $O(|E(P)|\cdot
n^{o(1)}\log\log L)$ for shortest-path-query. Lastly, the work of [BBG+20] on
dynamic spanners also provides a randomized adaptive-update
$(1+\epsilon)$-approximation algorithm with total update time $O(m\sqrt{n})$,
and query time $\tilde{O}(n)$. As mentioned already, they also provide an
algorithm for dynamic spanners, leading to a $\operatorname{poly}\log
n$-approximation algorithm with total update time $O(m\operatorname{poly}\log
n)$ for APSP, and hence for SSSP, with query time $\tilde{O}(n)$. To the best
of our knowledge, our result for the APSP problem is also the first adaptive-
adversary algorithm for SSSP with near-linear total update time, that achieves
an approximation that is below $\Theta(n)$, and query time
$\widetilde{O}(|E(P)|)$ for shortest-path-query. We now discuss our results
and techniques in more detail.

###  1.2 Our Results and Techniques

Our main result is a deterministic algorithm for decremental APSP, that is
summarized in the following theorem.

######  Theorem 1.1.

There is a deterministic algorithm, that, given an $m$-edge graph $G$ with
length $\ell(e)\geq 1$ on its edges, that undergoes an online sequence of edge
deletions, together with a parameter $c/\log\log m<\epsilon<1$ for some large
enough constant $c$, supports approximate shortest-path-query queries and
dist-query queries with approximation factor $O\left((\log
m)^{2^{O(1/\epsilon)}}\right)$. The query time for processing dist-query is
$O(\log m\log\log L)$, and the query time for processing shortest-path-query
is $O(|E(P)|)+O(\log m\log\log L)$, where $P$ is the returned path, and $L$ is
the ratio of longest to shortest edge length. The total update time of the
algorithm is bounded by:

$O\left(m^{1+O(\epsilon)}\cdot(\log m)^{O(1/\epsilon^{2})}\cdot\log L\right).$

Our proof exploits the decremental Sparse Neighborhood Cover problem, for
which we provide the following algorithm:

######  Theorem 1.2.

There is a deterministic algorithm, that, given an $m$-edge graph $G$ with
integral lengths $\ell(e)\geq 1$ on its edges, that undergoes an online
sequence of edge deletions, together with parameters $c/\log\log m<\epsilon<1$
for some large enough constant $c$, and $D\geq 1$, maintains a weak
$(D,\alpha\cdot D)$-neighborhood cover ${\mathcal{C}}$ of $G$, for
$\alpha=O\left((\log m)^{2^{O(1/\epsilon)}}\right)$, and supports queries
$\mbox{\sf{short-path-query}}(C,v,v^{\prime})$: given a cluster
$C\in{\mathcal{C}}$, and two vertices $v,v^{\prime}\in V(C)$, return a path
$P$ connecting $v$ to $v^{\prime}$ in $G$, of length at most $\alpha\cdot D$,
in time $O(|E(P)|)$. Additionally, for every vertex $v\in V(G)$, the algorithm
maintains a cluster $C=\mbox{\sf{CoveringCluster}}(v)$ in ${\mathcal{C}}$,
with $B_{G}(v,D)\subseteq V(C)$. The algorithm starts with
${\mathcal{C}}=\left\\{G\right\\}$, and the only allowed changes to the
clusters in ${\mathcal{C}}$ are: (i) delete an edge from a cluster
$C\in{\mathcal{C}}$; (ii) delete an isolated vertex from a cluster
$C\in{\mathcal{C}}$; and (iii) add a new cluster $C^{\prime}$ to
${\mathcal{C}}$, where $C^{\prime}\subseteq C$ for some cluster
$C\in{\mathcal{C}}$. The algorithm has total update time
$O\left(m^{1+O(\epsilon)}\cdot(\log m)^{O(1/\epsilon^{2})}\right)$ and ensures
that, for every vertex $v\in V(G)$, the total number of clusters
$C\in{\mathcal{C}}$ to which $v$ ever belongs over the course of the algorithm
is at most $m^{O(1/\log\log m)}$.

We remark that the above theorem requires that we initially set
${\mathcal{C}}=\left\\{G\right\\}$. Clearly, this initial cluster set
${\mathcal{C}}$ may not be a valid neighborhood cover of $G$. Therefore,
before the algorithm processes any updates of graph $G$, it may update this
initial cluster set ${\mathcal{C}}$, via changes of the types that are allowed
by the theorem, until it becomes a valid neighborhood cover. We also note that
we allow graphs to have parallel edges, so $m$ may be much larger than
$|V(G)|$.

Lastly, we provide an efficient algorithm for the Minimum Multicut and Maximum
Multicommodity Flow problems in unit-capacity graphs.

######  Theorem 1.3.

There is a deterministic algorithm, that, given an $n$-vertex $m$-edge graph
$G$, a collection
${\mathcal{M}}=\left\\{(s_{1},t_{1}),\ldots,(s_{k},t_{k})\right\\}$ of pairs
of its vertices, called _demand pairs_ , and a precision parameter $c/\log\log
m<\epsilon<1$ for some large enough constant $c$, computes, in time
$\tilde{O}\left(m^{1+O(\epsilon)}(\log
m)^{2^{O(1/\epsilon)}}+k/\epsilon\right)$, a solution to the Maximum
Multicommodity Flow instance $(G,{\mathcal{M}})$, of value at least
$\Omega\left(\mathsf{OPT}_{\mathsf{MCF}}/(\log m)^{2^{O(1/\epsilon)}}\right)$,
and a solution to the Minimum Multicut instance $(G,{\mathcal{M}})$, of cost
at most $O\left((\log
m)^{2^{O(1/\epsilon)}}\cdot\mathsf{OPT}_{\mathsf{MM}}\right)$, where
$\mathsf{OPT}_{\mathsf{MCF}}$ and $\mathsf{OPT}_{\mathsf{MM}}$ are optimal
solution values to instance $(G,{\mathcal{M}})$ of Maximum Multicommodity Flow
and Minimum Multicut, respectively.

The proof of Theorem 1.3 follows immediately from the proof of Theorem 1.2 via
standard techniques; see Section 10 for more details. It is also immediate to
obtain the proof of Theorem 1.1 from Theorem 1.2 using the standard approach
of considering each distance scale separately; see Section 3.4.2 for a formal
proof. We now focus on describing our algorithm for the Neighborhood Cover
problem from Theorem 1.2, introducing our new ideas and techniques one by one.

##### Recursive Dynamic Neighborhood Cover.

As mentioned already, one advantage of considering the Neighborhood Cover
problem is that its solution naturally provides an emulator for the input
graph $G$, which in turn can be used in order to compose algorithms for
Neighborhood Cover recursively. In fact, we initially prove a weaker version
of Theorem 1.2, by providing an algorithm (that we denote here for brevity by
$\operatorname{Alg}^{\prime}$), that achieves a similar approximation factor,
but a slower running time of:

$O\left(m^{1+O(\epsilon)}\cdot\operatorname{poly}(D)\cdot(\log
m)^{O(1/\epsilon^{2})}\right)$

(on the positive side, the algorithm maintains a strong neighborhood cover of
the graph $G$). Recall that we call the parameter $D$ the _target distance
threshold_ for the Neighborhood Cover problem instance. We use the recursive
composability of Neighborhood Cover in order to obtain the desired running
time, as follows555A similar approach of recursive composition of emulators
was used in numerous algorithms for APSP; see, e.g. [Che18].. Using standard
rescaling techniques, we can assume that $1\leq D\leq\Theta(m)$. For all
$1\leq i\leq O(1/\epsilon)$, let $D_{i}=m^{\epsilon i}$. We obtain an
algorithm for the Sparse Neighborhood Cover problem for each target distance
threshold $D_{i}$ recursively. For the base of the recursion, when $i=1$, we
simply run Algorithm $\operatorname{Alg}^{\prime}$, to obtain the desired
running time of $O\left(m^{1+O(\epsilon)}\cdot(\log
m)^{O(1/\epsilon^{2})}\right)$. Assume now that we have obtained an algorithm
for target distance threshold $D_{i}$, that maintains a neighborhood cover
${\mathcal{C}}_{i}$ of graph $G$. In order to obtain an algorithm for target
distance threshold $D_{i+1}$, we construct a new graph $H$, by starting with
$H=G$, deleting all edges of length greater than $D_{i+1}$, and rounding the
lengths of all remaining edges up to the next integral multiple of $D_{i}$.
Additionally, for every cluster $C\in{\mathcal{C}}_{i}$, we add a vertex
$u(C)$ (called a supernode), that connects, with an edge of length $D_{i}$, to
every vertex $v\in V(C)\cap V(G)$. It is not hard to show that this new graph
$H$ approximately preserves all distances between the vertices of $G$, that
are in the range $(D_{i},D_{i+1}]$. Since the length of every edge in $H$ is
an integral multiple of $D_{i}$, scaling all edge lengths down by factor
$D_{i}$ does not change the problem. It is then sufficient to solve the
Neighborhood Cover problem in the resulting dynamic graph $H$, with target
distance threshold $D_{i+1}/D_{i}=m^{\epsilon}$, which can again be done via
Algorithm $\operatorname{Alg}^{\prime}$, with total update time
$O\left(m^{1+O(\epsilon)}\cdot(\log m)^{O(1/\epsilon^{2})}\right)$. The final
algorithm for Theorem 1.2 is then obtained by recursively composing Algorithm
$\operatorname{Alg}^{\prime}$ with itself $O(1/\epsilon)$ times.

In order to be able to compose algorithms for the Neighborhood Cover problem
using the above approach, we define the problem slightly differently, and we
call the resulting variation of the problem Recursive Dynamic Neighborhood
Cover, or $\mathsf{RecDynNC}$. We assume that the input is a bipartite graph
$H=(V,U,E)$, with non-negative edge lengths. Intuitively, the vertices in set
$V$, that we refer to as _regular vertices_ , correspond to vertices of the
original graph $G$, while the vertices in set $U$, that we call _supernodes_ ,
represent some neighborhood cover ${\mathcal{C}}$ of the graph $G$ that is
possibly maintained recursively: $U=\left\\{u(C)\mid
C\in{\mathcal{C}}\right\\}$. (In order to obtain the initial graph $H$, we
subdivide every edge of $G$ by a new regular vertex; we view the original
vertices of $G$ as supernodes; and for every vertex $v\in V(G)$, we add a new
regular vertex $v^{\prime}$ that connects to $v$ with a length-$1$ edge.) In
addition to supporting standard edge-deletion and isolated vertex-deletion
updates, we require that the algorithm for the $\mathsf{RecDynNC}$ problem
supports a new update operation, that we call _supernode splitting_ 666We note
that a similar approach to handling cluster-splitting in an emulator that is
based on clustering was used before in numerous works, including, e.g., [BC16,
Ber17, CK19, CZ20].. In this operation, we are given a supernode $u\in V(H)$,
and a subset $E^{\prime}$ of edges that are incident to $u$ in graph $H$. The
update creates a new supernode $u^{\prime}$ in graph $H$, and, for every edge
$e=(u,v)\in E^{\prime}$, adds a new edge $(u^{\prime},v)$ of length $\ell(e)$
to $H$. The purpose of this update operation is to mimic the addition of a new
cluster $C$ to ${\mathcal{C}}$, where $C\subseteq C^{\prime}$ for some
existing cluster $C^{\prime}\in{\mathcal{C}}$. The supernode-splitting
operation is applied to supernode $u(C^{\prime})$, with edge set $E^{\prime}$
containing all edges $(v,u(C^{\prime}))$ with $v\in V(C)$, and the operation
creates a new supernode $u(C)$. Supernode-splitting operation, however, may
insert some new edges into the graph $H$. This creates several difficulties,
especially in bounding total update times in terms of number of edges. We get
around this problem as follows. Recall that the supernodes in set $U$
generally correspond to clusters in some dynamic neighborhood cover
${\mathcal{C}}$, that we maintain recursively. We ensure that this
neighborhood cover is sparse, that is, every regular vertex may only belong to
a small number of such clusters (typically, at most $m^{1/O(\log\log m)}$).
This in turn ensures that, in graph $H$, for every regular vertex $v\in V(H)$,
the total number of edges incident to $v$ that ever belong to $H$ is also
bounded by $m^{1/O(\log\log m)}$. We refer to this bound as the _dynamic
degree bound_ , and denote it by $\mu$. Therefore, if we denote by $N(H)$ the
number of regular vertices that belong to the initial graph $H$, then the
total number of edges that ever belong to $H$ is bounded by $N(H)\cdot\mu$.
This allows us to use the number of regular vertices of $H$ as a proxy to
bounding the number of edges in $H$.

To summarize, the definition of the $\mathsf{RecDynNC}$ problem is almost
identical to that of the Sparse Neighborhood Cover problem. The main
difference is that the input graph now has a specific structure (that is, it
is a bipartite graph), and, in addition to edge-deletions, we also need to
support isolated vertex deletions and supernode-splitting updates. Additional
minor difference is that we only require that the covering properties of the
neighborhood cover hold for the regular vertices of $H$ (and not necessarily
the supernodes), and we only bound the number of clusters ever containing a
vertex for regular vertices (and not supernodes). These are minor technical
details that are immaterial to this high-level overview.

##### Procedure $\mathsf{ProcCut}$ and reduction to the
$\mathsf{MaintainCluster}$ problem.

One of the main building blocks of our algorithm is Procedure
$\mathsf{ProcCut}$. Suppose our goal is to design an algorithm for the
$\mathsf{RecDynNC}$ problem on input graph $H$, with target distance threshold
$D$, and let ${\mathcal{C}}$ be the neighborhood cover that we maintain. We
denote by $N$ the number of regular vertices in the initial graph $H$, and,
for each subgraph $H^{\prime}\subseteq H$, we denote by $N(H^{\prime})$ the
number of regular vertices in $H^{\prime}$. Given a cluster
$C\in{\mathcal{C}}$, and two vertices $x,y\in C$, such that $\mbox{\sf
dist}_{C}(x,y)>\Omega(D\operatorname{poly}\log N)$, procedure
$\mathsf{ProcCut}$ produces two vertex-induced subgraphs
$C^{\prime},C^{\prime\prime}\subseteq C$, such that $N(C^{\prime})\leq
N(C^{\prime\prime})$, $\mbox{\sf diam}(C^{\prime})\leq
O(D\operatorname{poly}\log N)$, and each of $C^{\prime},C^{\prime\prime}$
contains exactly one of the two vertices $x,y$. Moreover, it guarantees that,
for every vertex $v\in V(C)$, either $B_{C}(v,D)\subseteq C^{\prime}$, or
$B_{C}(v,D)\subseteq C^{\prime\prime}$ holds. We then add $C^{\prime}$ to
${\mathcal{C}}$, and update $C$ by deleting edges and vertices from it, until
$C=C^{\prime\prime}$ holds. This procedure is exploited by our algorithm in
two ways: first, we compute an initial strong
$(D,D\cdot\operatorname{poly}\log N)$-neighborhood cover ${\mathcal{C}}$ of
the input graph $H$, before it undergoes any updates, by repeatedly invoking
this procedure. Later, as the algorithm progresses, and update operations are
applied to $H$, the diameters of some clusters $C\in{\mathcal{C}}$ may grow.
Whenever we identify such a situation, we use Procedure $\mathsf{ProcCut}$ in
order to cut the cluster $C$ into smaller subclusters. We note that, if
$C^{\prime}$ and $C^{\prime\prime}$ are the outcome of applying Procedure
$\mathsf{ProcCut}$ to cluster $C$, then we cannot guarantee that the two
clusters are disjoint, so they may share edges and vertices. Therefore, a
vertex of $H$ may belong to a number of clusters in ${\mathcal{C}}$. The main
challenge in designing Procedure $\mathsf{ProcCut}$ is to ensure that every
vertex of $H$ only belongs to a small number of clusters (at most
$N^{O(1/\log\log N)}$) over the course of the entire algorithm. The procedure
uses a carefully designed modification of the ball-growing technique of [LR99]
that allows us to ensure this property. We note that several previous works
used the ball-growing technique in order to compute and maintain a clustering
of a graph. For example, [CZ20] employ this technique in order to maintain
clustering at every distance scale. However, the clusters that they maintain
at each distance scale are disjoint, and so they can use the standard ball-
growing procedure of [LR99] in order to ensure that relatively few edges have
endpoints in different clusters. In contrast, in order to maintain a
neighborhood cover, we need to allow clusters at each distance scale to
overlap. While one can easily adapt the standard ball-growing procedure of
[LR99] to still ensure that the total number of edges in the resulting
clusters is sufficiently small, this would only ensure that every vertex
belongs to relatively few clusters on average. It is the strict requirement
that every vertex may only ever belong to few clusters in the neighborhood
cover that makes the design of Procedure $\mathsf{ProcCut}$ challenging. We
are not aware of any other work that adapted the ball-growing technique to
this type of requirement, except for the algorithm of [AP90, ABCP98], who did
so in the static setting. It is unclear though how to adapt their techniques
to the dynamic setting.

We also use Procedure $\mathsf{ProcCut}$ to reduce the $\mathsf{RecDynNC}$
problem to a new problem, that we call $\mathsf{MaintainCluster}$. In this
problem, we are given some cluster $C$ that was just added to the neighborhood
cover ${\mathcal{C}}$. The goal is to support queries $\mbox{\sf{short-path-
query}}(C,v,v^{\prime})$: given a pair $v,v^{\prime}\in V(C)$ of vertices of
$C$, return a path $P$ connecting $v$ to $v^{\prime}$ in $C$, of length at
most $\alpha\cdot D$, in time $O(|E(P)|)$. However, the algorithm may, at any
time, raise a flag $F_{C}$, to indicate that the diameter of $C$ has become
too large. When flag $F_{C}$ is raised, the algorithm must provide two
vertices $x,y\in C$, with $\mbox{\sf
dist}_{C}{(x,y)}>\Omega(D\operatorname{poly}\log N)$. The algorithm then
obtains a sequence of update operations (that we call a _flag-lowering
sequence_), at the end of which either $x$ or $y$ are deleted from $C$, and
flag $F_{C}$ is lowered. Queries short-path-query may only be asked when the
flag $F_{C}$ is down. Once flag $F_{C}$ is lowered, the algorithm may raise it
again immediately, as long as it supplies a new pair $x^{\prime},y^{\prime}\in
V(C)$ of vertices with $\mbox{\sf
dist}_{C}{(x^{\prime},y^{\prime})}>\Omega(D\operatorname{poly}\log N)$.
Intuitively, once flag $F_{C}$ is raised, we will simply run Procedure
$\mathsf{ProcCut}$ on cluster $C$, with the vertices $x,y$ supplied by the
algorithm, and obtain two new clusters $C^{\prime}$, $C^{\prime\prime}$.
Assume that $C^{\prime}$ contains fewer regular vertices than
$C^{\prime\prime}$. We then add $C^{\prime}$ to ${\mathcal{C}}$, and delete
edges and vertices from $C$ until $C=C^{\prime\prime}$ holds, thus creating a
flag-lowering update sequence for it. In order to obtain an algorithm for the
$\mathsf{RecDynNC}$ problem, it is then enough to obtain an algorithm for the
$\mathsf{MaintainCluster}$ problem. We focus on this problem in the remainder
of this exposition.

##### Pseudocuts, expanders, and their embeddings.

The next central tool that we introduce is balanced pseudocuts. Consider a
cluster $C$, for which we would like to solve the $\mathsf{MaintainCluster}$
problem, as $C$ undergoes a sequence of online updates, with target distance
threshold $D$. For a given balance parameter $\rho$, a standard balanced
multicut for $C$ can be defined as a set $E^{\prime}\subseteq E(C)$ of edges,
such that every connected component of $C\setminus E^{\prime}$ contains at
most $N(C)/\rho$ regular vertices. We weaken this notion of balanced multicut,
and use instead _balanced pseudocuts_. Let
$D^{\prime}=\Theta(D\operatorname{poly}\log N)$. A
$(D^{\prime},\rho)$-pseudocut in cluster $C$ is a collection $E^{\prime}$ of
its edges, such that, in graph $C\setminus E^{\prime}$, for every vertex $v\in
V(C)$, the ball $B_{C\setminus E^{\prime}}(v,D^{\prime})$ contains at most
$N(C)/\rho$ regular vertices. In particular, once all edges of $E^{\prime}$
are deleted from $C$, if we compute a strong $(D,D^{\prime})$-neighborhood
cover ${\mathcal{C}}^{\prime}$ of $C$, then we are guaranteed that for all
$C^{\prime}\in{\mathcal{C}}^{\prime}$, $N(C^{\prime})\leq N(C)/\rho$. We note
that standard balanced multicuts also achieve this useful property. An
advantage of using pseudocuts is that we can design a near-linear time
algorithm that computes a $(D^{\prime},\rho)$-pseudocut $E^{\prime}$ in graph
$C$, for $\rho=N^{\epsilon}$, and additionally it computes an expander $X$,
whose vertex set is $\left\\{v_{e}\mid e\in E^{\prime\prime}\right\\}$, where
$E^{\prime\prime}\subseteq E^{\prime}$ is a large subset of the edges of
$E^{\prime}$, together with an embedding of $X$ into $C$, via short embedding
paths, that causes a low edge-congestion (see Theorem 5.1 for details). This
allows us to build on known expander-based techniques in order to design an
efficient algorithm for the $\mathsf{MaintainCluster}$ problem. Consider the
following algorithm, that consists of a number of phases. In every phase, we
start by computing a $(D^{\prime},\rho)$-pseudocut $E^{\prime}$ of $C$, the
corresponding expander $X$, and its embedding into $C$. Let
$E^{\prime\prime}\subseteq E^{\prime}$ be the set of edges $e$, whose
corresponding vertex $v_{e}$ lies in the expander $X$, so
$V(X)=\left\\{v_{e}\mid e\in E^{\prime\prime}\right\\}$. We then use two data
structures. The first data structure is an ES-Tree $\tau$, whose root $s$ is a
new vertex, that connects to each endpoint of every edge in
$E^{\prime\prime}$, and has depth $O(D\operatorname{poly}\log N)$. This data
structure allows us to ensure that every vertex of $C$ is close enough to some
edge of $E^{\prime\prime}$, and to identify when this is no longer the case,
so that flag $F_{C}$ is raised. Additionally, we use known algorithms for APSP
on expanders, together with the algorithm of [SW19] for expander pruning, in
order to maintain the expander $X$ (under update operations performed on the
cluster $C$), and its embedding into $C$. This allows us to ensure that all
edges in $E^{\prime\prime}$ remain sufficiently close to each other. These two
data structures are sufficient in order to support the $\mbox{\sf{short-path-
query}}(C,v,v^{\prime})$ queries. If the initial pseudocut $E^{\prime}$ was
sufficiently large, then these data structures can be maintained over a long
enough sequence of update operations to cluster $C$. Once a large enough
number of edges are deleted from $C$, expander $X$ can no longer be
maintained, and we recompute the whole data structure from scratch. Therefore,
as long as the pseudocut $E^{\prime}$ that our algorithm computes is
sufficiently large (for example, its cardinality is at least
$(N(C))^{1-\epsilon}$), we can support the $\mbox{\sf{short-path-
query}}(C,v,v^{\prime})$ queries as needed, with a very efficient algorithm.

It now remains to deal with the situation where the size of the pseudocut
$E^{\prime}$ is small. One simple way to handle it is to maintain
$2|E^{\prime}|$ ES-Tree data structures, each of which is rooted at an
endpoint of a distinct edge of $E^{\prime}$, and has depth threshold
$\Theta(D\operatorname{poly}\log N)$. As long as the root vertex of an ES-Tree
$\tau$ remains in the current cluster $C$, we say that the tree $\tau$
_survives_. As long as at least one of the ES-Trees rooted at the endpoints of
the edges in $E^{\prime}$ survives, we can support the $\mbox{\sf{short-path-
query}}(C,v,v^{\prime})$ queries using any such tree. We can also use such a
tree in order to detect when the diameter of the cluster becomes too large,
and, when this happens, to identify a pair $x,y$ of vertices of $C$ with
$\mbox{\sf dist}_{C}(x,y)$ sufficiently large. Once every ES-Tree that we
maintain is destroyed, we are guaranteed that all edges of $E^{\prime}$ are
deleted from $C$. We can then iteratively apply Procedure $\mathsf{ProcCut}$
in order to further decompose $C$ into a collection of low-diameter clusters
(that is, we compute a collection ${\mathcal{C}}^{\prime}$ of subgraphs of
$C$, such that ${\mathcal{C}}^{\prime}$ is a $(D,D^{\prime})$-neighborhood
cover for $C$). Since $E^{\prime}$ was a $(D^{\prime},\rho)$-pseudocut for the
original cluster $C$, we are then guaranteed that every cluster in
${\mathcal{C}}^{\prime}$ is significantly smaller than $C$, and contains at
most $N(C)/\rho$ regular vertices. We can then initialize the algorithm for
solving the $\mathsf{MaintainCluster}$ problem on each cluster of
${\mathcal{C}}^{\prime}$. This approach already gives non-trivial guarantees
(though in order to optimize it, we should choose a different threshold for
the cardinality of $E^{\prime}$: if $|E^{\prime}|>\sqrt{N(C)}$, we should use
the expander-based approach, and otherwise we should maintain the ES-Tree’s).
Our rough estimate is that such an algorithm would result in total update time
$O\left(m^{1.5+O(\epsilon)}\cdot(\log m)^{O(1/\epsilon^{2})}\right)$, but it
is still much higher than our desired update time.

In order to achieve our desired near-linear total update time, we exploit
again the recursive composability properties of the $\mathsf{RecDynNC}$
problem. Specifically, consider the situation where the pseudocut $E^{\prime}$
that we have computed is small, that is, $|E^{\prime}|<(N(C))^{1-\epsilon}$,
and consider the graph $H^{\prime}=C\setminus E^{\prime}$. For all $1\leq
i\leq\left\lceil\log D\right\rceil$, we solve the $\mathsf{RecDynNC}$ problem
in graph $H^{\prime}$ with target distance threshold $D_{i}=2^{i}$
recursively. Fix some index $1\leq i\leq\left\lceil\log D\right\rceil$, and
let ${\mathcal{C}}_{i}$ be the initial strong
$(D_{i},D_{i}\cdot\operatorname{poly}\log N)$-neighborhood cover that this
algorithm computes. The properties of the balanced pseudocut ensure that each
cluster $C^{\prime}\in{\mathcal{C}}_{i}$ is significantly smaller that $C$:
namely, $N(C^{\prime})\leq N(C)/\rho\leq(N(C))^{1-\epsilon}$. Therefore, we
can solve the $\mathsf{MaintainCluster}$ problem on each such cluster
recursively, and we also do so for every cluster that is later added to
${\mathcal{C}}_{i}$. Let $\tilde{\mathcal{C}}=\bigcup_{i}{\mathcal{C}}_{i}$ be
the dynamic collection of clusters that we maintain.

We use the set $\tilde{\mathcal{C}}$ of clusters in order to construct a
_contracted graph_ $\hat{H}$. The vertex set of $\hat{H}$ consists of the set
$S$ of regular vertices – all regular vertices that serve as endpoints of the
edges of $E^{\prime}$ (the edges of the pseudo-cut); and the set
$U^{\prime}=\left\\{u(C^{\prime})\mid
C^{\prime}\in\tilde{\mathcal{C}}\right\\}$ of supernodes. For every edge
$e=(u,v)\in E^{\prime}$, where $v\in S$ is a regular vertex, we add an edge
connecting $v$ to every supernode $u(C^{\prime})$, such that cluster
$C^{\prime}$ contains either $v$ or $u$. The length of the edge is $D_{i}$,
where $i$ is the index for which $C^{\prime}\in{\mathcal{C}}_{i}$ holds. It is
not hard to show that the distances between the vertices of $S$ are
approximately preserved in graph $\hat{H}$. As cluster $C$ undergoes a
sequence of update operations, the neighborhood covers ${\mathcal{C}}_{i}$
evolve, which in turn leads to changes in the contracted graph $\hat{H}$.
However, we ensure that all changes to the neighborhood covers
${\mathcal{C}}_{i}$ are only of the types allowed by Theorem 1.2, namely: (i)
delete an edge from a cluster of ${\mathcal{C}}_{i}$; (ii) delete an isolated
vertex from a cluster of ${\mathcal{C}}_{i}$; or (iii) add a new cluster
$C^{\prime\prime}$ to ${\mathcal{C}}_{i}$, where $C^{\prime\prime}\subseteq
C^{\prime}$ for some cluster $C^{\prime}\in{\mathcal{C}}_{i}$. We are then
guaranteed that all resulting changes to graph $\hat{H}$ can be implemented
via allowed update operations: namely edge deletions, isolated vertex
deletions, and supernode splitting.

We construct two data structures. First, an ES-Tree $\tau$, in the graph
obtained from $C$ by adding a new source vertex $s^{*}$, that connects to
every vertex in $S$ with a length-$1$ edge. The depth of the tree is
$O(D\operatorname{poly}\log N)$. This data structure allows us to ensure that
every vertex of $C$ is sufficiently close to some vertex of $S$, and, when
this is no longer the case, to raise the flag $F_{C}$, and to supply two
vertices $x,y\in V(C)$ that are sufficiently far from each other.

The second data structure is obtained by applying the algorithm for the
$\mathsf{MaintainCluster}$ problem recursively to the contracted graph
$\hat{H}$. This data structure allows us to ensure that all vertices of $S$
are sufficiently close to each other, and, when this is no longer the case, it
supplies a pair of vertices $s,s^{\prime}\in S$, that are sufficiently far
from each other in $\hat{H}$, and hence in $C$. Since we only use this
algorithm in the scenario where $|E^{\prime}|\leq(N(C))^{1-\epsilon}$, we are
guaranteed that $|S|\leq(N(C))^{1-\epsilon}$, so graph $\hat{H}$ is
significantly smaller than $C$.

To summarize, in order to solve the $\mathsf{MaintainCluster}$ problem in
graph $C$, we use an expander-based approach, as long as the size of the
pseudocut $E^{\prime}$ that our algorithm computes is above
$(N(C))^{1-\epsilon}$. Once this is no longer the case, we recursively solve
the problem on clusters that are added to the neighborhood covers
${\mathcal{C}}_{i}$ of graph $H=C\setminus E^{\prime}$, for $1\leq
i\leq\left\lceil\log D\right\rceil$. This allows us to maintain the
neighborhood covers $\left\\{{\mathcal{C}}_{i}\right\\}$, which, in turn,
allow us to maintain the contracted graph $\hat{H}$. We then solve the
$\mathsf{MaintainCluster}$ problem recursively on the contracted graph
$\hat{H}$. Once all edges of $E^{\prime}$ are deleted from $C$, we start the
whole algorithm from scratch. Since we ensure that the diameter of $C$ is
bounded by $D^{\prime}$, from the definition of a balanced pseudocut, we are
guaranteed that $N(C)$ has decreased by at least a factor $N^{\epsilon}$.

##### Directions for future improvements.

A major remaining open question is whether we can obtain an algorithm for
decremental APSP with a significantly better approximation factor, while
preserving the near-linear total update time and the near-optimal query time.
While it seems plausible that the new tools presented in this paper may lead
to an improved $(\log m)^{\operatorname{poly}(1/\epsilon)}$-approximation
algorithm with similar running time guarantees, improving the approximation
factor beyond the $(\log m)^{\operatorname{poly}(1/\epsilon)}$ barrier seems
quite challenging. A necessary first step toward such an improvement is to
obtain better approximation algorithms for the decremental APSP problem on
expanders. We believe that this is a very interesting problem in its own
right, and it is likely that better algorithms for this problem will lead to
better deterministic algorithms for basic cut and flow problems, including
Minimum Balanced Cut and Sparsest Cut, via the techniques of [CGL+19]. This,
however, is not the only barrier to obtaining an approximation factor below
$(\log m)^{\operatorname{poly}(1/\epsilon)}$ for decremental APSP in near-
linear time. In order to bring the running time of the algorithm for the
$\mathsf{RecDynNC}$ problem down from
$O\left(m^{1+O(\epsilon)}\cdot\operatorname{poly}(D)\cdot(\log
m)^{O(1/\epsilon^{2})}\right)$ to the desired running time of
$O\left(m^{1+O(\epsilon)}\cdot(\log m)^{O(1/\epsilon^{2})}\right)$, we
recursively compose instances of $\mathsf{RecDynNC}$ with each other. This
leads to recursion depth $O(1/\epsilon)$, and unfortunately the approximation
factor accumulates with each recursive level. If the running time of our basic
algorithm for $\mathsf{RecDynNC}$ (see Theorem 3.3) can be improved to depend
linearly instead of cubically on $D$, it seems conceivable that one could use
the approach of [BC16, Ber17], together with Layered Core Decomposition of
[CS21] in order to avoid this recursion (though it is likely that, in the
running time of the resulting algorithm, term $m^{1+O(\epsilon)}$ will be
replaced with $n^{2+O(\epsilon)}$). Lastly, our algorithm for the
$\mathsf{MaintainCluster}$ problem needs to call to itself recursively on the
contracted graph $\hat{H}$, which again leads to a recursion of depth
$O(1/\epsilon)$, with the approximation factor accumulating at each recursive
level. One possible direction for reducing the number of the recursive levels
is designing an algorithm for computing a pseudocut $E^{\prime}$, its
corresponding expander $X$, and an embedding of $X$ into the cluster $C$ with
a better balance parameter $\rho$ (see Theorem 5.1). We believe that obtaining
an analogue of Theorem 5.1 with stronger parameters and faster running time is
a problem of independent interest.

###  1.3 Organization

Most of this paper focuses on the proof of Theorem 1.2. We start with
preliminaries in Section 2, and then define the Recursive Dynamic Neighborhood
Cover problem ($\mathsf{RecDynNC}$), and state our main result for it in
Section 3. We also show in Section 3 that the proofs of Theorem 1.1 and
Theorem 1.2 follow from this result. After that, we gradually introduce our
new technical tools. In Section 4 we describe and analyze Procedure
$\mathsf{ProcCut}$, and use it in order to reduce the $\mathsf{RecDynNC}$
problem to a new problem that we define in the same section, called
$\mathsf{MaintainCluster}$. In the same section, we show a slow and simple
algorithm for the $\mathsf{MaintainCluster}$ problem, that we will use as a
recursion base. In Section 5 we define balanced pseudocuts, and provide our
main algorithm for them, that allows us to compute a pseudocut in a given
cluster $C$, together with the corresponding expander $X$, and its embedding
into $C$. We also provide an algorithm for APSP on expanders, that is implicit
in [CS21]. Lastly, we show that these new tools already lead to a somewhat
faster algorithm for the $\mathsf{MaintainCluster}$ problem. In Section 6 we
define good clusters; intuitively, these are clusters on which we can solve
the $\mathsf{MaintainCluster}$ problem using the tools that we have developed
so far, and we provide an algorithm that does exactly that. We then define a
contracted graph and analyze its properties in Section 7, and we complete the
algorithm for the $\mathsf{MaintainCluster}$ problem, by combining all tools
that we have introduced, in Section 8. This completes the proof of Theorem 1.1
and Theorem 1.2. In Section 9 we summarize all main parameters used in the
proof. Lastly, in Section 10 we provide our algorithm for Maximum
Multicommodity Flow and Minimum Multicut, proving Theorem 1.3.

##  2 Preliminaries

All logarithms in this paper are to the base of $2$. All graphs in this paper
are undirected. Graphs may have parallel edges, except for simple graphs, that
cannot have them. Throughout the paper, we use a $\tilde{O}(\cdot)$ notation
to hide multiplicative factors that are polynomial in $\log m$ and $\log n$,
where $m$ and $n$ are the number of edges and vertices, respectively, in the
initial input graph.

We follow standard graph-theoretic notation. Given a graph $G=(V,E)$ and two
disjoint subsets $A,B$ of its vertices, we denote by $E_{G}(A,B)$ the set of
all edges with one endpoint in $A$ and another in $B$, and by $E_{G}(A)$ the
set of all edges with both endpoints in $A$. We also denote by $\delta_{G}(A)$
the set of all edges with exactly one endpoint in $A$. For a vertex $v\in
V(G)$, we denote by $\delta_{G}(v)$ the set of all edges incident to $v$ in
$G$, and by $\deg_{G}(v)$ the degree of $v$ in $G$. We may omit the subscript
$G$ when clear from context. Given a subset $S\subseteq V$ of vertices of $G$,
we denote by $G[S]$ the subgraph of $G$ induced by $S$.

Given a graph $G$ and a weight function $w:V(G)\rightarrow{\mathbb{R}}$ on its
vertices, for a subset $V^{\prime}\subseteq V(G)$ of its vertices, we denote
by $W(V^{\prime})=\sum_{v\in V^{\prime}}w(v^{\prime})$ the total weight of all
vertices in $V^{\prime}$. Abusing the notation, for a subgraph $C\subseteq G$,
we denote the weight of the subgraph $W(C)=\sum_{v\in V(C)}w(v)$.

Given a graph $G$ with lengths $\ell(e)\geq 0$ on edges $e\in E(G)$, for a
pair of vertices $u,v\in V(G)$, we denote by $\mbox{\sf dist}_{G}(u,v)$ the
_distance_ between $u$ and $v$ in $G$, that is, the length of the shortest
path between $u$ and $v$ with respect to the edge lengths $\ell(e)$. For a
pair $S,T$ of subsets of vertices of $G$, we define the distance between $S$
and $T$ to be $\mbox{\sf dist}_{G}(S,T)=\min_{s\in S,t\in T}\mbox{\sf
dist}_{G}(s,t)$. For a vertex $v\in V(G)$, and a vertex subset $S\subseteq
V(G)$, we also define the distance between $v$ and $S$ as $\mbox{\sf
dist}_{G}(v,S)=\min_{u\in S}\mbox{\sf dist}_{G}(v,u)$. The _diameter_ of the
graph $G$, denoted by $\mbox{\sf diam}(G)$, is the maximum distance between
any pair of vertices in $G$. For a path $P$ in $G$, we denote its length by
$\ell_{G}(P)=\sum_{e\in E(P)}\ell(e)$. For a vertex $v\in V(G)$ and a distance
parameter $D\geq 0$, we denote by $B_{G}(v,D)=\left\\{u\in V(G)\mid\mbox{\sf
dist}_{G}(u,v)\leq D\right\\}$ the _ball of radius $D$ around $v$_. Similarly,
for a vertex subset $S\subseteq V(G)$, we let the ball of radius $D$ around
$S$ be $B_{G}(S,D)=\left\\{u\in V(G)\mid\mbox{\sf dist}_{G}(u,S)\leq
D\right\\}$. We will sometimes omit the subscript $G$ when clear from context.

##### Neighborhood Covers.

Neighborhood Cover is a central notion that we use throughout the paper. We
use both a strong and a weak notion of neighborhood covers, that are defined
as follows.

######  Definition (Neighborhood Cover).

Let $G$ be a graph with lengths $\ell(e)>0$ on edges $e\in E(G)$, let
$S\subseteq V(G)$ be a subset of its vertices, and let $D\leq D^{\prime}$ be
two distance parameters. A _weak $(D,D^{\prime})$-neighborhood cover_ for
vertex set $S$ in $G$ is a collection
${\mathcal{C}}=\left\\{C_{1},\ldots,C_{r}\right\\}$ of vertex-induced
subgraphs of $G$ called _clusters_ , such that:

  * •

for every vertex $v\in S$, there is some index $1\leq i\leq r$ with
$B_{G}(v,D)\subseteq V(C_{i})$; and

  * •

for all $1\leq i\leq r$, for every pair $s,s^{\prime}\in S\cap V(C_{i})$ of
vertices, $\mbox{\sf dist}_{G}(s,s^{\prime})\leq D^{\prime}$.

A set ${\mathcal{C}}$ of subgraphs of $G$ is a _strong
$(D,D^{\prime})$-neighborhood cover_ for vertex set $S$ if it is a weak
$(D,D^{\prime})$-neighborhood cover for $S$, and, additionally, for every
cluster $C\in{\mathcal{C}}$, for every pair $s,s^{\prime}\in S\cap V(C)$ of
vertices, $\mbox{\sf dist}_{C}(s,s^{\prime})\leq D^{\prime}$.

If the vertex set $S$ is not specified, then we assume that $S=V(G)$.

##### Dynamic Graphs.

Throughout, we consider a graph $G$ that undergoes an online sequence
$\Sigma=(\sigma_{1},\sigma_{2},\ldots)$ of update operations. For now it may
be convenient to think of the update operations being edge deletions, though
we will consider additional update operations later. After each update
operation (e.g. edge deletion), our algorithm will perform some updates to the
data structure. We refer to different “times” during the algorithm’s
execution. The algorithm starts at time $0$. For each $t\geq 0$, we refer to
“time $t$ in the algorithm’s execution” as the time immediately after all
updates to the data structures maintained by the algorithm following the $t$th
update $\sigma_{t}\in\Sigma$ are completed. When we say that some property
holds at every time in the algorithm’s execution, we mean that the property
holds at all times $t$ of the algorithm’s execution, but it may not hold, for
example, during the procedure that updates the data structures maintained by
the algorithm, following some input update operation $\sigma_{t}\in\Sigma$.
For $t\geq 0$, we denote by $G^{t}$ the graph $G$ at time $t$; that is,
$G^{0}$ is the original graph, and for $t\geq 0$, $G^{t}$ is the graph
obtained from $G$ after the first $t$ update operations
$\sigma_{1},\ldots,\sigma_{t}$.

##### Even-Shiloach Trees [ES81, Din06, HK95].

Suppose we are given a graph $G=(V,E)$ with integral lengths $\ell(e)\geq 1$
on its edges $e\in E$, a source $s$, and a distance bound $D\geq 1$. Even-
Shiloach Tree (ES-Tree) algorithm maintains, for every vertex $v$ with
$\mbox{\sf dist}_{G}(s,v)\leq D$, the distance $\mbox{\sf dist}_{G}(s,v)$,
under the deletion of edges from $G$. Moreover, it maintains a shortest-path
tree $\tau$ rooted at vertex $s$, that includes all vertices $v$ with
$\mbox{\sf dist}_{G}(s,v)\leq D$. We denote the corresponding data structure
by $\mbox{\sf{ES-Tree}}(G,s,D)$. The total running time of the algorithm,
including the initialization and all edge deletions, is $O(m\cdot D\log n)$,
where $m$ is the initial number of edges in $G$ and $n=|V|$. Throughout this
paper, we refer to the corresponding data structure as _basic ES-Tree_. We
later define a slight generalization of this data structure that allows us to
handle some additional update operations. This more general data structure
will be referred to as _generalized ES-Tree_.

##### Cuts, Sparsity and Expanders.

Given a graph $G$, a _cut_ in $G$ is a bipartition $(A,B)$ of the set $V(G)$
of its vertices, with $A,B\neq\emptyset$. The _sparsity_ of the cut $(A,B)$ is
$\varphi_{G}(A,B)=\frac{|E_{G}(A,B)|}{\min\left\\{|A|,|B|\right\\}}$. We
denote by $\Phi(G)$ the smallest sparsity of any cut in $G$, and we refer to
$\Phi(G)$ as the _expansion_ of $G$.

######  Definition (Expander).

We say that a graph $G$ is a $\varphi$-expander iff $\Phi(G)\geq\varphi$.

We will repeatedly use the following standard observation, whose proof is
included in Section A.1 of Appendix for completeness.

######  Observation 2.1.

Let $G$ be an $n$-vertex $\varphi$-expander with maximum vertex degree at most
$\Delta$. Then for any pair $u,v$ of vertices of $G$, there is a path
connecting $u$ to $v$ that contains at most $\frac{8\Delta\log n}{\varphi}$
edges.

##### Expander Pruning.

We use an algorithm for expander pruning by [SW19]. We slightly rephrase it so
it is defined in terms of graph expansion, instead of conductance that was
used in the original paper. For completeness, we include the proof in Section
A.2 of Appendix.

######  Theorem 2.2 (Adaptation of Theorem 1.3 in [SW19]).

There is a deterministic algorithm, that, given an access to the adjacency
list of a graph $G=(V,E)$ that is a $\varphi$-expander, for some parameter
$0<\varphi<1$, such that the maximum vertex degree in $G$ is at most $\Delta$,
and a sequence $\Sigma=(e_{1},e_{2},\ldots,e_{k})$ of
${k\leq\varphi|E|/(10\Delta)}$ online edge deletions from $G$, maintains a
vertex set $S\subseteq V$ with the following properties. Let $G^{i}$ denote
the graph $G\setminus\left\\{e_{1},\ldots,e_{i}\right\\}$; let
$S_{0}=\emptyset$ be the set $S$ at the beginning of the algorithm, and for
all $0<i\leq k$, let $S_{i}$ be the set $S$ after the deletion of the edges of
$e_{1},\ldots,e_{i}$ from graph $G$. Then, for all $1\leq i\leq k$:

  * •

$S_{i-1}\subseteq S_{i}$;

  * •

$|S_{i}|\leq 8i\Delta/\varphi$;

  * •

$|E(S_{i},V\setminus S_{i})|\leq 4i$; and

  * •

graph $G^{i}[V\setminus S_{i}]$ is a $\varphi/(6\Delta)$-expander.

The total running time of the algorithm is
$\widetilde{O}(k\Delta^{2}/\varphi^{2})$.

##  3 Valid Input Structure, Valid Update Operations, Generalized Even-
Shiloach Trees, and the Dynamic Recursive Neighborhood Cover Problem

Throughout this paper, we will work with inputs that have a specific
structure. The structure is designed in a way that will allow us to naturally
compose different instances recursively, by exploiting the notion of
neighborhood covers. In order to avoid repeatedly defining such inputs, we
provide a definition here, and then refer to it throughout the paper. In this
section we also define the types of update operations that we allow for such
inputs, and extend the basic Even-Shiloach Tree data structure to support such
updates. Lastly, we formally define the Recursive Dynamic Neighborhood Cover
problem ($\mathsf{RecDynNC}$) and state our main result for this problem. We
then show that this result immediately implies the proofs of Theorems 1.1 and
1.2.

###  3.1 Valid Input Structure and Valid Update Operations

We start by defining a valid input structure; the definition is used
throughout the paper and is intended as a shorthand for the types of inputs
most our subroutines use.

######  Definition (Valid Input Structure).

A valid input structure consists of a bipartite graph $H=(V,U,E)$, a distance
threshold $D>0$ and integral lengths $1\leq\ell(e)\leq D$ for edges $e\in E$.
The vertices in set $V$ are called _regular vertices_ and the vertices in set
$U$ are called _supernodes_. We denote a valid input structure by
${\mathcal{I}}=\left(H=(V,U,E),\left\\{\ell(e)\right\\}_{e\in E(H)},D\right)$.
If the distance threshold $D$ is not explicitly defined, then we set it to
$\infty$.

Intuitively, supernodes in set $U$ correspond to clusters in a Neighborhood
Cover ${\mathcal{C}}$ of the vertices in $V$ with some (smaller) distance
threshold, that is computed and maintained recursively. Given a valid input
structure ${\mathcal{I}}=\left(H,\left\\{\ell(e)\right\\}_{e\in
E(H)},D\right)$, we will allow the following types of update operations, that
we refer to as _valid update operations_ :

  * •

Edge Deletion. Given an edge $e\in E(H)$, delete $e$ from $H$.

  * •

Isolated Vertex Deletion. Given a vertex $x\in V(H)$ that is an isolated
vertex, delete $x$ from $H$; and

  * •

Supernode Splitting. The input of this update operation is a supernode $u\in
U$ and a non-empty subset $E^{\prime}\subseteq\delta_{H}(u)$ of edges incident
to $u$. The update operation creates a new supernode $u^{\prime}$, and, for
every edge $e=(u,v)\in E^{\prime}$, it adds a new edge
$e^{\prime}=(u^{\prime},v)$ of length $\ell(e)$ to the graph $H$. We will
sometimes refer to $e^{\prime}$ as a _copy of edge $e$_.

For brevity of notation, we will refer to edge-deletion, isolated vertex
deletion, and supernode-splitting operations as _valid update operations_.
Notice that the update operations may not create new regular vertices, so
vertices may be deleted from the vertex set $V$, but never added to it. A
supernode splitting operation, however, adds a new supernode to the graph $H$,
and also inserts edges into $H$. Unfortunately, this means that the number of
edges in $H$ may grow as the result of the update operations, which makes it
challenging to analyze the running times of various algorithms that we run on
subgraphs $C$ of $H$ in terms of $|E(C)|$. In order to overcome this
difficulty, we use the notion of the _dynamic degree bound_.

######  Definition (Dynamic Degree Bound).

We say that a valid input structure
${\mathcal{I}}=\left(H=(V,U,E),\left\\{\ell(e)\right\\}_{e\in E(H)},D\right)$,
undergoing a sequence $\Sigma$ of valid update operations has dynamic degree
bound $\mu$ iff for every regular vertex $v\in V$, the total number of edges
incident to $v$ that are ever present in $H$ over the course of the update
sequence $\Sigma$ is at most $\mu$.

We will usually denote by $N^{0}(H)$ the number of regular vertices in the
initial graph $H$. If $({\mathcal{I}},\Sigma)$ have dynamic degree bound
$\mu$, then we are guaranteed that the number of edges that are ever present
in $H$ over the course of the update sequence $\Sigma$ is bounded by
$N^{0}(H)\cdot\mu$.

In general, we will always ensure that the dynamic degree bound $\mu$ is quite
low. It may be convenient to think of it as $m^{o(1)}$, where $m$ is the
initial number of edges in the input graph $G$ for the APSP problem.
Intuitively, every supernode of graph $H$ represents some cluster $C$ in a
$(\hat{D},\hat{D}^{\prime})$-neighborhood cover ${\mathcal{C}}$ of $G$, for
some parameters $\hat{D},\hat{D}^{\prime}\ll D$. Typically, each regular
vertex of $H$ represents some actual vertex of graph $G$, and an edge $(v,u)$
is present in $H$ iff vertex $v$ belongs to the cluster $C$ that vertex $u$
represents. Intuitively, we will ensure that the neighborhood cover
${\mathcal{C}}$ of $G$ is constructed and maintained in such a way that the
total number of clusters of ${\mathcal{C}}$ to which a given regular vertex
$v$ ever belongs over the course of the algorithm is very small. This will
ensure that the dynamic degree bound for graph $H$ is small as well.

Note that we can assume without loss of generality that every vertex in the
original graph $H^{0}$ has at least one edge incident to it, as otherwise it
is an isolated vertex, and will remain so as long as it lies in $H$. Moreover,
from the definition of a supernode-splitting operation, it may not be applied
to an isolated vertex (as we require that the edge set $E^{\prime}$ is non-
empty). Therefore, any isolated vertex of $H^{0}$ can be ignored. We will
therefore assume from now on that every supernode in the original graph
$H^{0}$ has degree at least $1$. (This assumption is only used for
convenience, so that we can bound the total number of vertices in $H^{0}$ by
$O(|E(H^{0})|)$.)

We use the following simple observation to show that the distances in the
graph $H$ may not decrease as the result of a valid update operation.

######  Observation 3.1.

Consider the graph $H$ at any time during the execution of the sequence
$\Sigma$ of valid update operations, and let $x,x^{\prime}$ be any two
vertices of $H$. Let $H^{\prime}$ be the graph obtained after a single valid
update operation on $H$. Then $\mbox{\sf
dist}_{H^{\prime}}(x,x^{\prime})\geq\mbox{\sf dist}_{H}(x,x^{\prime})$.

###### Proof.

If the valid update operation is an edge deletion, or an isolated vertex
deletion, then the statement is clearly true. Assume now that the valid update
operation is supernode-splitting, applied to a supernode $u$, with the
corresponding edge set $E^{\prime}$. It is easy to verify that $\mbox{\sf
dist}_{H^{\prime}}(x,x^{\prime})=\mbox{\sf dist}_{H}(x,x^{\prime})$, since
every path $P$ connecting $x$ to $x^{\prime}$ in $H^{\prime}$ can be
transformed into a path $P^{\prime}$ of the same length connecting $x$ to
$x^{\prime}$ in $H$, by replacing the vertex $u^{\prime}$ with the vertex $u$
on it (if $u^{\prime}\in V(P)$; otherwise $P\subseteq H$ holds).

Throughout the paper, it may sometimes be convenient for us to work with
vertex weights. In such cases, we will always let the weight of every
supernode be $0$, and the weight of every regular vertex be $1$. For a
subgraph $C\subseteq H$, we can then denote by $W(C)$ the total weight of all
vertices in $C$. From the above discussion, $|E(C)|\leq W(C)\cdot\mu$ always
holds. Some of the technical tools that we develop work even when vertex
weights are arbitrary. Since we believe that some of these tools are
interesting in their own right, and may be useful for future work, we state
them in the most general way, with arbitrary non-negative vertex weights.
However, when applying these tools to our problem, we will always set vertex
weights as described above.

###  3.2 Generalized Even-Shiloach Trees

In this subsection we show that the basic ES-Tree data structure of [ES81,
Din06, HK95] can be extended to the setting of a valid input structure that
undergoes valid update operations. We do so in the following theorem, whose
proof is standard and is deferred to Section B of Appendix. We note that a
similar data structure was used, either explicity or implicitly, in numerous
previous papers.

######  Theorem 3.2.

There is a deterministic algorithm, that we refer to as _generalized ES-Tree_,
that, given a valid input structure
${\mathcal{I}}=\left(H,\left\\{\ell(e)\right\\}_{e\in E(H)},D\right)$, where
graph $H$ undergoes a sequence $\Sigma$ of valid update operations with
dynamic degree bound $\mu$, and given additionally a source vertex $s\in
V(H)$, and a distance threshold $D^{*}>0$, such that the length of every edge
in $H$ is bounded by $D^{*}$, supports SSSP-query queries: given a vertex
$x\in V(H)$, either correctly establish, in time $O(1)$, that $\mbox{\sf
dist}_{H}(s,x)>D^{*}$, or return a shortest $s$-$x$ path $P$ in $H$, in time
$O(|E(P)|)$. The total update time of the algorithm is
$\widetilde{O}(N^{0}\cdot\mu\cdot D^{*})$, where $N^{0}$ is the number of
regular vertices in the initial graph $H$.

###  3.3 The Recursive Dynamic Neighborhood Cover ($\mathsf{RecDynNC}$)
Problem

In this subsection we define the Recursive Dynamic Neighborhood Cover problem,
and then state our main technical result that provides a deterministic
algorithm for this problem. We then provide an algorithm with faster update
time by exploiting the recursive composability properties of this problem.
This faster algorithm, in turn, will immediately provide an algorithm for the
APSP problem, proving Theorem 1.1, and an algorithm for the Neighborhood Cover
problem, proving Theorem 1.2.

##### Problem Definition.

The input to the Recursive Dynamic Neighborhood Cover ($\mathsf{RecDynNC}$)
problem is a valid input structure
${\mathcal{I}}=\left(H=(V,U,E),\left\\{\ell(e)\right\\}_{e\in E},D\right)$,
where graph $H$ undergoes a sequence $\Sigma$ of valid update operations with
some given dynamic degree bound $\mu$. Additionally, we are given a desired
approximation factor $\alpha$. We assume that we are also given some arbitrary
fixed ordering ${\mathcal{O}}$ of the vertices of $H$, and that any new vertex
that is inserted into $H$ as the result of supernode-splitting updates appears
at the end of the current ordering. The goal is to maintain the following data
structures:

  * •

a collection ${\mathcal{U}}$ of subsets of vertices of graph $H$, together
with a collection ${\mathcal{C}}=\left\\{H[S]\mid S\in{\mathcal{U}}\right\\}$
of clusters in $H$, such that ${\mathcal{C}}$ is a weak $(D,\alpha\cdot D)$
neighborhood cover for the set $V$ of regular vertices in graph $H$. For every
set $S\in{\mathcal{U}}$, the vertices of $S$ must be maintained in a list,
sorted according to the ordering ${\mathcal{O}}$;

  * •

for every regular vertex $v\in V$, a cluster
$C=\mbox{\sf{CoveringCluster}}(v)$, with $B_{H}(v,D)\subseteq V(C)$;

  * •

for every vertex $x\in V(H)$, a list
$\mbox{\sf{ClusterList}}(x)\subseteq{\mathcal{C}}$ of all clusters containing
$x$, and for every edge $e\in E(H)$, a list
$\mbox{\sf{ClusterList}}(e)\subseteq{\mathcal{C}}$ of all clusters containing
$e$.

The set ${\mathcal{U}}$ of vertex subsets must be maintained as follows.
Initially, ${\mathcal{U}}=\left\\{V(H^{0})\right\\}$, where $H^{0}$ is the
initial input graph $H$. After that, the only allowed changes to vertex sets
in ${\mathcal{U}}$ are:

  * •

$\operatorname{DeleteVertex}(S,x)$: given a vertex set $S\in{\mathcal{U}}$,
and a vertex $x\in S$, delete $x$ from $S$;

  * •

$\operatorname{AddSuperNode}(S,u)$: if $u$ is a supernode that is lying in $S$
that just underwent supernode splitting update, add the newly created
supernode $u^{\prime}$ to $S$; and

  * •

$\operatorname{ClusterSplit}(S,S^{\prime})$: given a vertex set
$S\in{\mathcal{U}}$, and a subset $S^{\prime}\subseteq S$ of its vertices, add
$S^{\prime}$ to ${\mathcal{U}}$.

We refer to the above operations as _allowed changes to ${\mathcal{U}}$_. In
other words, if we consider the sequence of changes that clusters in
${\mathcal{C}}$ undergo over the course of the algorithm, the corresponding
sequence of changes in vertex sets in $\left\\{U(C)\mid
C\in{\mathcal{C}}\right\\}$ must obey the above rules.

In addition to maintaining the above data structures, an algorithm for the
$\mathsf{RecDynNC}$ problem needs to support queries $\mbox{\sf{short-path-
query}}(C,v,v^{\prime})$: given two regular vertices $v,v^{\prime}\in V$, and
a cluster $C\in{\mathcal{C}}$ with $v,v^{\prime}\in C$, return a path $P$ in
the current graph $H$, of length at most $\alpha\cdot D$ connecting $v$ to
$v^{\prime}$ in $H$, in time $O(|E(P)|)$. This completes the definition of the
$\mathsf{RecDynNC}$ problem.

### Statement of Main Technical Result

Our main technical result is a deterministic algorithm for the
$\mathsf{RecDynNC}$ problem, that is summarized in the following theorem.

######  Theorem 3.3.

There is a deterministic algorithm for the $\mathsf{RecDynNC}$ problem, that,
on input ${\mathcal{I}}=\left(H=(V,U,E),\left\\{\ell(e)\right\\}_{e\in
E},D\right)$ undergoing a sequence of valid update operations with dynamic
degree bound $\mu$, and a parameter $c/\log\log W<\epsilon<1$, for some large
enough constant $c$, where $W$ is the number of regular vertices in $H$ at the
beginning of the algorithm, achieves approximation factor
$\alpha=(\log(W\mu))^{2^{O(1/\epsilon)}}$, and has total update time
$O\left(W^{1+O(\epsilon)}\cdot\mu^{2+O(\epsilon)}\cdot
D^{3}\cdot(\log(W\mu))^{O(1/\epsilon^{2})}\right)$. Moreover, the algorithm
ensures that for every regular vertex $v\in V$, the total number of clusters
in the neighborhood cover ${\mathcal{C}}$ that the algorithm maintains, to
which vertex $v$ ever belongs over the course of the algorithm is bounded by
$W^{O(1/\log\log W)}$. It also ensures that the neighborhood cover
${\mathcal{C}}$ that it maintains is a strong $(D,\alpha\cdot D)$ neighborhood
cover for the set $V$ of regular vertices of $H$.

The following sections of this paper focus on the proof of Theorem 3.3. Notice
however that the running time of the algorithm from Theorem 3.3 is somewhat
slow, and in particular it has a high dependence on the distance threshold
$D$, that we would like to avoid. We now show an algorithm that exploits the
recursive composability of instances of the $\mathsf{RecDynNC}$ problem in
order to do so.

###  3.4 A Faster Algorithm for $\mathsf{RecDynNC}$ and Proofs of Theorems 1.1
and 1.2

We prove the following theorem, that provides a faster algorithm for the
$\mathsf{RecDynNC}$ problem, and follows from Theorem 3.3.

######  Theorem 3.4.

There is a deterministic algorithm for the $\mathsf{RecDynNC}$ problem, that,
given a valid input structure
${\mathcal{I}}=\left(H=(V,U,E),\left\\{\ell(e)\right\\}_{e\in E},D\right)$
undergoing a sequence of edge-deletion and isolated vertex-deletion
operations, with dynamic degree bound $2$, and a parameter $c/\log\log
W<\epsilon<1$, for some large enough constant $c$, where $W$ is the number of
regular vertices in $H$ at the beginning of the algorithm, achieves
approximation factor $\alpha=(\log W)^{2^{O(1/\epsilon)}}$, with total update
time $O\left(W^{1+O(\epsilon)}\cdot(\log W)^{O(1/\epsilon^{2})}\right)$.
Moreover, the algorithm ensures that for every regular vertex $v\in V$, the
total number of clusters in the weak neighborhood cover ${\mathcal{C}}$ that
the algorithm maintains, to which vertex $v$ ever belongs over the course of
the algorithm, is bounded by $W^{O(1/\log\log W)}$.

We note that, since the dynamic degree bound is $2$, the degree of every
regular vertex in the initial graph $H$ is at most $2$. Notice that supernode-
splitting operations are not allowed in the above theorem, and so the degree
of every regular vertex remains at most $2$ over the course of the algorithm.
Therefore, the number of edges in $H$ is bounded by $2W$ throughout the
algorithm.

We start by showing that Theorems 1.1 and 1.2 immediately follow from Theorem
3.4.

####  3.4.1 Completing the proof of Theorem 1.2

We assume that we are given an $m$-edge graph $G$ with integral length
$\ell(e)\geq 1$ on its edges, that undergoes an online sequence of edge
deletions, together with parameters $c^{\prime}/\log\log m<\epsilon<1$ for
some large enough constant $c^{\prime}$, and $D\geq 1$. Note that we can
assume that $G$ is a connected graph, as otherwise we can run the algorithm on
each of its connected components separately, so $|V(G)|\leq m$ holds. We
construct a bipartite graph $H=(V,U,E)$ as follows. We start with the graph
$G$, and we let $U=V(G)$ be the set of the supernodes of $H$. We then
subdivide every edge $e\in E(G)$ with a new regular vertex $v_{e}$, and we set
the lengths of both new edges to be $\ell(e)$. The set $V$ of regular vertices
of $H$ is the union of two subsets: a set $\left\\{v_{e}\mid e\in
E(G)\right\\}$ of vertices corresponding to edges of $G$, and another subset
$S=\left\\{x^{\prime}\mid x\in V(G)\right\\}$ of vertices corresponding to
vertices of $G$. Every vertex $x^{\prime}\in S$ connects to the corresponding
vertex $x\in V(G)$ with a length-$1$ edge. Once we delete all edges of length
greater than $3D$, we obtain a valid input structure
${\mathcal{I}}=\left(H=(V,U,E),\left\\{\ell(e)\right\\}_{e\in E},3D\right)$.
Given an online sequence $\Sigma$ of edge deletions for graph $G$, we can
produce a corresponding online sequence $\Sigma^{\prime}$ of edge deletions
and isolated vertex deletions for graph $H$, as follows: whenever an edge
$e\in E(G)$ is deleted from $G$, we delete its two corresponding edges (that
are incident to $v_{e}$) from graph $H$, and we then delete vertex $v_{e}$
that becomes an isolated vertex. We have therefore obtained an instance
${\mathcal{I}}$ of the $\mathsf{RecDynNC}$ problem, on valid input structure
${\mathcal{I}}$ that undergoes a sequence of edge-deletion and isolated
vertex-deletion operations. Since the degree of every regular vertex in $H$ is
at most $2$, it is easy to see that $H$ has dynamic degree bound $2$. We let
$W=|V|\leq 2m$ be the number of regular vertices in $H$. By letting
$c^{\prime}$ be a large enough constant, we can assume that $c/\log\log
W<\epsilon<1$, where $c$ is the constant from Theorem 3.4. We run the
algorithm for the $\mathsf{RecDynNC}$ problem from Theorem 3.4 on input
${\mathcal{I}}$ undergoing the sequence $\Sigma^{\prime}$ of update
operations. Let ${\mathcal{C}}$ be the neighborhood cover that the algorithm
maintains. We then define a neighborhood cover ${\mathcal{C}}^{\prime}$ for
graph $G$ as follows. For every cluster $C\in{\mathcal{C}}$, there is a
cluster $C^{\prime}\in{\mathcal{C}}^{\prime}$, which is a subgraph of $G$
induced by vertex set $\left\\{x\in V(G)\mid x^{\prime}\in V(C)\right\\}$.
Recall that cluster set ${\mathcal{C}}$ is initially defined to be
${\mathcal{C}}=\left\\{H\right\\}$, so initially,
${\mathcal{C}}^{\prime}=\left\\{G\right\\}$ holds. After that, the only
changes to vertex sets in ${\mathcal{U}}=\left\\{U(C)\mid
C\in{\mathcal{C}}\right\\}$ are the allowed changes, that include:

  * •

$\operatorname{DeleteVertex}(R,x)$: given a vertex set $R\in{\mathcal{U}}$,
and a vertex $x\in R$, delete $x$ from $R$; if $x=y^{\prime}$ for some vertex
$y\in V(G)$, then we also delete $y$ from the cluster
$C\in{\mathcal{C}}^{\prime}$ representing $H[R]$;

  * •

$\operatorname{AddSuperNode}(R,u)$: since we do not allow supernode splitting
operations, no such updates will be performed; and

  * •

$\operatorname{ClusterSplit}(\tilde{R},R)$: given a vertex set
$R\in{\mathcal{U}}$, and a subset $\tilde{R}\subseteq R$ of its vertices, add
$\tilde{R}$ to ${\mathcal{U}}$. In this case, we create a new cluster in
${\mathcal{C}}^{\prime}$ that is a subgraph of $G$, induced by the set
$\left\\{x\in V(G)\mid x^{\prime}\in R^{\prime}\right\\}$ of vertices.

Additionally, when an edge $e$ is deleted from $G$, we need to delete it from
every cluster of ${\mathcal{C}}$ that contains it. The time that is needed to
make all these updates to cluster set ${\mathcal{C}}^{\prime}$ is subsumed by
the time required to maintain cluster set ${\mathcal{C}}$.

Consider now some vertex $x\in V(G)$. Recall that the algorithm for the
$\mathsf{RecDynNC}$ problem maintains a cluster $C\in{\mathcal{C}}$, with
$B_{H}(x^{\prime},3D)\subseteq V(C)$. It is easy to verify that
$B_{H}(x^{\prime},3D)$ contains, for every vertex $y\in B_{G}(x,D)$, the
corresponding vertex $y^{\prime}\in V$. We then set
$\mbox{\sf{CoveringCluster}}(x)=C^{\prime}$, where
$C^{\prime}\in{\mathcal{C}}$ is the cluster corresponding to $C$.

Lastly, suppose we are given a query $\mbox{\sf{short-path-
query}}(C^{\prime},x,y)$, where $C^{\prime}\in{\mathcal{C}}^{\prime}$, and
$x,y\in V(C)$. We then run query $\mbox{\sf{short-path-
query}}(C,x^{\prime},y^{\prime})$ in the data structure maintained by the
algorithm for the $\mathsf{RecDynNC}$ problem, obtaining a path $P$ in graph
$H$ that connects $x^{\prime}$ to $y^{\prime}$ and has length at most $3\alpha
D$, for $\alpha=(\log m)^{2^{O(1/\epsilon)}}$. By deleting the first and the
last vertex on $P$, and by suppressing some vertices, we obtain a path
$P^{\prime}$ in graph $G$, connecting $x$ to $y$, whose length is at most
$D\cdot(\log m)^{2^{O(1/\epsilon)}}$. The running time of this algorithm is
$O(|E(P)|)$. The fact that we can support queries $\mbox{\sf{short-path-
query}}(C^{\prime},x,y)$, together with the above discussion, proves that the
cluster set ${\mathcal{C}}^{\prime}$ that we maintain is a weak $(D,3\alpha
D)$-neighborhood cover for graph $G$. Moreover, from Theorem 3.4, the total
update time of the algorithm is $O\left(m^{1+O(\epsilon)}\cdot(\log
m)^{O(1/\epsilon^{2})}\right)$, and we are also guaranteed that for every
vertex $v\in V(G)$, the total number of clusters in ${\mathcal{C}}^{\prime}$
to which vertex $v$ ever belonged is at most $m^{O(1/\log\log m)}$.

####  3.4.2 Completing the proof of Theorem 1.1

By using standard scaling and rounding of edge lengths, at the cost of losing
a factor $2$ in the approximation ratio, we can assume that all edge lengths
are integers between $1$ and $L$. We define
$\lambda=\left\lceil\log{L}\right\rceil$ distance thresholds
$D_{1},\ldots,D_{\lambda}$, where for $1\leq i\leq\lambda$, $D_{i}=2^{i}$.

For all $1\leq i\leq\lambda$, we apply the algorithm from Theorem 1.2 to graph
$G$, for distance threshold $D_{i}$, the input parameter $\epsilon$, and
approximation factor $\alpha=O\left((\log m)^{2^{O(1/\epsilon)}}\right)$. We
denote the neighborhood cover that the algorithm maintains by
${\mathcal{C}}_{i}$ and the corresponding data structure by
${\mathcal{D}}_{i}$. Note that the total update time of this algorithm, over
all distance scales $D_{i}$ is $O\left(m^{1+O(\epsilon)}\cdot(\log
m)^{O(1/\epsilon^{2})}\cdot\log L\right)$, as required. We now show algorithms
for processing dist-query and shortest-path-query queries.

Given a query $\mbox{\sf{dist-query}}(x,y)$, for a pair $x,y\in V(G)$ of
vertices, we perform a binary search on an integer $1\leq i\leq\lambda$, such
that, if $C=\mbox{\sf{CoveringCluster}}(x)$ is a cluster in
${\mathcal{C}}_{i}$ that covers $x$, then $y\in V(C)$, but, if
$C^{\prime}=\mbox{\sf{CoveringCluster}}(x)$ is the cluster of
${\mathcal{C}}_{i-1}$ covering $x$, then $y\not\in C^{\prime}$. In order to do
so, we consider the current guess $i^{\prime}$ on the integer $i$, find the
cluster $C=\mbox{\sf{CoveringCluster}}(x)$ in data structure
${\mathcal{D}}_{i^{\prime}}$ in time $O(1)$, and check whether $y\in V(C)$ in
time $O(\log m)$. If this is the case, then in our next guess we increase the
index $i^{\prime}$; otherwise we decrease it. Once the desired index $i$ is
found, we return the value $2D_{i}$. We claim that $D_{i}/2\leq\mbox{\sf
dist}_{G}(x,y)\leq\alpha D_{i}$. Indeed, from the definition of weak
$(D,\alpha D)$-neighborhood cover, since $x$ and $y$ lie in the same cluster
of ${\mathcal{C}}_{i}$, $\mbox{\sf dist}_{G}(x,y)\leq\alpha D_{i}$. Moreover,
since $y$ does not lie in the cluster
$C^{\prime}=\mbox{\sf{CoveringCluster}}(x)$ in ${\mathcal{C}}_{i-1}$, we get
that $y\not\in B_{G}(x,D_{i-1})$, and so $\mbox{\sf
dist}_{G}(x,y)>D_{i-1}=D_{i}/2$. Since we perform a binary search over
$\lambda=\left\lceil\log L\right\rceil$ values $i$, the running time of the
algorithm for responding to the query is $O(\log m\log\log L)$.

Consider now a query $\mbox{\sf{shortest-path-query}}(x,y)$ for a pair $x,y\in
V(G)$ of vertices. We start by computing an index $i$ exactly as in
$\mbox{\sf{dist-query}}(x,y)$, so that $D_{i}/2\leq\mbox{\sf
dist}_{G}(x,y)\leq\alpha D_{i}$, together with the cluster
$C=\mbox{\sf{CoveringCluster}}(x)$ in ${\mathcal{C}}_{i}$, so that $y\in C$
holds. This can be done in time $O(\log m\log\log L)$ as before. We then run
query $\mbox{\sf{short-path-query}}(C,x,y)$ in data structure
${\mathcal{D}}_{i}$, to compute a path $P$ in graph $G$, connecting $x$ to
$y$, of length at most $\alpha\cdot D_{i}\leq 2\alpha\mbox{\sf
dist}_{G}(x,y)\leq(\log m)^{2^{O(1/\epsilon)}}\cdot\mbox{\sf dist}_{G}(x,y)$,
in time $O(|E(P)|)$.

Therefore, in order to prove Theorems 1.1 and 1.2, it is enough to prove
Theorem 3.4.

####  3.4.3 Proof of Theorem 3.4

In this subsection we prove Theorem 3.4 using the algorithm from Theorem 3.3.
We can assume that graph $H$ has no isolated vertices, as all such vertices
can be ignored (e.g. each such vertex can be placed in a separate cluster).
For simplicity, we denote by $n$ and $m$ the number of vertices and edges in
the initial graph $H$. Notice that $m\leq 2W$, and $n\leq 3W$ must hold.

We start by showing that, at the cost of losing a factor $2$ in the
approximation ratio, we can assume that $D=2n$, and that all edge lengths are
integers between $1$ and $D$. We show this using standard arguments. Recall
that, since ${\mathcal{I}}$ is a valid input structure, all edges in $H$ have
lengths at most $D$. Next, we set the length of each edge $e$ to be
$\ell^{\prime}(e)=\left\lceil n\ell(e)/D\right\rceil$.

For every pair $x,y$ of vertices, let $\mbox{\sf dist}^{\prime}(x,y)$ denote
the distance between $x$ and $y$ with respect to the new edge length values.
Notice that for every pair $x,y$ of vertices, $\frac{n}{D}\cdot\mbox{\sf
dist}(x,y)\leq\mbox{\sf dist}^{\prime}(x,y)\leq\frac{n}{D}\cdot\mbox{\sf
dist}(x,y)+n$, since the shortest $x$-$y$ path contains at most $n$ edges.

Therefore, if $\mbox{\sf dist}(x,y)\leq D$, then $\mbox{\sf
dist}^{\prime}(x,y)\leq 2n$. Moreover, if $P$ is an $x$-$y$ path with
$\ell^{\prime}(P)\leq\alpha n$, then $\ell(P)\leq\alpha D$ must hold. It is
now enough to solve the problem on graph $H$ with the new edge weights
$\ell^{\prime}(e)$ for $e\in E(H)$, and distance bound $D^{\prime}=2n$.
Therefore, we assume from now on that $D=2n$, and that all edge lengths are
integers between $1$ and $D$.

The main idea of the proof is to apply the algorithm from Theorem 3.3
recursively, for smaller and smaller distance bounds. Specifically, we prove
the following lemma by induction.

######  Lemma 3.5.

There is a universal constant $\tilde{c}$, and a deterministic algorithm for
the $\mathsf{RecDynNC}$ problem, that, given a valid input structure
${\mathcal{I}}=\left(H=(V,U,E),\left\\{\ell(e)\right\\}_{e\in E(H)},D\right)$
undergoing a sequence of edge-deletion and isolated vertex-deletion
operations, with dynamic degree bound $2$, and a parameter $0<\epsilon<1$,
such that $D\leq 6W^{\epsilon i}$ holds for some integer $i$, where $W$ is the
number of regular vertices in $H$ at the beginning of the algorithm, achieves
approximation factor $\alpha_{i}=(\log W)^{\tilde{c}i\cdot
2^{\tilde{c}/\epsilon}}$, and has total updtate time at most
$\left(\tilde{c}^{i}\cdot W^{1+\tilde{c}\epsilon}\cdot(\log
W)^{\tilde{c}/\epsilon^{2}}\right)$. Moreover, the algorithm ensures that for
every regular vertex $v\in V$, the total number of clusters in the weak
neighborhood cover ${\mathcal{C}}$ that the algorithm maintains, to which
vertex $v$ ever belongs over the course of the algorithm, is bounded by
$W^{O(1/\log\log W)}$.

Notice that the above lemma completes the proof of Theorem 3.4, by setting
$i=\left\lceil 1/\epsilon\right\rceil$. The approximation factor achieved by
the algorithm is at most $(\log W)^{2\tilde{c}\cdot
2^{\tilde{c}/\epsilon}/\epsilon}=(\log W)^{2^{O(1/\epsilon)}}$, and its
running time is $O\left(W^{1+O(\epsilon)}\cdot(\log
W)^{O(1/\epsilon^{2})}\right)$. The proof of the lemma is somewhat technical
and is deferred to Section C of Appendix. We provide here a short intuitive
overview of the proof. The proof is by induction on $i$, where the base case,
with $i=1$, follows immediately by invoking the algorithm from Theorem 3.3. In
order to prove the lemma for some integer $i>1$, we select a threshold
$D^{\prime}\approx 6W^{\epsilon(i-1)}$; we say that an edge $e\in E$ is long,
if its length is greater than $D^{\prime}$, and it is short otherwise. Let
$H^{\prime}$ be the graph obtained from $H$ after all long edges are deleted
from it. We can then use the induction hypothesis in order to maintain a data
structure ${\mathcal{D}}(H^{\prime})$, solving the $\mathsf{RecDynNC}$ problem
on graph $H^{\prime}$, with distance bound $\Theta(D^{\prime})$, and
approximation factor $\alpha_{i-1}=(\log W)^{\tilde{c}(i-1)\cdot
2^{\tilde{c}/\epsilon}}$. Let ${\mathcal{C}}^{\prime}$ be the collection of
clusters maintained by the algorithm. Next, we define another graph $\hat{H}$,
as follows. Initially, we start with $\hat{H}=H$, except that we increase all
edge lengths to become integral multiples of $D^{\prime}$; this does not
distort the lengths of long edges by much, but it may increase lengths of
short edges significantly. Additionally, for every cluster
$C\in{\mathcal{C}}^{\prime}$, we add a supernode $u(C)$ to graph $\hat{H}$,
that connects to every regular vertex $v\in V(C)$ with an edge of length
$D^{\prime}$. Let $\hat{H}^{0}$ be the initial graph $\hat{H}$, before any
updates to graph $H$. We show that we can use the data structure
${\mathcal{D}}(H^{\prime})$, and the corresponding dynamic neighborhood cover
${\mathcal{C}}^{\prime}$, in order to produce a sequence of valid update
operations for graph $\hat{H}$, so that, if the resulting sequence of update
operations is applied to the initial graph $\hat{H}^{0}$, then the resulting
dynamic graph is precisely $\hat{H}$. We also show that distances are
approximately preserved in $\hat{H}$: that is, if $v,v^{\prime}$ are two
regular vertices in graph $H$ that lie at distance at most $D$ in $H$, then
the distance between $v$ and $v^{\prime}$ in $\hat{H}$ is also bounded by
$O(D)$. Additionally, we show an algorithm that, given a path $P$ in graph
$\hat{H}$, connecting any pair $v,v^{\prime}$ of its regular vertices,
produces a path $P^{\prime}$ in graph $H$, connecting the same pair of
vertices, such that the length of $P^{\prime}$ is close to the length of $P$.
Lastly, we scale all edge lengths in graph $\hat{H}$ down by factor
$D^{\prime}$, and use the algorithm from Theorem 3.3 in order to maintain a
neighborhood cover $\hat{\mathcal{C}}^{\prime}$ in the resulting graph
$\hat{H}^{\prime}$, with distance threshold $\hat{D}^{\prime}=D/D^{\prime}\leq
W^{O(\epsilon)}$. We exploit this data structure (that we denote by
${\mathcal{D}}(\hat{H}^{\prime})$), and the fact that $V(H)\subseteq
V(\hat{H}^{\prime})$, in order to maintain neighborhood cover ${\mathcal{C}}$
for graph $H$, as follows. Consider the collection of vertex sets
$\hat{\mathcal{U}}^{\prime}=\left\\{V(C)\mid
C\in\hat{\mathcal{C}}^{\prime}\right\\}$ that is maintained by data structure
${\mathcal{D}}(\hat{H}^{\prime})$. For every vertex set
$S\in\hat{\mathcal{U}}^{\prime}$, we define a set $S^{\prime}=S\cap V(H)$. We
then let ${\mathcal{C}}=\left\\{H[S^{\prime}]\mid
S\in\hat{\mathcal{U}}^{\prime}\right\\}$ be the neighborhood cover for graph
$H$. In other words, we maintain the same set of clusters as
$\hat{\mathcal{C}}^{\prime}$, except that we ignore vertices that do not lie
in the graph $H$. This completes the high-level description of the proof of
Lemma 3.5. A formal proof appears in Section C of Appendix.

The remainder of this paper focuses on the proof of Theorem 3.3. In subsequent
sections, we gradually introduce several new technical tools, which are used
in order to define faster and faster algorithms for the $\mathsf{RecDynNC}$
problem, building up to the proof of Theorem 3.3.

##  4 First Set of Tools: Procedure $\mathsf{ProcCut}$, Initial Neighborhood-
Cover Decomposition, and Reduction to $\mathsf{MaintainCluster}$ Problem

In this section we introduce one of the central tools that we use in order to
maintain neighborhood cover – Procedure $\mathsf{ProcCut}$. Intuitively,
suppose we are given a valid input structure
${\mathcal{I}}=\left(H,\left\\{\ell(e)\right\\}_{e\in E(H)},D\right)$ that
undergoes a sequence of valid update operations with dynamic degree bound
$\mu$, and our goal is to solve the $\mathsf{RecDynNC}$ problem on it, for
some approximation factor $\alpha$. We set vertex weights in the usual way:
the weight of every regular vertex is $1$, and the weight of each supernode is
$0$. We assume that we are given some parameter $W\geq W^{0}(C)$, where
$W^{0}(C)$ is the weight of all vertices in the initial graph $C$. We will
maintain a neighborhood cover ${\mathcal{C}}$ of $H$, starting from
${\mathcal{C}}=\left\\{H\right\\}$. Given some subgraph $C\subseteq H$ (that
may lie in the neighborhood cover ${\mathcal{C}}$), whose diameter is greater
than $D^{\prime}=\Theta(D\log^{4}W)$, the procedure produces two new clusters
$C^{\prime},C^{\prime\prime}\subseteq C$. It outputs cluster $C^{\prime}$
explicitly, by listing all its vertices and edges, while cluster
$C^{\prime\prime}$ is output implicitly, by listing all vertices and edges of
$C\setminus C^{\prime\prime}$. Cluster $C^{\prime}$ is then added to the
neighborhood cover ${\mathcal{C}}$, and cluster $C\in{\mathcal{C}}$ is updated
so that $C=C^{\prime\prime}$ holds. We say that cluster $C^{\prime}$ was
_split off of $C$_. In order to ensure that ${\mathcal{C}}$ remains a valid
neighborhood cover, we cannot guarantee that the two clusters $C^{\prime}$ and
$C^{\prime\prime}$ are disjoint, but we will ensure that they have a small
overlap. At the beginning of our algorithm for the $\mathsf{RecDynNC}$
problem, we will compute an initial neighborhood cover ${\mathcal{C}}$ via
Algorithm $\mathsf{InitNC}$, that is described later in this section, which
iteratively employs Procedure $\mathsf{ProcCut}$ on the input graph $H$. As
the algorithm progresses and edges are deleted from $H$, the diameters of some
clusters $C\in{\mathcal{C}}$ may become large. Intuitively, whenever that
happens, we would like to further decompose the cluster $C$ by employing
Procedure $\mathsf{ProcCut}$ again. In practice, we will define another
problem, $\mathsf{MaintainCluster}$, whose goal is to maintain the cluster
$C\in{\mathcal{C}}$ and to support queries $\mbox{\sf{short-path-
query}}(C,v,v^{\prime})$: given two regular vertices $v,v^{\prime}\in V(C)$,
return a path $P$ in $C$, of length at most $\alpha\cdot D$ connecting $v$ to
$v^{\prime}$, in time $O(|E(P)|)$. The algorithm for the
$\mathsf{MaintainCluster}$ problem on cluster $C$ may, at any time, raise a
flag $F_{C}$ to indicate that it can no longer support short-path-query
queries because the diameter of $C$ became too large. When flag $F_{C}$ is
raised, the algorithm for the $\mathsf{MaintainCluster}$ problem needs to
supply two vertices $x,y\in V(C)$ with $\mbox{\sf
dist}_{C}(x,y)>\Omega(D\log^{4}W)$. We will then employ Procedure
$\mathsf{ProcCut}$ on graph $C$, possibly multiple times, in order to update
the cluster $C$, so that its diameter falls back below $\alpha D$. As part of
this process, new clusters will be added to the neighborhood cover
${\mathcal{C}}$. As mentioned already, the clusters in ${\mathcal{C}}$ may not
be disjoint. However, we will ensure that every regular vertex lies in only a
small number of such clusters. It is this requirement that makes the
description and the analysis of Procedure $\mathsf{ProcCut}$ somewhat
challenging.

The remainder of this section is organized as follows. We start with some
basic definitions and notation in Section 4.1. We describe Procedure
$\mathsf{ProcCut}$ and provide its analysis in Section 4.2. Then we describe
and analyze Procedure $\mathsf{InitNC}$ for computing an initial Neighborhood
Cover, in Section 4.3. In Section 4.4, we provide a general algorithmic
framework for solving the $\mathsf{RecDynNC}$ problem that exploits both
Procedure $\mathsf{InitNC}$ and Procedure $\mathsf{ProcCut}$. The framework
assumes that we are given an oracle that flags clusters $C$ whose diameter
become too large, and provides witnesses for this, in the form of a pair $x,y$
of vertices of $C$ whose distance in $C$ is large. In Section 4.5 we define a
new problem, called $\mathsf{MaintainCluster}$. An algorithm for this problem
will be used in order to implement the oracle in the above-mentioned
algorithmic framework, and will also be responsible for supporting short-path-
query queries within the clusters. We also state our main result for the
$\mathsf{MaintainCluster}$ problem – namely, a fast dynamic algorithm for it,
and complete the proof of Theorem 3.3 using it in Section 4.5. The remainder
of the paper then focuses on desiginig a fast algorithm for the
$\mathsf{MaintainCluster}$ problem. As a first step towards this goal, in
Section 4.6 we provide a slow and simple algorithm for the
$\mathsf{MaintainCluster}$ problem, called $\mathsf{AlgSlow}$, that we will
use as a recursion base.

###  4.1 Basic Definition, Parameters and Notation

Throughout this section, we assume that we are given a valid input structure
${\mathcal{I}}=\left(H,\left\\{\ell(e)\right\\}_{e\in E(H)},D\right)$, with
$H=(V,U,E)$, that undergoes a sequence $\Sigma=(\sigma_{1},\sigma_{2},\ldots)$
of valid update operations with dynamic degree bound $\mu$. We define vertex
weights in the usual way: the weight of every regular vertex is $1$, and the
weight of every supernode is $0$. We denote by $W$ the total weight of all
vertices at the beginning of the algorithm. We assume that we are given a
target approximation factor $\alpha\geq\Omega(\log^{4}W)$. Our goal is to
solve the $\mathsf{RecDynNC}$ problem on ${\mathcal{I}}$ with approximation
factor $\alpha$. Therefore, we will maintain a collection ${\mathcal{C}}$ of
vertex-induced subgraphs of $H$, that we call clusters. At the beginning of
the algorithm, we set ${\mathcal{C}}=\left\\{H^{0}\right\\}$, where $H^{0}$ is
the initial graph $H$ (but we will may make some additional updates to this
initial set of clusters before processing the first update
$\sigma_{1}\in\Sigma$).

We use the following parameters: $r=2\left\lceil\frac{\log W}{\log\log
W}\right\rceil$, and $\gamma=2^{r}=W^{O(1/\log\log W)}$. As mentioned above,
we aim to construct and maintain a strong $(D,\alpha D)$-neighborhood cover
${\mathcal{C}}$. We will ensure that for every regular vertex $v\in V(H)$, the
number of clusters in ${\mathcal{C}}$ to which $v$ ever belongs is at most
$\gamma$.

Given a regular vertex $v\in V(H)$, we denote by $n_{v}$ the number of
clusters in the current cluster set ${\mathcal{C}}$ containing $v$. In order
to bound the total number of clusters to which a regular vertex belongs, we
use the notion of _vertex budgets_ that we define next.

######  Definition (Vertex Budgets).

Let $x\in V(H)$ be a vertex, and let $C\in{\mathcal{C}}$ be a cluster that
contains $x$. Then the _budget of $x$ for cluster $C$_ is
$\beta_{C}(x)=\left(1+\frac{\log W(C)}{\log^{2}W}\right)\cdot w(x)$. The total
budget of $x$ is $\beta(x)=\sum_{\stackrel{{\scriptstyle
C\in{\mathcal{C}}:}}{{x\in V(C)}}}\beta_{C}(x)$. For a subset $X\subseteq
V(H)$ of vertices, we denote by $\beta(X)=\sum_{x\in X}\beta(x)$.

Note that for a supernode $u\in U$, $\beta(u)=0$, since $w(u)=0$, and for a
regular vertex $v$, for every cluster $C$ containing $v$,
$w(v)\leq\beta_{C}(v)\leq(1+1/\log W)w(v)$, and overall,
$w(v)n_{v}\leq\beta(v)\leq(1+1/\log W)w(v)n_{v}$.

Assume now that we are given some collection ${\mathcal{C}}$ of clusters of
$H$, and let $C\in{\mathcal{C}}$ be any such cluster. As graph $H$ undergoes
valid update operations, cluster $C$ is updated accordingly. Specifically,
consider any update opertion $\sigma_{t}\in\Sigma$. If $\sigma_{t}$ is a
deletion of an edge $e$, and $e\in E(C)$, then we delete $e$ from $C$ as well.
If $\sigma_{t}$ is a deletion of an isolated vertex $x$, and $x\in V(C)$, then
we delete $x$ from $C$ as well. Assume now that $\sigma_{t}$ is a supernode
splitting operation, applied to a supernode $u$, and a set
$E^{\prime}\subseteq\delta_{H}(u)$ of its incident edges. If $u\not\in C$,
then we do not need to update the cluster $C$. Otherwise, we let
$E^{\prime}_{C}=E^{\prime}\cap E(C)$. We then update the cluster $C$ by
performing a supernode-splitting operation in it, for vertex $u$, with edge
set $E^{\prime}_{C}$. Note that such update operations may not introduce new
regular vertices into $C$. We then immediately obtain the following
observation.

######  Observation 4.1.

If an edge-deletion or a supernode-splitting update operation is performed in
graph $H$, then for every vertex $x\in V(H)$, budget $\beta(x)$ remains
unchanged, and for every cluster $C$ containing $x$, $\beta_{C}(x)$ remains
unchanged. Additionally, for every cluster $C$, $\sum_{x\in V(C)}\beta_{C}(x)$
remains unchanged, and the total budget of all vertices $\sum_{x\in
V(H)}\beta(x)$ remains unchanged. If an isolated vertex deletion update
operation is performed in graph $H$, with the deleted vertex $y$, then
$\sum_{x\in V(H)}\beta(x)$ decreases by at least $\beta(y)$; for every cluster
$C^{\prime}\in{\mathcal{C}}$ with $y\not\in C^{\prime}$, the budget
$\sum_{x\in V(C)}\beta_{C}(x)$ does not change, and for every cluster
$C^{\prime}\in{\mathcal{C}}$ with $y\in C^{\prime}$, $\sum_{x\in
V(C)}\beta_{C}(x)$ decreases by at least $\beta_{C}(y)$.

Recall that $r=2\left\lceil\frac{\log W}{\log\log W}\right\rceil$. The regular
vertices in $V$ are partitioned into classes $S_{0},\ldots,S_{r}$, as follows.

######  Definition (Vertex Classes).

For a regular vertex $v\in V$ and an integer $0\leq j<r$, we say that $v$
belongs to class $S_{j}$, iff $2^{j}\leq n_{v}<2^{j+1}$. If $n_{v}\geq 2^{r}$,
then we say that $v$ belongs to class $S_{r}$. For all $1\leq j\leq r$, we
denote $S_{\geq j}=S_{j}\cup\cdots\cup S_{r}$.

###  4.2 Procedure $\mathsf{ProcCut}$

The input to Procedure $\mathsf{ProcCut}$ is a cluster $C\in{\mathcal{C}}$,
some vertex $x\in V(C)$, and a distance threshold $D$ (which is identical to
the input distance parameter $D$). The procedure runs Dijkstra’s algorithm (or
weighted BFS) from vertex $x$ in graph $C$, up to a certain depth $D^{*}$,
that will be determined later.

Recall that Dijkstra’s algorithm maintains a set $S$ of “discovered” vertices,
where at the beginning $S=\left\\{x\right\\}$. Throughout the algorithm, for
every vertex $y\in S$, we maintain the distance $\mbox{\sf dist}_{C}(x,y)$,
and a neighbor vertex $a_{y}$ of $y$ that does not lie in $S$, and minimizes
the length of the edge $(y,a_{y})$. In every iteration, we select a vertex
$y\in S$, for which $\mbox{\sf dist}_{C}(x,y)+\ell(y,a_{y})$ is minimized, and
add vertex $a_{y}$ to $S$. We are then guaranteed that $\mbox{\sf
dist}_{C}(x,a_{y})=\mbox{\sf dist}_{C}(x,y)+\ell(y,a_{y})$. Assume that we are
given, for every vertex $y\in V(C)$, a list $\lambda(y)$ of its neighbors $a$,
sorted according to the length $\ell(a,y)$ of the corresponding edge, from
smallest to largest. Then Dijkstra’s algorithm can be implemented so that, if
$S_{i}$ is the set $S$ after the $i$th iteration, then the total running time
of the algorithm up to and including iteration $i$ is $O(E(S_{i}))$. In order
to do so, we maintain, for every vertex $y\in V(G)$, a pointer $p_{y}$ to the
vertex $a_{y}$ on the list $\lambda(y)$. We also maintain a heap of vertices
in set $\left\\{a_{y}\mid y\in S\right\\}$, whose key is $\mbox{\sf
dist}_{G}(x,y)+\ell(y,a_{y})$. In every iteration, we select a vertex
$a=a_{y}$ from the top of the heap, add it to $S$, and then advance the
pointer $p_{y}$ until the first vertex that does not lie in $S$ is encountered
(if vertex $a$ that was added to $S$ serves as vertex $a_{y}$ for several
vertices $y\in S$, we advance the pointer $p_{y}$ for each such vertex $y$).
We also initialize pointer $p_{a}$.

For all $i\geq 0$, we denote by $L_{i}$ the set of all vertices of $C$ that
lie at distance $2(i-1)D+1$ to $2iD$ from $x$ in $C$. In other words:

$L_{i}=B_{C}(x,2iD)\setminus B_{C}(x,2(i-1)D).$

We refer to the vertices of $L_{i}$ as _layer $i$ of the BFS_. We denote by
$W_{i}=\sum_{y\in L_{i}}w(y)$ the total weight of all vertices in $L_{i}$.
Recall that we have denoted by $W$ the total weight of all vertices of $H$ at
the beginning of the algorithm. The following definition is crucial for the
description of Procedure $\mathsf{ProcCut}$.

######  Definition (Eligible Layer).

For an integer $i>1$, we say that layer $L_{i}$ of the BFS is _eligible_ iff
the following conditions hold:

  1. C1.

$\sum_{i^{\prime}\leq i}W_{i^{\prime}}\leq W(C)/2$;

  2. C2.

$W_{i}\leq\left(\sum_{i^{\prime}<i}W_{i^{\prime}}\right)/(64\log^{2}W)$; and

  3. C3.

for all $1\leq j\leq r$: $W(L_{i}\cap S_{\geq
j})\leq\left(\sum_{i^{\prime}<i}W(L_{i^{\prime}}\cap S_{\geq
j})\right)/\left(64\log^{2}W\right)$.

We need the following claim, whose proof uses standard arguments and appears
in Section D.1 of Appendix.

######  Claim 4.2.

If the total weight of all vertices in $B_{C}(x,256D\log^{4}W)$ is at most
$W(C)/2$, then there is some eligible layer $L_{i}$ with $1<i<128\log^{4}W$.

We are now ready to describe the algorithm for $\mathsf{ProcCut}$. The input
to the procedure is a cluster $C\in{\mathcal{C}}$, a vertex $x\in V(C)$, and a
distance threshold $D>0$. We assume that we are given, for every vertex $y\in
V(C)$, a list $\lambda(y)$ of its neighbors $a$ in $C$, sorted according to
the length $\ell(a,y)$ of the corresponding edge, from smallest to largest.
The procedure runs Dijkstra’s algorithm from the input vertex $x$ in graph
$C$, until it encounters the first layer $L_{i}$, such that either
$\sum_{i^{\prime}\leq i}W_{i^{\prime}}>W(C)/2$, or $L_{i}$ is an eligible
layer. In the former case, the algorithm outputs FAIL. In the latter case, it
computes two new clusters: cluster $C^{\prime}$ is the subgraph of $H$ induced
by vertex set $L_{1}\cup\cdots\cup L_{i}$. Cluster $C^{\prime\prime}$ is
obtained from cluster $C$ by deleting all vertices in $L_{1}\cup\cdots
L_{i-1}$ from it. The algorithm outputs cluster $C^{\prime}$ explicitly, by
listing all its vertics and edges, and it outputs cluster $C^{\prime\prime}$
implicitly, by listing the edges and the vertices of $C\setminus
C^{\prime\prime}$. Notice that vertices of $L_{i}$, and edges that connect
them, belong to both $C^{\prime}$ and $C^{\prime\prime}$. The following
observation immediately follows from Claim 4.2 and the definition of a layer.

######  Observation 4.3.

If Procedure $\mathsf{ProcCut}(C,x,D)$ does not return FAIL, then it produces
two clusters $C^{\prime},C^{\prime\prime}$, with $W(C^{\prime})\leq W(C)/2$,
and $\mbox{\sf diam}(C^{\prime})\leq 512D\log^{4}W$. Moreover,
$V(C^{\prime})\subseteq B_{C}(x,256D\log^{4}W)$.

Next, we establish that the two new clusters $C^{\prime},C^{\prime\prime}$
contain a $D$-neighborhood every vertex of $C$ in the following claim, whose
proof appears in Section D.2 of Appendix.

######  Claim 4.4.

Assume that Procedure $\mathsf{ProcCut}(C,x,D)$ produces two clusters
$C^{\prime}$ and $C^{\prime\prime}$. Then for every vertex $y\in V(C)$, either
$B_{C}(y,D)\subseteq V(C^{\prime})$ or $B_{C}(y,D)\subseteq
V(C^{\prime\prime})$ must hold.

We view Procedure $\mathsf{ProcCut}$ as creating a new cluster $C^{\prime}$
that is split off of the cluster $C$; recall that $W(C^{\prime})\leq W(C)/2$
must hold. We then update the cluster $C$, by setting $C=C^{\prime\prime}$.
Notice that the running time of the procedure is $O(|E(C^{\prime})|)\leq
O(W(C^{\prime})\mu)$.

Lastly, we prove the following lemma, that is central to bounding the number
of clusters that a regular vertex may belong to. The proof appears in Section
D.3 of Appendix.

######  Lemma 4.5.

Assume that Procedure $\mathsf{ProcCut}(C,x,D)$, when applied to a cluster
$C\in{\mathcal{C}}$, produced two clusters $C^{\prime}$, $C^{\prime\prime}$,
and assume that cluster set ${\mathcal{C}}$ was updated accordingly. Denote by
$\beta$ and $\beta^{\prime}$ the total budget of all vertices in $V(H)$ at the
beginning and at the end of the procedure, respectively. For all $1\leq j\leq
r$, let $\beta_{\geq j}$ and $\beta^{\prime}_{\geq j}$ denote the total budget
of all vertices in $S_{\geq j}$ at the beginning and at the end of the
procedure, respectively, and let $W^{\prime}_{j}$ be the total weight of new
regular vertices that join class $S_{j}$ at the end of the procedure. Then
$\beta^{\prime}\leq\beta$, and moreover, for all $1\leq j\leq r$, $\beta_{\geq
j}^{\prime}\leq\beta_{\geq j}+2^{j}(1+1/\log W)W^{\prime}_{j}$.

##### Modified $\mathsf{ProcCut}$.

So far we have described Procedure $\mathsf{ProcCut}$, whose input is a
cluster $C$, a vertex $x$, and a distance parameter $D$. Recall that, if the
total weight of all vertices in $B_{C}(x,256D\log^{4}W)$ is greater than
$W(C)/2$, the procedure may return FAIL. We will sometimes use the procedure
slightly differently. The input to this modified procedure, that we denote by
$\mathsf{ProcCut}^{\prime}$, is a cluster $C$, a distance bound $D$, and two
vertices $x,y\in V(C)$ with $\mbox{\sf dist}_{C}(x,y)\geq 1024D\log^{4}W$. As
before, we assume that we are given, for every vertex $a\in V(C)$, a list
$\lambda(a)$ of its neigbhors $b$, sorted by the length of the corresponding
edge $(a,b)$. We run the procedure $\mathsf{ProcCut}$ simultaneously from
vertex $x$ and from vertex $y$ in graph $C$. In other words, we run Dijkstra’s
algorithm from both vertices simultaneously, so that the number of edges that
the two algorithms discover at each time step (or, equivalently, the time they
invest), remain within a constant factor from each other. Once an eligible
layer is reached by either of the procedures, we terminate both algorithms
(since $B_{C}(x,256D\log^{4}W)\cap B_{C}(y,256D\log^{4}W)=\emptyset$, this is
guaranteed to happen, from 4.2, with a layer $L_{i}$ whose index
$1<i<128\log^{4}W$). Assume w.l.o.g. that $\mathsf{ProcCut}(C,x)$ has reached
an eligible layer $L_{i}$ before $\mathsf{ProcCut}(C,y)$. Let
$C^{\prime},C^{\prime\prime}$ be the two resulting clusters, so that $x\in
C^{\prime}$, $V(C^{\prime})=L_{1}\cup\cdots\cup L_{i}$, while $y\in
C^{\prime\prime}$, with $V(C^{\prime\prime})=V(C)\setminus(L_{1}\cup\cdots\cup
L_{i-1})$, and $W(C^{\prime})\leq W(C)/2$. We then let $C^{\prime\prime}$ be
the cluster obtained from $C$ by deleting the vertices of $L_{1}\cup\cdots\cup
L_{i-1}$. The outcome of the procedure $\mathsf{ProcCut}^{\prime}(C,x,y,D)$ is
the pair $C^{\prime},C^{\prime\prime}$ of clusters, where, as before, cluster
$C^{\prime}$ is returned explicitly, by listing all of its vertices and edges,
and cluster $C^{\prime\prime}$ is returned implicitly, by listing all vertices
and edges of $C\setminus C^{\prime\prime}$. We summarize the properties of
Procedure $\mathsf{ProcCut}^{\prime}$ in the next claim.

######  Claim 4.6.

Procedure $\mathsf{ProcCut}^{\prime}(C,x,y,D)$, given a pair $x,y\in V(C)$ of
vertices with $\mbox{\sf dist}_{C}(x,y)\geq 1024D\log^{4}W$ produces two
subgraphs $C^{\prime},C^{\prime\prime}$ of $C$, with $x\in C^{\prime}\setminus
C^{\prime\prime}$ and $y\in C^{\prime\prime}\setminus C^{\prime}$, or the
other way around. Moreover, $\mbox{\sf diam}(C^{\prime})\leq 512D\log^{4}W$,
$W(C^{\prime})\leq W(C)/2$, and for every vertex $z\in V(C)$, either
$B_{C}(z,D)\subseteq V(C^{\prime})$ or $B_{C}(z,D)\subseteq