# Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and
Slightly Super-Linear Work

Michael Elkin1 and Shaked Matar1

(1Department of Computer Science, Ben-Gurion University of the Negev, Beer-
Sheva, Israel.
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
We study a _$(1+\epsilon)$ -approximate single-source shortest paths_
(henceforth, $(1+\epsilon)$-SSSP) in $n$-vertex undirected, weighted graphs in
the parallel (PRAM) model of computation. A randomized algorithm with
polylogarithmic time and slightly super-linear work $\tilde{O}(|E|\cdot
n^{\rho})$, for an arbitrarily small $\rho>0$, was given by Cohen [Coh94] more
than $25$ years ago. Exciting progress on this problem was achieved in recent
years [EN17b, EN19, Li19, ASZ19], culminating in randomized polylogarithmic
time and $\tilde{O}(|E|)$ work. However, the question of whether there exists
a _deterministic_ counterpart of Cohen’s algorithm remained wide open.

In the current paper we devise the first _deterministic_ _polylogarithmic-
time_ algorithm for this fundamental problem, with work $\tilde{O}(|E|\cdot
n^{\rho})$, for an arbitrarily small $\rho>0$. This result is based on the
first efficient deterministic parallel algorithm for building hopsets, which
we devise in this paper.

##  1 Introduction

###  1.1 Approximate Single-Source Shortest Paths

Consider a weighted undirected graph $G=(V,E,\omega)$ with111One can also
extend our results to non-negative weights. To eliminate zero weight edges,
one starts with contracting them. This can be done, e.g., by running the
algorithm of Shiloach and Vishkin [SV82]. $\omega(e)>0$ for every $e\in E$,
and a source vertex $s\in V$. We want to compute $(1+\epsilon)$-approximate
shortest paths from $s$ to all other vertices (henceforth, $(1+\epsilon)$-SSSP
problem), for an arbitrarily small constant $\epsilon>0$, in the parallel PRAM
model of computation. This is one of the most basic and central graph
algorithmic problems, and it has been intensively researched starting from
late eighties. In particular, in their influential survey on parallel
algorithms, Karp and Ramachandran [KR90] list six fundamental graph-
algorithmic problems for which there was no satisfactory solution known. The
SSSP problem is one of them.

Early algorithms for this problem [UY91, KS97] used randomization, and
provided tradeoff between time $t$ and number of processors $p$ in which the
product $t\cdot p$ is close to $n^{3}$. Improved tradeoffs were given by Shi
and Spencer [Spe97, SS99], whose randomized algorithm requires $\tilde{O}(t)$
time for a parameter $t,\ 1\leq t\leq n$, and
$\tilde{O}(\frac{n^{3}}{t^{2}}+|E|)$ work. (The notation $\tilde{O}$ hides
here a polylogarithmic dependence of $n$.) Cohen [Coh97] devised a
deterministic algorithm that achieves a similar tradeoff. Note however that
for polylogarithmic time, the work complexity of her algorithm becomes
$\tilde{O}(n^{3})$.

Galil and Margalit [GM97], Alon et al. [AGM97] and Zwick [Zwi98] devised
algorithms based on fast matrix multiplication for the
$(1+\epsilon)$-approximate variant of the problem. These algorithms have
polylogarithmic (parallel) time and work complexity $O(n^{\omega})$, where
$\omega<2.377\dots$ is the matrix multiplication exponent [CW87, Wil12, GU18].

In a major breakthrough, Cohen [Coh94] devised a _randomized_
$(1+\epsilon)$-approximate algorithm for this problem with polylogarithmic
time $({\log n})^{O\left(\frac{\log{1}/{\rho}}{\rho}\right)}$, and work
complexity $\tilde{O}(|E|\cdot n^{\rho})$, for any arbitrarily small constant
parameters $\epsilon,\rho>0$. Her algorithm is based on _hopsets_. See Section
1.2 for the definition of hopset.

Improved constructions of hopsets, due to [EN17b, EN19], led to improved
tradeoff for the problem: specifically, their algorithm has running time
$({\log n})^{O(1/\rho)}$, and work $\tilde{O}(|E|\cdot n^{\rho})$. Similarly
to the algorithm of Cohen [Coh94], the algorithms of [EN17b, EN19] are
randomized.

Most recently, using ideas from continuous optimization [She16, Mad13,
BKKL16], Li [Li19] and Andoni et al. [ASZ19] devised algorithms with $({\log
n})^{O(1)}$ running time and $\tilde{O}(|E|)$ work for the $(1+\epsilon)$-SSSP
problem. Their algorithms are, however, randomized as well.

To summarize, the only known _deterministic_ PRAM algorithms for this central
problem that use polylogarithmic time require at least $O(n^{\omega})$ work
[Zwi02]. The question if there exists a _deterministic_ algorithm with
polylogarithmic time and close to $|E|$ work complexity remained wide open,
despite all this intensive research.

In the current paper, we devise the first deterministic PRAM NC algorithm for
building hopsets. As a consequence, we obtain a _deterministic_
polylogarithmic-time algorithm with slightly super-linear work for the
$(1+\epsilon)$-SSSP problem. Specifically, for any arbitrarily small constant
parameter $\rho>0$, our algorithm has running time $({\log n})^{O(1/\rho)}$,
and work complexity $\tilde{O}(|E|\cdot n^{\rho})$.

Providing deterministic solutions for fundamental problems for which efficient
randomized parallel algorithms are known is a central thread in Theoretical
Computer Science. The importance of derandomizing PRAM algorithm was pointed
out in a pioneering work by Karp and Pippenger [KP83]. See also [KW85, Lub86,
KR88, NW88, KR90, NN93, BRS94]. In particular, derandomization of PRAM
algorithms led to development of fundamental tools such as small-biased
limited independence probability spaces [NN93, AGHP92].

###  1.2 Hopsets

As was mentioned above, our algorithm for $(1+\epsilon)$-SSSP is based on a
novel deterministic PRAM NC algorithm for building hopsets. To our knowladge,
our algorithm is the first NC algorithm for building hopsets with work smaller
than $n^{\omega}$.

Given a graph $G=(V,E,\omega)$ and a pair of parameters $\epsilon>0$ and
$\beta=1,2,\dots,$ a graph $G^{\prime}=(V,H,\omega^{\prime})$ is said to be a
_$(1+\epsilon,\beta)$ -hopset_ for $G$ if for every pair of vertices $u,v\in
V$, we have

$\displaystyle d_{G}(u,v)\leq d_{G\cup
G^{\prime}}^{(\beta)}(u,v)\leq(1+\epsilon)d_{G}(u,v).$ (1)

Here $d_{G\cup G^{\prime}}^{(\beta)}(u,v)$ stands for the _$\beta$ -bounded
$u-v$ distance_ in $G\cup G^{\prime}$, i.e., the length of the shortest $u-v$
path in $G\cup G^{\prime}$ that contains at most $\beta$ edges. The parameter
$\beta$ is called the _hopbound_ of the hopset $G^{\prime}$.

Cohen [Coh94] devised a randomized PRAM algorithm that for any parameters
$\epsilon,\rho>0$, and for any $n$-vertex, weighted graph $G=(V,E,\omega)$,
builds a $\left(1+\epsilon,\beta_{Coh}=({\log
n})^{O(\frac{1}{\rho}{\log\frac{1}{\rho}})}\right)$-hopset with
$\tilde{O}(n^{1+\rho})$ edges, in $\tilde{O}(\beta_{Coh})$ time, and using
$\tilde{O}(|E|\cdot n^{\rho})$ work. Her algorithm is based on _pairwise
covers_ , and Cohen [Coh94] remarked that a deterministic NC algorithm that
constructs the latter would suffice for derandomizing her hopset construction.
However, more than quarter a century after Cohen’s work [Coh94], still no
efficient parallel deterministic procedure for building these covers is known.

Elkin and Neiman [EN19] devised a different randomized algorithm with
polylogarithmic depth for constructing hopsets. In their algorithm222Their
algorithm also gave rise to first constructions of hopsets with constant
hopbound $\beta$. However, this property is of little help for the _single-
source_ shortest paths problem., $\beta_{EN}=({\log n})^{O(1/\rho)}$,
improving $\beta_{Coh}=({\log n})^{O(\frac{1}{\rho}{\log\frac{1}{\rho}})}$.
The algorithm of [EN19] is based on the _superclustering-and-interconnection_
approach, originated in the work of Elkin and Peleg [EP01] on near-additive
spanners. In this approach, one identifies dense areas of the graph, i.e.,
areas that contain many clusters, and builds from them superclusters. The
remaining clusters are then interconnected, i.e., shortest paths between them
are inserted into the hopset.

To implement their approach efficiently in PRAM, [EN19] used random sampling.
Dense areas are more likely to be sampled, and as a result superclustered. In
the current paper we show that the sampling step can be replaced by carefully
constructed _ruling sets_. For a pair of parameters $\alpha,\gamma\geq 1$, a
set $U\subset V$ is said to be an _$(\alpha,\gamma)$ -ruling set_ for a set
$\widehat{U}\subseteq V$, if the following two conditions hold:

  1. 1.

For every $u,v\in U$, $d_{G}(u,v)\geq\alpha$.

  2. 2.

For every $\widehat{u}\in\widehat{U}$, there exists a vertex $u\in U$ with
$d_{G}(u,\widehat{u})\leq\gamma$.

Ruling sets are long known to be a key derandomization tool in distributed
algorithms [GPS88, AGLP89]. As long as $\gamma=\Omega(\alpha\cdot{\log n})$,
they can be efficiently constructed in parallel and distributed models
[GPS88]. We show that such ruling sets are sufficient for constructing
hopsets. Note that these ruling sets are applicable for unweighted graphs,
while hopsets are built for weighted graphs. Our algorithm builds appropriate
unweighted cluster graphs, and constructs ruling sets for them. As a result,
we derandomize the result of [EN19], and devise a deterministic NC algorithm
that for any constant parameters $\rho,\epsilon>0$, and any $n$-vertex graph
$G=(V,E,\omega)$, constructs a $(1+\epsilon,\beta=\beta_{EN})$-hopset $H$ with
$\tilde{O}(n^{1+\rho})$ edges, in time $\tilde{O}(\beta_{EN})=({\log
n})^{O(1/\rho)}$, and using work $\tilde{O}(|E|\cdot n^{\rho})$. Once the
hopset is constructed, we conduct a Bellman-Ford exploration in the graph
union the hopset $H$ to depth $\beta$. This exploration requires additional
time $\tilde{O}(\beta)$, and work complexity $\tilde{O}(|V|+|H|)$. Both are
dominated by the respective complexities of constructing the hopset $H$.

In addition to its main application to the $(1+\epsilon)$-SSSP problem, our
deterministic algorithm for constructing hopsets has other applications. In
particular, recently Elkin and Neiman [EN20] devised a PRAM algorithm with
polylogarithmic depth that computes $(1+\epsilon)$-approximate shortest paths
from all pairs in $S\times V$, for a set $S$ of at most $n^{0.313...}$ sources
using $\tilde{O}(n^{2})$ work. (They actually have a tradeoff between the
number of sources and running time. See [EN20] for more details.) This
algorithm relies on an efficient computation of a suitable hopset. In
conjunction with the deterministic construction of hopsets that we devise in
the current paper, the algorithm of [EN20] can be made deterministic. Yet
another possible application of our deterministic algorithm for constructing
hopset can be found in [EGN19]. That algorithm is for the same problem of
computing paths for all pairs $(s,v)\in S\times V$ as above, but this time
allowing both multiplicative error of $(1+\epsilon)$ and an additive error of
$\beta\cdot W(s,v)$, where $\beta$ is a large constant that depends on
$\epsilon$ and on some other parameters, but is independent of $n$, and
$W(s,v)$ is the weight of the heaviest edge on a shortest $s-v$ path. It has
polylogarithmic depth and work roughly $\tilde{O}(|E|+|S|\cdot n)$. It has two
randomized ingredients, one of which is an algorithm for constructing a hopset
and another one is an algorithm for constructing a near-additive weighted
spanner. Our algorithm in the current paper can be plugged there. Once the
other ingredient (i.e., the construction of weighted near-additive spanner) is
derandomized (and it is plausible that this can be accomplished via ideas
similar to ones that we develop here), one would obtain a deterministic
counterpart of the result of [EGN19]. To summarize, our deterministic PRAM NC
algorithm for building hopsets is valuable on its own right, and we believe
that additional applications of it will be found in future.

###  1.3 Path-Reporting Hopsets

Our additional contribution is in devising a _path-reporting_ variant of our
hopsets. The basic variant of our hopset construction enables one to compute
approximate distances, but not paths that implement these distances.

Elkin and Neiman [EN18, EN19] devised a different implicit mechanism for
making their hopset path-reporting. Their hopset enables, upon a query $u,v$,
to retrieve a $(1+\epsilon)$-approximate shortest path $P_{u,v}$ in $G$
between $u$ and $v$ in $O({\log n})$ PRAM time and $\tilde{O}(|P_{u,v}|)$
work. Their algorithm however cannot retrieve the entire
$(1+\epsilon)$-Shortest-Path-Tree (henceforth, SPT) within the desired
resource bounds. (See the discussion at the beginning of Section 5.4 of
[EN19].)

Our new path-reporting mechanism enables us to compute a $(1+\epsilon)$-SPT in
$G$ in polylogarithmic time and slightly super-linear work. This mechanism can
be used also in conjunction with previous randomized algorithms for building
hopsets [Coh94, EN18, EN19]. It simplifies the respective path-reporting
variant of these hopsets, and more importantly, makes them _explicit_. We
believe that this mechanism is of independent interest.

We next shortly outline it. Our hopset is a union of logarithmically many
single-scale hopsets333Informally, a single-scale hopset $H_{k}$ for a scale
$k$ is a hopset that takes care of pairs of vertices $u,v$ such that
$d_{G}(u,v)\in(2^{k},2^{k+1}]$. See Section 2 for more details.. Moreover,
each edge $e=(u,v)$ in a scale-$k$ hopset $H_{k}$, for some $k\geq 2$, is
implemented by at most $\beta=polylog(n)$ edges that either belong to the
scale-$(k-1)$ hopset $H_{k-1}$, or to the original graph $G$. In our
algorithm, we store for every edge $(u,v)\in H_{k}$ a path $P^{(k-1)}_{u,v}$
between $u$ and $v$ in $G\cup H_{k-1}$. This increases our storage by just a
polylogarithmic factor. When we need to retrieve paths (e.g., when building an
approximate SPT), we conduct a _peeling_ process. First, we replace all hopset
edges of the highest scale-$\lambda$ by edges of the original graph $G$ and of
the scale-$(\lambda-1)$. Then we replace the latter by hopset edges of
scale-$(\lambda-2)$, etc., up until all hopset edges are eliminated. This
results in a polylogarithmic overhead (of $\tilde{O}(\beta)$) in the total
work.

This peeling process becomes far more elaborate when one combines it with the
weight reduction of [KS92, Coh94, EN19]. The latter reduction eliminates the
dependency on the maximum edge weight from our results. From the technical
viewpoint, it creates graphs
$\mathcal{G}^{1},\mathcal{G}^{2},\dots,\mathcal{G}^{\lambda}$, each of which
is obtained from the original graph by contracting some edges, and grouping
some sets of vertices into _nodes_.

To construct a $(1+\epsilon)$-SPT for the original graph $G$, our algorithm
first computes a $(1+\epsilon)$-SPT in $G$ union the hopset, which in turn is
the union of hopset
$\mathcal{H}^{1},\mathcal{H}^{2},\dots,\mathcal{H}^{\lambda}$ of all these
graphs $\mathcal{G}^{1},\mathcal{G}^{2},\dots,\mathcal{G}^{\lambda}$. Each of
the latter hopsets contains edges between the nodes, and also, for every node
$\widehat{v}$ it contains (the so called ”star”) edges between its center $v$
and each other vertex $u\in\widehat{v}$. During the peeling process, we
carefully replace the star edges by paths in $G$, and hopset edges
$(\widehat{v}_{1},\widehat{v}_{2})$ between nodes $\widehat{v}_{1}$ and
$\widehat{v}_{2}$ by paths between their respective centers $v_{1}$ and
$v_{2}$ in $G$. In addition, we also find appropriate portal vertices
$v_{1}^{\prime}$ and $v_{2}^{\prime}$ in $\widehat{v}_{1}$ and
$\widehat{v}_{2}$, respectively, that enable us to integrate the path in our
final $(1+\epsilon)$-SPT for $G$, and connect the centers $v_{1}$ and $v_{2}$
to their respective portals.

###  1.4 Related Work

Improved randomized constructions of hopsets, which are based on Thorup-Zwick
[TZ01, TZ06] sampling hierarchy, were devised in [EN17b, HP19]. Existential
lower bounds on hopsets were shown in [ABP17].

Henzinger et al. [HKN16] devised a distributed deterministic algorithm for
building hopsets. However, the hopbound of their hopset is $2^{O(\sqrt{{\log
n}{\log{\log n}}})}$, and not at most polylogarithmic in $n$, as that of
hopsets of [Coh94, EN19, EN17b] and of our hopset. As a result, any PRAM
algorithm that would use their hopset is doomed to use at least this running
time (of $2^{O(\sqrt{{\log n}{\log{\log n}}})}$), while we achieve a
polylogarithmic running time.

Also, the current authors [EM19] used ruling sets to derandomize the
superclustering-and-interconnection approach of [EP01, EN17a] in the context
of near-additive spanners for unweighted graphs in the distributed CONGEST
model. The running time of the algorithm of [EM19] is $O(n^{\rho})$, for an
arbitrarily small parameter $\rho>0$. Our current work follows the same
approach, but does so in a far more complicated setting of hopsets for
weighted graphs, and in a more restrictive PRAM model. Also, the running time
of our current algorithm is polylogarithmic in $n$, as apposed to the
polynomial time in [EM19].

Finally, hopsets were found extremely useful for dynamic algorithms for
approximate shortest paths problems [Ber09, BR11, HKN16]. We believe that the
techniques that we developed for our new deterministic algorithm for building
hopsets will be useful in this context as well.

###  1.5 Preliminaries

Let $G=(V,E,\omega)$ be a weighted, undirected graph on $n$ vertices, where
the minimal edge weight is $1$. If $(u,v)\notin E$, then $\omega(u,v)=\infty$.
For convenience, we assume that each vertex $v\in V$ has a unique ID in the
range $\\{0,1,\dots,n-1\\}$. We also assume that $n$ is a power of $2$. This
assumption does not affect our ultimate result.

Throughout the algorithm, we construct clusters. Each cluster $C$ is centered
around a designated center $r_{C}\in C$. The ID of the cluster $C$ is the ID
of its center $r_{C}$. For a pair of clusters $C,C^{\prime}$ in a graph $X$
let $d^{(h)}_{X}(C,C^{\prime})={\min\\{d^{(h)}_{X}(u,u^{\prime})\ |\ u\in C\
and\ u^{\prime}\in C^{\prime}\\}}$, where $h$ is a hopbound. If $h$ is not
specified, then the hopbound is not bounded, i.e.,
$d_{X}(C,C^{\prime})=d^{(\infty)}_{X}(C,C^{\prime})$.

Denote by $\Lambda$ the aspect ratio of the graph, i.e., the ratio between the
largest and the smallest distance in $G$. In the main part of this paper we
will assume that $\Lambda=n^{O(1)}$. In Appendix C we argue that using Klein-
Sairam’s weight reduction [KS97], one can get rid of this assumption.

Throughout the paper, when the logarithm base is unspecified, it is equal to
$2$. For a pair of integers $i,j,$ where $i\leq j$, the notation $[i,j]$
stands for $\\{i,i+1,\dots,j\\}$.

#### 1.5.1 The Computation Model

We consider the concurrent-read-exclusive-write (CREW) PRAM model (see, e.g.,
[JáJ92]), in which all processors work in synchronous rounds. In every round,
each processor either writes to some memory cell associated with it, reads
some memory cell or stays idle. Concurrent read is allowed, but only one
processor can write to each cell in every round. To avoid access conflicts,
vertices write on odd rounds and read on even rounds. The running time of the
algorithm is the number of rounds that the algorithm requires, also referred
to as the depth of the algorithm. The work of the algorithm is the number of
read and write operations executed by all processors throughout the algorithm.
A trivial upper bound on the work of the algorithm is the running time,
multiplied by the number of processors.

We aim at using roughly $O(|E|\cdot n^{\rho})$ processors, for some parameter
$0<\rho<1/2$. Every vertex and edge in the graph are simulated by
$O(n^{\rho})$ processors, and each processor is associated with $O(1)$ memory
cells. Every cluster $C$ constructed by the algorithm is simulated by its
center $r_{C}$. That is, the processors and memory of $r_{C}$ are utilized for
the simulation of the cluster $C$. Throughout our algorithm, we add edges to a
hopset $H$. Every edge that is added to the hopset is also allocated
$O(n^{\rho})$ processors. For every edge $(u,v)\in E\cup H$, the processors
$p^{\langle u,v\rangle}_{1},p^{\langle u,v\rangle}_{1},\dots,p^{\langle
u,v\rangle}_{n^{\rho}}$ and $p^{\langle v,u\rangle}_{1},p^{\langle
v,u\rangle}_{1},\dots,p^{\langle v,u\rangle}_{n^{\rho}}$ simulate the
(directed) edges $\langle u,v\rangle,\langle v,u\rangle$, respectively.

###  1.6 Outline

Section 2 contains the details of our construction of hopsets. In Section 3 we
analyze the properties of the resulting hopset and the computational
complexity of the algorithm, which are then summarized in Theorems 3.7 and
3.8. Section 4 contains a path-reporting hopset construction. Its properties
are summarized in Theorem 4.6.

Appendix A contains a PRAM implementation of a BFS exploration in a virtual
graph that is used by our algorithm. Appendix B contains a PRAM implementation
of the algorithm of [AGLP89, SEW13, KMW18] for constructing ruling sets. In
Appendices C and D we argue that the dependence of our results on the aspect
ratio can be eliminated. These results are summarized in Theorem C.2 and D.1,
respectively.

Bibliography appears after the appendix.

##  2 The Algorithm

In this section, we provide the details of the construction. The input for our
algorithm is an undirected, weighted graph $G=(V,E,\omega)$, where
$\omega(e)>0$ for all $e\in E$, and parameters $0<\epsilon<1/10$,
$\kappa=1,2,\dots$ and $0<\rho<1/2$. The parameter $\kappa$ governs the
sparsity of the hopset and $\rho$ governs the work complexity. The hopbound
parameter $\beta$ is a function of $n,\Lambda,\epsilon,\kappa,\rho$ (recall
that $\Lambda$ stands for the aspect ratio of the graph), and is given by

$\beta=O\left(\frac{{\log{\Lambda}}{\log
n}({\log\kappa\rho}+1/\rho)}{\epsilon}\right)^{\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1}.$
(2)

Let $G=(V,E,\omega)$ be a weighted, undirected graph, with aspect ratio
$\Lambda$. Let $k=0,1,\dots,\lceil{\log\Lambda}\rceil$. A set of edges $H_{k}$
with weights given by the weight function $\omega_{H_{k}}$ is said to be a
_$(1+\epsilon,\beta)$ -hopset for the scale_ $k$ if for every pair of vertices
$u,v$ with $d_{G}(u,v)\in(2^{k},2^{k+1}]$ we have that:

$d_{G}(u,v)\leq d^{(\beta)}_{G_{k}}(u,v)\leq(1+\epsilon)d_{G}(u,v),$

where $G_{k}=(V,E\cup H_{k},\omega_{k})$ and
$\omega_{k}(u,v)={\min\\{\omega(u,v),\omega_{H_{k}}(u,v)\\}}$ for every edge
$(u,v)\in E\cup H_{k}$.

The algorithm constructs a separate hopset $H_{k}$ for every scale
$(2^{0},2^{1}],(2^{1},2^{2}],\dots,(2^{\lceil{\log\Lambda}\rceil-1},2^{\lceil{\log\Lambda}\rceil}]$.
Note that for $k\leq\left\lfloor{\log{\beta}}\right\rfloor-1$, we can set
$H_{k}=\emptyset$. This is since $2^{k+1}\leq\beta$, and thus for each pair of
vertices $u,v\in V$ with $d_{G}(u,v)\leq 2^{k+1}$, the original graph $G$
already contains a shortest path between $u,v$ that uses at most $\beta$
edges. In other words, $d_{G}(u,v)=d^{(\beta)}_{G}(u,v)$. Denote
$k_{0}=\left\lfloor{\log{\beta}}\right\rfloor$ and
$\lambda=\lceil{\log\Lambda}\rceil-1$. We construct a hopset $H_{k}$ for every
$k\in[k_{0},\lambda]$.

During the construction of a hopset $H_{k}$, for some $k\geq k_{0}$, we will
need to conduct explorations from certain vertices to depth $\delta\leq
2^{k+1}$. Therefore, we use the $(1+\epsilon_{k-1},\beta)$-hopset $H_{k-1}$
for the scale $(2^{k-1},2^{k}]$ in the construction of $H_{k}$. The value of
$\epsilon_{k-1}$ will be determined in the sequel.

Instead of conducting explorations from the vertex $u\in V$ to depth $\delta$
in the original graph $G$, we conduct the explorations from $u$ to depth
$(1+\epsilon_{k-1})\delta$ and $(2\beta+1)$ hops in the graph $G_{k-1}$. The
following lemma shows that the exploration executed in $G_{k-1}$ will reach
all vertices that are within distance up to $\delta$ from $u$ in the original
graph $G$. (This lemma is analogous to Lemma 3.9 in [EN19].) We will later
show that distances in $G_{k-1}$ are never shorter than those in the original
graph $G$, i.e., that for every pair of vertices $u,v\in V$ we have
$d_{G}(u,v)\leq d_{G_{k-1}}(u,v)$.

######  Lemma 2.1.

Let $u\in V$, and let $v$ be a vertex such that $d_{G}(u,v)\leq 2^{k+1}$.
Then,

$d^{(2\beta+1)}_{G_{k-1}}(u,v)\leq(1+\epsilon_{k-1})d_{G}(u,v).$

###### Proof.

Let $\pi(u,v)=(u=u_{0},u_{1},\dots,u_{t}=v)$ be a shortest path in $G$ between
$u,v$. Let $u_{j}$ be the last vertex on $\pi(u,v)$ such that
$d_{G}(u,u_{j})\leq 2^{k}$. Then, $d_{G}(u,u_{j+1})>2^{k}$. See Figure 1 for
an illustration. Note that the length of $\pi(u,v)$ is at most $2^{k+1}$. It
follows that since $j$ is the maximal index such that $d_{G}(u,u_{j})\leq
2^{k}$, we have $d_{G}(u_{j+1},v)\leq 2^{k}$. Hence we conclude that

$d^{(\beta)}_{G_{k-1}}(u,u_{j})\leq(1+\epsilon_{k-1})d_{G}(u,u_{j})\qquad\text{and}\qquad
d^{(\beta)}_{G_{k-1}}(u_{j+1},v)\leq(1+\epsilon_{k-1})d_{G}(u_{j+1},v).$

Let $\pi(u,u_{j})$ and $\pi(u_{j+1},v)$ be the shortest $\beta$-hop limited
paths in $G_{k-1}$ from $u$ to $u_{j}$ and $u_{j+1}$ to $v$, respectively.

Figure 1: The path in $G_{k-1}$ from $u$ to $v$. The straight line represents
a shortest path from $u$ to $v$ in the original graph $G$. The curved lines
represent the paths in $G_{k-1}$ from $u$ to $u_{j}$ and $u_{j+1}$ to $v$ of
length at most $(1+\epsilon_{k-1})d_{G}(u,u_{j})$ and
$(1+\epsilon_{k-1})d_{G}(u_{j+1},v)$, respectively. Each of them consists of
at most $\beta$ edges. The thick line depicts the edge $(u_{j},u_{j+1})$ from
the graph $G$. By concatenating the path of $\beta$ edges from $u$ to $u_{j}$
with the edge $(u_{j},u_{j+1})$ and the path of $\beta$ edges from $u_{j+1}$
to $v$, we obtain a path with at most $2\beta+1$ hops, of length at most
$(1+\epsilon_{k-1})d_{G}(u,v)$.

In addition, the graph $G_{k-1}$ also contains the edge $(u_{j},u_{j+1})$.
Then, by concatenating the path $\pi(u,u_{j})$ with the edge $(u_{j},u_{j+1})$
and the path $\pi(u_{j+1},v)$, we obtain a path of at most $2\beta+1$ hops and
length at most $(1+\epsilon_{k-1})d_{G}(u,v)$. It follows that

$d^{(2\beta+1)}_{G_{k-1}}(u,v)\leq(1+\epsilon_{k-1})d_{G}(u,v).$

∎

###  2.1 Constructing $H_{k}$

We are now ready to discuss the construction of a hopset $H_{k}$, for some
$k\in[k_{0},\lambda]$. The algorithm works in phases. The input for each phase
$i\in[0,\ell]$ is a collection of clusters $P_{i}$, a degree threshold
parameter $deg_{i}$ and a distance threshold parameter $\delta_{i}$. The
parameters $\ell,\\{deg_{i},\delta_{i}\ |\ i\in[0,\ell]\\}$ will be specified
in the sequel. For phase $0$, the input $P_{0}$ is the partition of $V$ into
singleton clusters, i.e., $P_{0}=\\{\\{u\\}\ |\ u\in V\\}$.

Our algorithm uses the _superclustering-and-interconnection_ approach (see,
e.g., [EP01, EN17a, EN17b, EN19, EM19]). Generally speaking, in every phase
$i$, we define clusters that have many other clusters in their vicinity as
popular. Popular clusters are grouped into superclusters, which become the
input for the next phase. Clusters that have not been superclustered in this
phase are interconnected with the clusters in their vicinity. The set of
superclusters is the input collection for the next phase. Intuitively, this
approach allows us to defer work on dense areas of the graph to later phases
of the algorithm.

Recall that
$d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})={\min\\{d^{(2\beta+1)}_{G_{k-1}}(u,u^{\prime})\
|\ u\in C\ and\ u^{\prime}\in C^{\prime}\\}}$. Formally, a pair of clusters
$C,C^{\prime}\in P_{i}$ are said to be neighbors (or, equivalently,
_neighboring clusters_) if
$d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})\leq(1+\epsilon_{k-1})\delta_{i}$. For
a cluster $C\in P_{i}$, define

$\Gamma(C)=\\{C^{\prime}\ |\
d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})\leq(1+\epsilon_{k-1})\delta_{i},\ C\neq
C^{\prime}\\}.$

A cluster $C\in P_{i}$ and its center are called popular if $|\Gamma(C)|\geq
deg_{i}$. Otherwise, they are called unpopular.

Each phase $i$ is divided into two steps. In the superclustering step of phase
$i$, popular clusters are detected, and are grouped into superclusters. The
set of new superclusters becomes the input of the next phase, i.e., it is the
set $P_{i+1}$. Let $U_{i}$ be the set of clusters from $P_{i}$ that have not
been superclustered in this phase. In the interconnection step of phase $i$,
clusters in $U_{i}$ are interconnected with their neighboring clusters that
are also in $U_{i}$. For the last phase $\ell$, we will ensure that the number
of clusters in $P_{\ell}$ is at most $deg_{\ell}$. Therefore, in this phase
there will be no popular clusters, and thus the superclustering step will be
skipped.

We now set the parameters $\\{deg_{i},\delta_{i}\ |\ i\in[0,\ell]\\},\ell$.
The degree parameter $deg_{i}$ determines the number of edges added in the
interconnection step of phase $i$. In addition, the degree parameter
determines how many clusters of $P_{i}$ are necessary to construct a
supercluster in phase $i$, and thus determines also the number of phases of
the algorithm. To achieve a polylogarithmic running time, the algorithm uses
$\Theta(deg_{i})$ processors to simulate each vertex and each edge in phase
$i$. Since we aim at using $O(n^{\rho})$ processors to simulate each edge and
vertex, we divide the phases into an exponential growth stage and a fixed
growth stage444Recall that $\kappa$ and $\rho$ are input parameters of our
algorithm. We assume $0<\rho<1/2$.. Set
$\ell=\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1$.
For the exponential growth stage, that consists of phases
$i\in[0,i_{0}=\lfloor{\log\kappa\rho}\rfloor]$, we set
$deg_{i}=n^{\frac{2^{i}}{\kappa}}$. For the fixed growth stage, that consists
of phases $i\in[i_{1}=i_{0}+1,\ell]$, we set $\deg_{i}=n^{\rho}$.

For the distance parameter, for every $i\in[0,\ell]$ set
$\delta_{i}=\alpha\cdot\left({1}/{\epsilon}\right)^{i}$, where
$\alpha=\epsilon^{\ell}\cdot 2^{k+1}$.

Let $C\in P_{i}$ be a cluster centered around a vertex $r_{C}\in C$. The
radius of $C$ is defined to be $Rad(C)=\max\\{d^{(i)}_{G_{k}}(r_{C},v)\ |\
v\in C\\}$. For the collection $P_{i}$, define

$Rad(P_{i})=\max\\{Rad(C)\ |\ C\in P_{i}\\}.$ (3)

Define recursively $R_{0}=0$, and
$R_{i+1}=(2(1+\epsilon_{k-1})\delta_{i}+4R_{i}){\log n}+R_{i}$. We will show
that for all $i\in[0,\ell]$, we have $Rad(P_{i})\leq R_{i}$ (see Lemma 2.2).

#### 2.1.1 Superclustering

This section contains the details of the superclustering step for each phase
$i\in[0,\ell-1]$. Recall that on phase $\ell$, the superclustering step is
skipped. Let $\tilde{G}_{i}=(P_{i},\tilde{E})$ be an unweighted virtual graph
where $\tilde{E}=\\{(C,C^{\prime})\ |\
d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})\leq(1+\epsilon_{k-1})\delta_{i}\\}$. In
other words, the graph $\tilde{G}_{i}$ is the graph on the set of
supervertices (clusters) $P_{i}$, that contains an edge for every pair of
neighboring clusters in $P_{i}$. Note that the edges of the virtual graph
$\tilde{G}_{i}$ are not necessarily known to the processors.

The superclustering step of phase $i$ begins by detecting the popular
clusters, i.e., the clusters that have at least $deg_{i}$ edges incident to
them in the graph $\tilde{G}_{i}$. This is done by a simulation of $deg_{i}+1$
parallel BFS explorations executed from all supervertices (clusters) in
$\tilde{G}_{i}$ to depth $1$ in the virtual graph $\tilde{G}_{i}$. When the
explorations terminate, each cluster $C\in P_{i}$ is associated with an array
$m(C)$ that contains IDs of neighboring clusters of $C$. If the cluster $C$
has at least $deg_{i}$ neighboring clusters in $P_{i}$, this array will
contain information regarding at least $deg_{i}$ of these clusters. Otherwise,
the array $m(C)$ will contain the IDs and $(2\beta+1)$-hop bounded distance in
$G_{k-1}$ to all the neighbors $C^{\prime}$ of $C$. In other words, for every
cluster $C^{\prime}\in\Gamma(C)$, the cluster $C$ will know the ID of
$C^{\prime}$ as well as the distance $d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})$.

To implement these explorations, we use Algorithm 2, described in Appendix A.
Its properties are summarized in Lemma A.3.

Lemma A.3 Given a weighted undirected graph $G_{k-1}=(V,E\cup
H_{k-1},\omega_{k-1})$ on $n$ vertices, a set of clusters $P_{i}$, distance
parameter $(1+\epsilon_{k-1})\delta_{i}$, degree parameter $deg_{i}$ and a
hopbound $2\beta+1$, Algorithm 2 requires $O(\beta{\log n})$ time and
$O((|E|+|H_{k-1}|)\cdot n^{\rho})$ processors. When the algorithm terminates,
every cluster $C\in P_{i}$ is associated with an array $m(C)$ such that:

  1. 1.

If $C$ is popular, then the first $deg_{i}+1$ cells of $m(C)$ contain
information regarding $deg_{i}+1$ clusters from $P_{i}$. One of them is $C$,
and the other are neighboring clusters of $C$.

  2. 2.

If $C$ is _unpopular_ then $m(C)$ contains the identities and $(2\beta+1)$-hop
bounded distances in $G_{k-1}$ between $C$ and all its neighboring clusters.
In addition, the $(deg_{i}+1)$st cell in $m(C)$ is empty.

When the algorithm terminates, each center $r_{C}$ of a cluster $C\in C$
checks weather the $(deg_{i}+1)$st cell in $m(C)$ is empty or not. If it is
not empty, then $C$ is marked as popular. Otherwise, it is marked unpopular.

Let $W_{i}$ be the set of popular clusters. A subset $Q_{i}\subseteq W_{i}$ is
selected to grow superclusters around. This is done in order to ensure that
the number of superclusters formed in phase $i$ is significantly smaller than
the number of clusters in $P_{i}$.

To select the set $Q_{i}$, a $(3,2{\log n})$-ruling set for $W_{i}$ with
respect to (henceforth, w.r.t.) the graph $\tilde{G}_{i}$, is computed using
the algorithm of [AGLP89, SEW13, KMW18]. The implementation of the algorithm
in the PRAM CREW model and its analysis are given in Appendix B. The following
corollary summarizes the properties of the set $Q_{i}$.

Corollary B.4 Given a weighted undirected graph $G_{k-1}=(V,E\cup
H_{k-1},\omega_{k-1})$ on $n$ vertices, a set of clusters $P_{i}$, a distance
parameter $(1+\epsilon_{k-1})\delta_{i}$, and a hopbound $2\beta+1$, Algorithm
4 uses $O(|E|+|H_{k-1}|)$ processors and $O(\beta{\log^{2}n})$ time, and
returns a $(3,2{\log n})$-ruling set $Q_{i}$ for the set $W_{i}$ w.r.t. the
graph $\tilde{G}_{i}=(P_{i},\tilde{E})$, where $\tilde{E}=\\{(C,C^{\prime})\
|\ d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})\leq(1+\epsilon_{k-1})\delta_{i}\\}$.

To cover all popular clusters, a BFS exploration to depth $2{\log n}$ in the
graph $\tilde{G}_{i}$ is simulated from all clusters in $Q_{i}$, using
Algorithm 2. The details of the execution of this exploration, as well as the
pseudocode of Algorithm 2, are given in Appendix A.

Each cluster $C\in P_{i}$ that is detected by the exploration that has
originated in a cluster $C^{\prime}\in Q_{i}$ becomes superclustered into the
supercluster $\widehat{C}^{\prime}$ formed around $C^{\prime}$. The center $r$
of the cluster $C$ adds to the hopset $H_{k}$ an edge to the center
$r^{\prime}$ of the cluster ${C}^{\prime}$, and sets
$\omega_{H_{k}}(r,r^{\prime})=2((1+\epsilon_{k-1})\delta_{i}+2R_{i}){\log n}$.
The new edge is allocated $O(n^{\rho})$ new processors. We show in Lemma 2.3
that superclustering edges do not shorten distances with respect to the
original graph $G$.

For each new supercluster $\widehat{C}^{\prime}$ formed around a cluster
$C^{\prime}\in Q_{i}$, its center is set to be the center of the cluster
$C^{\prime}$. The supercluster $\widehat{C}^{\prime}$ contains all the
vertices that belonged to $C^{\prime}$, as well as all the vertices that
belonged to other clusters that have been superclustered into
$\widehat{C}^{\prime}$. The input collection for the next phase $P_{i+1}$ is
set to be the set of new superclusters.

The following lemmas summarize the properties of the superclusters formed in
phase $i$. Recall that the $i$-hop bounded radius of a cluster $C\in P_{i}$ in
the graph $G_{k}$ is defined by eq. 3 to be
$Rad(C)=\max\\{d^{(i)}_{G_{k}}(r_{C},v)\ |\ v\in C\\}$, and that the radius of
$P_{i}$ is set to be $Rad(P_{i})=\max\\{Rad(C)\ |\ C\in P_{i}\\}$. Define
recursively $\sigma_{0}=0$ and $\sigma_{i+1}=(4{\log
n}+1)\sigma_{i}+2(2\beta+1){\log n}$, for all $i\in[1,\ell]$. Note that the
sequence $(\sigma_{i}\ |\ i=0,1,\dots)$ is monotonically increasing. For every
cluster $C\in P_{i}$ centered around a vertex $r_{C}$, define the
$\sigma_{i}$-bounded radius of the cluster $C$ in the graph $G_{k-1}$ to be

$Rad^{(\sigma_{i})}_{k-1}(C)=\max\\{d^{(\sigma_{i})}_{G_{k-1}}(r_{C},v)\ |\
v\in C\\}.$

For the collection $P_{i}$, define
$Rad^{(\sigma_{i})}_{k-1}(P_{i})=\max\\{Rad^{(\sigma_{i})}_{k-1}(C)\ |\ C\in
P_{i}\\}$. Also recall that $R_{0}=0$ and
$R_{i+1}=(2(1+\epsilon_{k-1})\delta_{i}+4R_{i}){\log n}+R_{i}$ for all
$i\in[0,\ell]$. The following lemma provides upper bounds for $Rad(P_{i})$ and
$Rad^{(\sigma_{i})}_{k-1}(P_{i})$.

######  Lemma 2.2.

For $i\in[0,\ell]$, we have $Rad(P_{i})\leq R_{i}$ and also
$Rad^{(\sigma_{i})}_{k-1}(P_{i})\leq R_{i}$.

###### Proof.

The proof is by induction on the index of the phase $i$. For $i=0$, all
clusters in $P_{i}$ are singletons and so
$Rad(P_{i})=Rad^{(\sigma_{i})}_{k-1}(P_{i})=0$, and also, by definition,
$R_{0}=0$.

Assume that the claim holds for some $i\in[0,\ell-1]$ and prove it for $i+1$.
Let $\widehat{C}$ be a cluster in $P_{i+1}$, centered around a vertex $r_{C}$.
Observe that $\widehat{C}$ was constructed around a cluster $C\in P_{i}$ (also
centered around $r_{C}$) during phase $i$. Let $u\in\widehat{C}$. The analysis
splits into two cases.

Case 1: The vertex $u$ is in $C$. By the induction hypothesis, we have
$d_{G_{k}}^{(i)}(r_{C},u)\leq R_{i}$ and
$d_{G_{k-1}}^{(\sigma_{i})}(r_{C},u)\leq R_{i}$. Therefore,
$d_{G_{k}}^{(i+1)}(r_{C},u)\leq R_{i}\leq R_{i+1}$, and
$d_{G_{k-1}}^{(\sigma_{i+1})}(r_{C},u)\leq
d_{G_{k-1}}^{(\sigma_{i})}(r_{C},u)\leq R_{i}\leq R_{i+1}$. Thus the claim
holds.

Figure 2: The path in $G_{k-1}$ from $r_{C}$ to $u$. The white circles
represent the clusters along the path $P$. The squares represent cluster
centers. The solid curved lines represent paths in $G_{k-1}$ from a center of
a cluster to a vertex in the cluster. The dashed lines depict paths of at most
$2\beta+1$ hops in $G_{k-1}$ between neighboring clusters.

Case 2: The vertex $u$ belongs to a cluster $C^{\prime}\in P_{i}$, where
$C^{\prime}\neq C$. Let $r_{C^{\prime}}$ be the center of the cluster
$C^{\prime}$. Since $u\in\widehat{C}$, we have that the cluster $C^{\prime}$
was detected by the exploration to depth $2{\log n}$ in the graph
$\tilde{G}_{i}$ that originated in $C$. It follows that an edge
$(r_{C},r_{C^{\prime}})$ was added to $H_{k}$. The weight of the edge is
$2((1+\epsilon_{k-1})\delta_{i}+2R_{i}){\log n}$. By the induction hypothesis,
we have that $d^{(i)}_{G_{k}}(r_{C^{\prime}},u)\leq R_{i}$. It follows that
$d^{(i+1)}_{G_{k}}(r_{C},u)\leq 2((1+\epsilon_{k-1})\delta_{i}+2R_{i}){\log
n}+R_{i}=R_{i+1}$, and therefore we have that $Rad(\widehat{C})\leq R_{i+1}$.

Let $P=\\{C=C_{0},C_{1},\dots,C_{t}=C^{\prime}\\}$ be the shortest path from
$C$ to $C^{\prime}$ in the (unweighted) virtual graph $\tilde{G}_{i}$. Observe
that $t\leq 2{\log n}$. For every $j\in[0,t-1]$, let $x_{j}\in C_{j}$ and
$y_{j+1}\in C_{j+1}$ be the vertices such that
$d^{(2\beta+1)}_{G_{k-1}}(x_{j},y_{j+1})$ is minimal. See Figure 2 for an
illustration. By definition of $\tilde{G}_{i}$, for every $j\in[0,t-1]$, we
have
$d^{(2\beta+1)}_{G_{k-1}}(x_{j},y_{j+1})\leq(1+\epsilon_{k-1})\delta_{i}$. For
every cluster $C_{j}$ along the path $P$, denote by $r_{j}$ its center. By the
induction hypothesis, for every $j\in[0,t-1]$ we have
$d^{(\sigma_{i})}_{G_{k-1}}(r_{j},x_{j})\leq R_{i}$, and for every $j\in[1,t]$
we have $d^{(\sigma_{i})}_{G_{k-1}}(r_{j},y_{j})\leq R_{i}$. It follows that

$\begin{array}[]{lclclclclclclc}\par
d^{(t(2\sigma_{i}+2\beta+1))}_{G_{k-1}}(r_{C},r_{C^{\prime}})&\leq&\sum_{j=0}^{t-1}d^{(2\sigma_{i}+2\beta+1)}_{G_{k-1}}(r_{j},r_{j+1})\\\
&\leq&\sum_{j=0}^{t-1}d^{(\sigma_{i})}_{G_{k-1}}(r_{j},x_{j})+d^{(2\beta+1)}_{G_{k-1}}(x_{j},y_{j+1})+d^{(\sigma_{i})}_{G_{k-1}}(y_{j+1},r_{j+1})\\\
&\leq&t((1+\epsilon_{k-1})\delta_{i}+2R_{i}).\end{array}$

Recall that $t\leq 2{\log n}$. Observe that $2(2\sigma_{i}+2\beta+1){\log
n}=\sigma_{i+1}-\sigma_{i}$. Therefore, we conclude that

$\begin{array}[]{lclclclclclclc}d^{(\sigma_{i+1}-\sigma_{i})}_{G_{k-1}}(r_{C},r_{C^{\prime}})&\leq&2((1+\epsilon_{k-1})\delta_{i}+2R_{i}){\log
n}.\end{array}$ (4)

By the induction hypothesis, we also have
$d^{(\sigma_{i})}_{G_{k-1}}(r_{C^{\prime}},u)\leq R_{i}$. It follows that

$\begin{array}[]{lclclclclclclc}d^{(\sigma_{i+1})}_{G_{k-1}}(r_{C},u)&\leq&d^{(\sigma_{i+1}-\sigma_{i})}_{G_{k-1}}(r_{C},r_{C^{\prime}})+d^{(\sigma_{i})}_{G_{k-1}}(r_{t},u)&\leq&2((1+\epsilon_{k-1})\delta_{i}+2R_{i}){\log
n}+R_{i}&=&R_{i+1}.\end{array}$

Hence, $Rad^{(\sigma_{i})}_{k-1}(\widehat{C})\leq R_{i+1}$.

∎

From eq. 4 we derive the following lemma. Recall that a superclustering edge
$(r_{C},r_{C^{\prime}})$ is added to $H_{k}$ in phase $i$ with weight
$2((1+\epsilon_{k-1})\delta_{i}+2R_{i}){\log n}$. Thus, the next lemma shows
that superclustering edges never shorten distances w.r.t. $G_{k-1}$.

######  Lemma 2.3.

For every superclustering edge $(r_{C},r_{C^{\prime}})$ added to the hopset
$H_{k}$ during phase $i$, we have

$d^{(\sigma_{i+1}-\sigma_{i})}_{G_{k-1}}(r_{C},r_{C^{\prime}})\leq
2(2R_{i}+(1+\epsilon_{k-1})\delta_{i}){\log n}.$

Remark: For the correctness of the basic variant of our hopset algorithm, it
is important that there exists a path in $G_{k-1}$ between $r_{C}$ and
$r_{C^{\prime}}$ with weight at most $R_{i}$. The number of hops in this path
is not important. However, in Section 4, we use this bound to show that one
can modify the current algorithm to obtain a path-reporting hopset.

Next, we show that all popular clusters in phase $i$ are superclustered in
phase $i$.

######  Lemma 2.4.

Let $C\in P_{i}$ be a popular cluster. Then $C$ is superclustered into a
cluster of $P_{i+1}$.

###### Proof.

Since $C$ is popular, we know that $C\in W_{i}$. Recall that by Corollary B.4,
the set $Q_{i}$ is a $(3,2{\log n})$-ruling set for the set $W_{i}$ w.r.t. the
graph $\tilde{G}_{i}$. Then, there exists a cluster $C^{\prime}\in Q_{i}$ such
that $d_{\tilde{G}_{i}}(C,C^{\prime})\leq 2{\log n}$. Therefore, the BFS
exploration executed in the graph $\tilde{G}_{i}$ from all clusters in $Q_{i}$
to depth $2{\log n}$ discovers the cluster $C$, and it becomes superclustered
into a cluster of phase $i+1$. ∎

Next, we show that the each supercluster formed in phase $i$ contains many
clusters of $P_{i}$.

######  Lemma 2.5.

For every $i\in[0,\ell-1]$, each supercluster constructed in phase $i$
contains at least $deg_{i}+1$ clusters from $P_{i}$.

###### Proof.

Let $\widehat{C}$ be a cluster constructed in phase $i$, around a cluster
$C\in Q_{i}$. Since $C\in Q_{i}\subseteq W_{i}$, we have that $|\Gamma(C)|\geq
deg_{i}$. In addition, since $Q_{i}$ is $3$-separated w.r.t. the graph
$\tilde{G}_{i}$, for every cluster $C^{\prime}\in\Gamma(C)$, the cluster $C$
is the only neighbor of $C^{\prime}$ in the set $Q_{i}$. Therefore, all
clusters in $\Gamma(C)$ are detected by the BFS exploration originated in $C$.
Thus the supercluster formed around $C$ contains all clusters of $\Gamma(C)$,
and the cluster $C$ itself. It follows that the new supercluster $\widehat{C}$
contains at least $deg_{i}+1$ clusters of $P_{i}$. ∎

Finally, we prove that in phase $\ell$ there are no popular clusters, and so
we do not need to create superclusters. The following two lemmas provide upper
bounds to the size of $P_{i}$ in the exponential and the fixed growth stages,
respectively.

######  Lemma 2.6.

For $i\in[0,i_{0}+1]$, the size of $P_{i}$ is at most
$n^{1-\frac{2^{i}-1}{\kappa}}$.

###### Proof.

The proof is by induction on the index of the phase $i$. For $i=0$, the claim
is trivial since $|P_{0}|=n$. Assume that the claim holds for some $i\leq
i_{0}$, and prove it for $i+1$.

By Lemma 2.5, each supercluster formed in phase $i$ contains at least
$deg_{i}=n^{\frac{2^{i}}{\kappa}}$ clusters from $P_{i}$. Together with the
induction hypothesis, we have

$|P_{i+1}|\quad\leq\quad|P_{i}|\cdot deg_{i}^{-1}\quad\leq\quad
n^{1-\frac{2^{i}-1}{\kappa}}\cdot n^{-\frac{2^{i}}{\kappa}}\quad=\quad
n^{1-\frac{2^{i+1}-1}{\kappa}}.$

∎

######  Lemma 2.7.

For $i\in[i_{0}+1,\ell]$, the size of $P_{i}$ is at most
$n^{1+\frac{1}{\kappa}-(i-i_{0})\rho}$.

###### Proof.

The proof is by induction on the index of the phase $i$. For
$i=i_{0}+1=\left\lfloor\log{\kappa\rho}\right\rfloor+1$, by Lemma 2.6 we have
that

$|P_{i_{0}+1}|\quad\leq\quad n^{1-\frac{2^{i_{0}+1}-1}{\kappa}}\quad\leq\quad
n^{1-\frac{{\kappa\rho}-1}{\kappa}}\quad=\quad n^{1+\frac{1}{\kappa}-\rho},$

and so the claim holds. Assume that the claim holds for some
$i\in[i_{0}+1,\ell-1]$, and prove it for $i+1$.

By Lemma 2.5, we have that each supercluster formed in phase $i$ contains at
least $deg_{i}=n^{\rho}$ clusters from $P_{i}$. Together with the induction
hypothesis, we have

$|P_{i+1}|\quad\leq\quad|P_{i}|\cdot deg_{i}^{-1}\quad\leq\quad
n^{1+\frac{1}{\kappa}-(i-i_{0})\rho}\cdot n^{-\rho}\quad=\quad
n^{1+\frac{1}{\kappa}-(i+1-i_{0})\rho}.$

∎

Recall that
$\ell=\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1$.
Also note that since $\rho<1/2$ we have that $\ell>i_{0}$, and so
$deg_{\ell}=n^{\rho}$. By Lemma 2.7, there are no popular clusters in phase
$\ell$ since

$|P_{\ell}|\quad\leq\quad
n^{1+\frac{1}{\kappa}-(i_{0}+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1-i_{0})\rho}\quad\leq\quad
n^{\rho}\quad=\quad deg_{\ell}.$ (5)

#### 2.1.2 Interconnection

In this section, we provide the technical details of the interconnection step
for each phase $i\in[0,\ell]$.

Recall that $U_{i}$ is the set of clusters from $P_{i}$ that have not been
superclustered in this phase. In the interconnection step, every cluster $C\in
U_{i}$ is interconnected with all clusters $C^{\prime}\in\Gamma(C)\cap U_{i}$.
Specifically, for each cluster $C\in U_{i}$, its center $r_{C}$ adds edges to
all centers of clusters in $\Gamma(C)\cap U_{i}$. By Lemma 2.4, we have that
all popular clusters have been superclustered in this phase. Thus, all
clusters in $U_{i}$ are not popular. By Lemma A.3, we have that for every
cluster $C\in U_{i}$, its center $r_{C}$ maintains an array $m(C)$ such that
for every neighboring cluster $C^{\prime}\in\Gamma(C)$, the array $m(C)$
contains the ID of $C^{\prime}$ and the $(2\beta+1)$-hop-bounded distance in
$G_{k-1}$ between $C$ and $C^{\prime}$. Then, $r_{C}$ only needs to learn
which of the neighbors of $C$ are in $U_{i}$. Each center $r_{C^{\prime}}$ of
a cluster $C^{\prime}\in U_{i}$ writes to its memory that $C^{\prime}$ belongs
to $U_{i}$. Then, each center $r_{C}$ of a cluster $C\in U_{i}$ checks which
of its neighboring clusters are also in $U_{i}$. Recall that $r_{C}$ has
$O(n^{\rho})$ processors associated with it. Thus, checking which clusters
$C^{\prime}\in m(C)$ belong to $U_{i}$ can be performed in $O(1)$ time. The
center $r_{C}$ of the cluster $C$ adds to $H_{k}$ an interconnection edge of
weight $d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})+2R_{i}$ to every center of a
cluster $C^{\prime}\in\Gamma(C)\cap U_{i}$. Every new interconnection edge is
assigned $O(n^{\rho})$ new processors.

In phase $\ell$, we set $U_{\ell}=P_{\ell}$, and the superclustering step is
skipped. Thus the clusters do not possess the required information regarding
their neighbors. Therefore, we execute $|P_{\ell}|$ parallel BFS explorations
from all clusters in $P_{\ell}$ in the virtual graph $\tilde{G}_{\ell}$ to
depth $1$ using Algorithm 2 from Appendix A. By eq. 5, we have that
$|P_{\ell}|\leq n^{\rho}$. Hence, by Lemma A.3 these explorations use
$O((|E|+|H_{k-1}|)n^{\rho})$ processors and require $O(\beta{\log n})$ time.

Since $|P_{\ell}|\leq n^{\rho}$, every cluster $C\in P_{\ell}$ has at most
$n^{\rho}-1$ neighboring clusters in $\tilde{G}_{\ell}$, and there are no
popular clusters in $P_{\ell}$. As a result, by Lemma A.3 we have that every
cluster $C\in P_{\ell}$ maintains an array $m(C)$ that contains the IDs and
$(2\beta+1)$-hop bounded distance in $G_{k-1}$ between $C$ and all its
neighboring clusters. Each center $r_{C}$ of a cluster $C$ adds to $H_{k}$ an
interconnection edge of weight $d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})+2R_{i}$
to every center of a cluster $C^{\prime}\in\Gamma(C)\cap P_{\ell}$. Every new
interconnection edge is assigned $O(n^{\rho})$ new processors.

The following lemmas summarize the properties of the interconnection step.

Figure 3: The path from $u$ to $v$ in $G_{k}$. The dashed line depicts the
path from $u$ to $v$ in the original graph $G$. The curved lines represent
paths of length at most $R_{i}$ and at most $i$ hops from $u,v$ to their
respective cluster centers $r_{u},r_{v}$. The straight line depicts the
interconnection hopset edge between the cluster centers $r_{u},r_{v}$.

######  Lemma 2.8.

Let $u,v$ be a pair of vertices with
$d_{G}(u,v)\leq\alpha\cdot(1/\epsilon)^{i}$, such that $u\in C_{u},\ v\in
C_{v}$ and $C_{u},C_{v}\in U_{i}$. Then,

$d^{(2i+1)}_{G_{k}}(u,v)\leq(1+\epsilon_{k-1})d_{G}(u,v)+4R_{i}.$

###### Proof.

Denote $r_{u},r_{v}$ the centers of the clusters $C_{u},C_{v}$, respectively.
See Figure 3 for an illustration. By definition, we have
$d_{G}(C_{u},C_{v})\leq d_{G}(u,v)\leq\alpha\cdot(1/\epsilon)^{i}=\delta_{i}$.
Recall that $\alpha=\epsilon^{\ell}\cdot 2^{k+1}$, and $\epsilon<1$. Thus
$d_{G}(C_{u},C_{v})\leq 2^{k+1}$. By Lemma 2.1 we have
$d^{(2\beta+1)}_{G_{k-1}}(C_{u},C_{v})\leq(1+\epsilon_{k-1})d_{G}(C_{u},C_{v})$,
and so
$d^{(2\beta+1)}_{G_{k-1}}(C_{u},C_{v})\leq(1+\epsilon_{k-1})d_{G}(u,v)\leq(1+\epsilon_{k-1})\delta_{i}$.
Then, since $C_{u},C_{v}\in U_{i}$, in the interconnection step of phase $i$
the centers $r_{u},r_{v}$ add the edge $(r_{u},r_{v})$, with weight

$d^{(2\beta+1)}_{G_{k-1}}(C_{u},C_{v})+2R_{i}\leq(1+\epsilon_{k-1})d_{G}(C_{u},C_{v})+2R_{i}\leq(1+\epsilon_{k-1})d_{G}(u,v)+2R_{i}.$

In addition, by Lemma 2.2, we have that $d_{G_{k}}^{(i)}(u,r_{u})\leq R_{i}$
and $d_{G_{k}}^{(i)}(v,r_{v})\leq R_{i}$. It follows that

$d_{G_{k}}^{(2i+1)}(u,v)\leq(1+\epsilon_{k-1})d_{G}(u,v)+4R_{i}.$

∎

Next, we show that interconnection edges added to the hopset $H_{k}$ do not
shorten distances with respect to the graph $G_{k-1}$.

######  Lemma 2.9.

For every interconnection edge $(r_{C},r_{C^{\prime}})$ added to the hopset
$H_{k}$ in phase $i\in[0,\ell]$, it holds that
$d^{(2\sigma_{i}+(2\beta+1))}_{G_{k-1}}(r_{C},r_{C^{\prime}})\leq
d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})+2R_{i}$.

###### Proof.

Consider an interconnection edge $(r_{C},r_{C^{\prime}})$ added to the hopset
$H_{k}$ in some phase $i\in[0,\ell]$, between a pair of clusters
$C,C^{\prime}$, where $r_{C}\in C$ and $r_{C^{\prime}}\in C^{\prime}$. This
edge was added to the hopset with weight
$d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})+2R_{i}$. Let $u\in C$ and
$u^{\prime}\in C^{\prime}$ be the vertices such that
$d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})=d^{(2\beta+1)}_{G_{k-1}}(u,u^{\prime})$.
By Lemma 2.2, we have that $d^{(\sigma_{i})}_{G_{k-1}}(r_{C},u)\leq R_{i}$,
and also $d^{(\sigma_{i})}_{G_{k-1}}(r_{C^{\prime}},u^{\prime})\leq R_{i}$. It
follows that

$d^{(2\sigma_{i}+(2\beta+1))}_{G_{k-1}}(r_{C},r_{C^{\prime}})\ \leq\
d^{(\sigma_{i})}_{G_{k-1}}(r_{C},u)+d^{(2\beta+1)}_{G_{k-1}}(u,u^{\prime})+d^{(\sigma_{i})}_{G_{k-1}}(u^{\prime},r_{C^{\prime}})\
\leq\ d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})+2R_{i}.$

∎

For every $i\in[0,\ell]$, define $U^{(i)}=\bigcup_{j=0}^{i}U_{j}$. The next
lemma shows that for every vertex $v$ there exists an index $i\in[0,\ell]$
such that $v$ belongs to a cluster that joins the set $U_{i}$. For notational
purposes, define $U_{-1}=\emptyset$, and $U^{(i)}=\bigcup_{j=-1}^{i}U_{i}$ for
all $i\in[0,\ell]$.

######  Lemma 2.10.

For every index $i\in[0,\ell]$, the set $P_{i}\cup U^{(i-1)}$ is a partition
of $V$.

###### Proof.

The proof is by induction on the index of the phase $i$. For $i=0$, the claim
is trivial since $P_{0}$ is a partition of $V$ into singleton clusters.

Assume the claim holds for some index $i\in[0,\ell-1]$. Let $v\in V$. By the
induction hypothesis, $v$ belongs to a cluster $C\in P_{i}\cup U^{(i-1)}$.

If $C\in U^{(i-1)}$, then, by definition, $C\in U^{(i)}$. Note that in this
case, the cluster $C$ will not join a supercluster in phase $i$, and so the
cluster $C$ is the only cluster containing the vertex $v$ in the set
$U^{(i)}\cup P_{i+1}$.

If $C\in P_{i}$, by the induction hypothesis, we know that there is no cluster
$C^{\prime}\in U^{(i-1)}$ that contains $v$. In phase $i$, the cluster $C$ has
either been superclustered into a supercluster of $P_{i+1}$, or it has joined
$U_{i}$. In any case, $C\in P_{i+1}\cup U^{(i)}$. Since every vertex $v\in V$
belongs to a single cluster $C\in P_{i+1}\cup U^{(i)}$, we have that
$P_{i+1}\cup U^{(i)}$ is a partition of $V$. ∎

Recall that in the last phase $\ell$, we skip the superclustering step and set
$U_{\ell}=P_{\ell}$. Thus, Lemma 2.10 implies that $U^{(\ell)}$ is a partition
of $V$.

##  3 Analysis of the Construction

In this section we analyze the size and stretch that the hopset
$H=\bigcup_{k=k_{0}}^{\lambda}H_{k}$ guarantees, as well as the complexity of
the construction.

###  3.1 Analysis of the Size

Let $k\in[k_{0},\lambda]$. We begin by analyzing the number of edges added to
$H_{k}$ by every phase $i$ of the algorithm. Recall that in phase $i$, only
centers of clusters in $P_{i}$ add edges to the hopset.

Consider a cluster $C\in P_{i}$. During phase $i$, if the cluster $C$ is
selected to the ruling set $Q_{i}$ it will grow a supercluster of $P_{i+1}$.
In this case, the center of $C$ will not add to $H_{k}$ any edges in phase $i$
of the algorithm. If $C\notin Q_{i}$, but it is detected by the exploration
originated from a cluster in $Q_{i}$, it will join a supercluster. In this
case, in phase $i$ the center of $C$ will add a single superclustering edge to
$H_{k}$. If the cluster $C\notin Q_{i}$, and it is not detected by the
exploration from $Q_{i}$, then $C$ joins the set $U_{i}$. In this case, the
center $r_{C}$ of $C$ will add interconnection edges to all centers of
clusters in $\Gamma(C)$. By Lemma 2.4, we have that all popular clusters of
phase $i$ have been superclustered in phase $i$. It follows that all clusters
in $U_{i}$ are not popular. Thus, the number of interconnection edges added to
the hopset $H_{k}$ by $r_{C}$ is at most $deg_{i}$.

Therefore, the number of superclustering edges added to the hopset $H_{k}$ in
phase $i\in[0,\ell-1]$ is exactly $|P_{i}|-|Q_{i}|-|U_{i}|.$ The number of
interconnection edges added to to the hopset $H_{k}$ in phase $i\in[0,\ell]$
is at most $|U_{i}|\cdot deg_{i}.$ Note that by eq. 5, we have that the size
of $P_{\ell}$ is at most $deg_{\ell}$. Thus this upper bound also holds for
phase $\ell$.

It follows that the number of edges added to $H_{k}$ in phase $i$ is at most

$|P_{i}|-|Q_{i}|-|U_{i}|+|U_{i}|\cdot
deg_{i}=|P_{i}|-|Q_{i}|+|U_{i}|\cdot(deg_{i}-1).$ (6)

Next, we use the size of $P_{i+1}$ to bound the size of $U_{i}$. By Lemma 2.5,
every cluster of $P_{i+1}$ contains at least $deg_{i}+1$ clusters of $P_{i}$.
Therefore, we have

$|U_{i}|\leq|P_{i}|-|P_{i+1}|\cdot(deg_{i}+1).$ (7)

Recall that $|Q_{i}|=|P_{i+1}|$. By eqs. 6 and 7 we have that the number of
edges added to the hopset $H_{k}$ in phase $i$ is at most

$\begin{array}[]{lclclclclcl}|P_{i}|-|Q_{i}|+|U_{i}|\cdot(deg_{i}-1)&\leq&|P_{i}|-|P_{i+1}|+(|P_{i}|-|P_{i+1}|\cdot(deg_{i}+1))\cdot(deg_{i}-1)\\\
&=&|P_{i}|-|P_{i+1}|+|P_{i}|\cdot(deg_{i}-1)-|P_{i+1}|\cdot(deg^{2}_{i}-1)\\\
&=&|P_{i}|\cdot deg_{i}-|P_{i+1}|\cdot deg^{2}_{i}.\end{array}$

Recall that in phase $\ell$ we do not form superclusters. Therefore, the
number of edges added to the hopset by phase $\ell$ is at most
$|P_{\ell}|\cdot(|P_{\ell}|-1)$. By eq. 5, we have that $|P_{\ell}|\leq
deg_{\ell}$, and so in phase $\ell$ we add at most $|P_{\ell}|\cdot
deg_{\ell}$ edges to $H_{k}$. Hence, the number of edges added to $H_{k}$ by
all phases of the algorithm is bounded by

$\begin{array}[]{lclclclclcl}|H_{k}|&\leq&\sum_{i=0}^{\ell-1}(|P_{i}|\cdot
deg_{i}-|P_{i+1}|\cdot deg^{2}_{i})+|P_{\ell}|\cdot deg_{\ell}\\\
&=&|P_{0}|\cdot
deg_{0}+\sum_{i=1}^{\ell}(|P_{i}|\cdot(deg_{i}-deg^{2}_{i-1}))\\\
&=&n^{1+\frac{1}{\kappa}}+\sum_{i=1}^{\ell}(|P_{i}|\cdot(deg_{i}-deg^{2}_{i-1})).\end{array}$
(8)

Recall that in the exponential growth stage, we have
$deg_{i}=n^{\frac{2^{i}}{\kappa}}$. Thus for $i\in[1,i_{0}]$ we have
$deg_{i}=deg^{2}_{i-1}$. Recall also that in the fixed growth stage, we have
$deg_{i}=n^{\rho}$. Note that
$deg_{i_{0}}=n^{\frac{2^{\left\lfloor\log\kappa\rho\right\rfloor}}{\kappa}}\geq
n^{\frac{\rho}{2}}$. It follows that for $i\in[i_{0}+1,\ell]$ we also have
$deg_{i}\leq deg^{2}_{i-1}$. By eq. 8, the size of $H_{k}$ satisfies:

$\begin{array}[]{lclclclclcl}|H_{k}|&\leq&n^{1+\frac{1}{\kappa}}+\sum_{i=1}^{\ell}(|P_{i}|\cdot(deg_{i}-deg^{2}_{i-1}))&\leq&n^{1+\frac{1}{\kappa}}.\end{array}$
(9)

Recall that the ultimate hopset $H$ is the union of the hopsets $H_{k}$
constructed for each scale $k\in[k_{0},\lambda]$. By eq. 9, we have that the
size of the hopset $H$ is at most:

$\begin{array}[]{lclclclclcl}|H|&=&\lceil{\log\Lambda}\rceil\cdot
n^{1+\frac{1}{\kappa}}.\end{array}$ (10)

###  3.2 Analysis of the Running Time and Work

In this section, we analyze the computational complexity of the construction.
Observe that for the construction of the hopset $H_{k}$, the algorithm uses
the graph $G_{k-1}$, that contains all edged of $E$ and all edges of the
hopset $H_{k-1}$. Edges of the hopsets $H_{k-2},H_{k-3},\dots$ are not used
explicitly in the construction of $H_{k}$. Recall that for every scale
$k\in[k_{0},\lambda]$, by eq. 9 we have $|H_{k}|\leq n^{1+\frac{1}{\kappa}}$.
Therefore, in the construction of the hopset $H_{k}$, the algorithm uses
processors that simulate edges of the original graph $G$, as well as
$O(n^{1+\frac{1}{\kappa}}\cdot n^{\rho})$ processors that simulate edges of
the hopset $H_{k-1}$. When the construction of $H_{k}$ terminates, the
processors that simulate the edges of $H_{k-1}$ are reallocated to simulate
the edges of $H_{k+1}$. Hence, in every time point, our algorithm uses up to
$O((|E|+n^{1+\frac{1}{\kappa}})\cdot n^{\rho})$ processors to simulate edges
and vertices.

######  Lemma 3.1.

Our algorithm uses $O((|E|+n^{1+\frac{1}{\kappa}})\cdot n^{\rho})$ processors,
and its running time is
$O(({\log\Lambda})({\log\kappa\rho}+1/\rho)\beta{\log^{2}n})$.

###### Proof.

We begin by analyzing the running time of a single phase $i$ in the
construction of $H_{k}$, for some $k\in[k_{0},\lambda]$.

Superclustering: By Lemma A.3, detecting popular clusters using
$O((|E|+n^{1+\frac{1}{\kappa}})\cdot n^{\rho})$ processors requires
$O(\beta{\log n})$ time. Constructing a $(3,2{\log n})$ ruling set for the
graph $\tilde{G}_{i}$ using $O(|E|+n^{1+\frac{1}{\kappa}})$ processors
requires additional $O(\beta{\log^{2}n})$ time, by Corollary B.4. Forming
superclusters requires executing a BFS exploration to depth $2{\log n}$ in the
graph $\tilde{G}_{i}$. By Corollary A.5, this requires
$O(|E|+n^{1+\frac{1}{\kappa}})$ processors and $O(\beta{\log^{2}n})$ time.
Therefore, overall, the execution of each superclustering step requires
$O((|E|+n^{1+\frac{1}{\kappa}})\cdot n^{\rho})$ processors and
$O(\beta\cdot{\log^{2}n})$ time.

Interconnection: In phases $i\in[0,\ell-1]$, by Lemma A.3, each center $r_{C}$
of a cluster $C\in U_{i}$ knows the centers of the (up to) $n^{\rho}$ clusters
it needs to connect to, and the distances to them. Thus, for these phases, the
interconnection step requires $O(n^{1+\rho})$ processors and $O(1)$ time.

For the concluding phase $\ell$, Algorithm 2 is executed as a part of the
interconnection step. By Lemma A.3, this exploration requires
$O((|E|+n^{1+\frac{1}{\kappa}})\cdot n^{\rho})$ processors and $O(\beta{\log
n})$ time.

It follows that the overall running time of a single phase $i\in[0,\ell]$ is
$O(\beta{\log^{2}n})$. Recall that the algorithm constructs hopsets for at
most $\lceil{\log\Lambda}\rceil$ scales, and in each scale it executes
$\ell+1$ phases.

Hence, the algorithm uses $O((|E|+n^{1+\frac{1}{\kappa}})\cdot n^{\rho})$
processors and requires
$O(({\log\Lambda})({\log\kappa\rho}+1/\rho)\beta{\log^{2}n})$ time. ∎

###  3.3 Analysis of the Stretch

We begin by providing an upper bound on $R_{i}$. Recall that by definition, we
have $R_{0}=0$, and

$R_{i+1}=(2(1+\epsilon_{k-1})\delta_{i}+4R_{i}){\log
n}+R_{i}=2(1+\epsilon_{k-1})\alpha\cdot\left({1}/{\epsilon}\right)^{i}{\log
n}+(4{\log n}+1)R_{i}.$

######  Lemma 3.2.

For all $i\in[0,\ell]$, we have $R_{i}=2(1+\epsilon_{k-1})\alpha{\log
n}\cdot\sum_{j=0}^{i-1}\left(\frac{1}{\epsilon}\right)^{j}\cdot(4{\log
n}+1)^{i-1-j}$.

###### Proof.

The proof is by induction on the index of the phase $i$. For $i=0$, both sides
of the equation are equal to $0$.

Assume that the claim holds for some index $i\in[0,\ell-1]$, and prove it for
$i+1$. By definition and the induction hypothesis we have

$\begin{array}[]{lclclclclclclc}R_{i+1}&=&2(1+\epsilon_{k-1})\alpha\cdot\left({1}/{\epsilon}\right)^{i}{\log
n}+(4{\log n}+1)R_{i}\\\
&=&2(1+\epsilon_{k-1})\alpha\cdot\left({1}/{\epsilon}\right)^{i}{\log
n}+(4{\log n}+1)\cdot 2(1+\epsilon_{k-1})\alpha{\log
n}\cdot\sum_{j=0}^{i-1}\left(\frac{1}{\epsilon}\right)^{j}\cdot(4{\log
n}+1)^{i-1-j}\\\ &=&2(1+\epsilon_{k-1})\alpha{\log
n}\cdot\sum_{j=0}^{i}\left(\frac{1}{\epsilon}\right)^{j}\cdot(4{\log
n}+1)^{i-j}.\par\end{array}$

∎

Next, we provide an explicit bound on $R_{i}$. Assume that
$\epsilon<\frac{1}{2(4{\log n}+1)}$. This assumption will not affect our final
result (see Section 3.4 for details). For all $i\in[0,\ell]$,

$\begin{array}[]{lclclclclclclc}R_{i}&=&2(1+\epsilon_{k-1})\alpha{\log
n}\cdot\sum_{j=0}^{i-1}\left(\frac{1}{\epsilon}\right)^{j}\cdot(4{\log
n}+1)^{i-1-j}\\\ &=&2(1+\epsilon_{k-1})\alpha{\log n}\cdot(4{\log
n}+1)^{i-1}\sum_{j=0}^{i-1}\left(\frac{1}{\epsilon}\right)^{j}\cdot{(4{\log
n}+1)^{-j}}\\\ &\leq&2(1+\epsilon_{k-1})\alpha{\log n}\cdot(4{\log
n}+1)^{i-1}\left[\frac{\left(\frac{1}{\epsilon(4{\log
n}+1)}\right)^{i}}{\frac{1}{\epsilon(4{\log n}+1)}-1}\right]\\\
&\leq&2(1+\epsilon_{k-1})\alpha{\log n}\cdot(4{\log
n}+1)^{i-1}\cdot\left(\frac{1}{\epsilon(4{\log
n}+1)}\right)^{i}\cdot\frac{\epsilon(4{\log n}+1)}{1-\epsilon(4{\log n}+1)}\\\
&\leq&4\cdot(1+\epsilon_{k-1})\alpha{\log
n}\cdot\left(\frac{1}{\epsilon}\right)^{i-1}.\end{array}$ (11)

For the sake of brevity, we denote $c(n)=4\cdot(1+\epsilon_{k-1}){\log n}$.

We are now ready to analyze the stretch and hopbound guarantees that the
hopset $H_{k}$ provides for pairs of vertices $u,v\in V$ with
$d_{G}(u,v)\in(2^{k},2^{k+1}]$. Recall that $\alpha=\epsilon^{\ell}\cdot
2^{k+1}$. Define $h_{0}=1$, and $h_{i}=(1/\epsilon+2)\cdot(h_{i-1}+1)+2i+1$.

######  Lemma 3.3.

Let $u,v$ be a pair of vertices with
$d_{G}(u,v)\leq\alpha\cdot\left({1}/{\epsilon}\right)^{i}$, such that all
vertices of a shortest path $\pi(u,v)$ in $G$ between them are clustered in
$U^{(i)}$, for some $i\leq\ell$. Then it holds that

$d_{G}(u,v)\ \leq\ d^{(h_{i})}_{G_{k}}(u,v)\ \leq\ (1+\epsilon_{k-1}+5\cdot
c(n)(i-1)\epsilon)\cdot d_{G}(u,v)+5\cdot\alpha\cdot
c(n)\cdot(1/\epsilon)^{i-1}.$

###### Proof.

For the left-hand side of the equation, observe that Lemmas 2.3, 2.9 imply
that for any $k\in[k_{0},\lambda]$, distances in $G_{k}$ are never shorter
than distances in $G_{k-1}$. Since $H_{k_{0}-1}=\emptyset$, we conclude that
for every pair of vertices we have

$d_{G}(u,v)=d_{G_{k_{0}-1}}(u,v)\leq d_{G_{k}}(u,v).$

We continue with the proof of the right-hand side of the equation. The proof
is by induction on the index $i$. For $i=0$, consider a pair of vertices $u,v$
such that $\\{u\\},\\{v\\}\in U_{0}$ and also
$d_{G}(u,v)\leq\alpha\cdot\left({1}/{\epsilon}\right)^{i}=\delta_{0}$. By
Lemma 2.1, we have that
$d^{(2\beta+1)}_{G_{k-1}}(u,v)\leq(1+\epsilon_{k-1})d_{G}(u,v)\leq(1+\epsilon_{k-1})\delta_{0}$.
Since $\\{u\\},\\{v\\}\in U_{0}$, the edge $(u,v)$ was added to $H_{k}$ with
weight $d^{(2\beta+1)}_{G_{k-1}}(u,v)\leq(1+\epsilon_{k-1})d_{G}(u,v)$ in the
interconnection step of phase $0$. Thus,
$d^{(1)}_{G_{k}}(u,v)\leq(1+\epsilon_{k-1})d_{G}(u,v)$. In addition, since
$d_{G}(u,v)\leq\alpha$, we have

$\begin{array}[]{llllclclclc}d^{(1)}_{G_{k}}(u,v)&\leq&(1+\epsilon_{k-1})d_{G}(u,v)\\\
&\leq&(1+\epsilon_{k-1})d_{G}(u,v)+5\cdot c(n)\cdot\epsilon(\alpha-
d_{G}(u,v))\\\ &=&(1+\epsilon_{k-1}-5\cdot c(n)\cdot\epsilon)d_{G}(u,v)+5\cdot
c(n)\cdot\epsilon\alpha.\end{array}$

Hence the claim holds for the base case.

Let $i\in[0,\ell-1]$. Assume that the claim holds for all
$i^{\prime}\in[0,i]$, and prove it for $i+1$.

Consider first a pair of vertices $x,y$ such that there exists a shortest path
between them $\pi(x,y)$, and all vertices on this path are
$U^{(i)}$-clustered. (We do not require $d_{G}(x,y)$ to be bounded.) We divide
this path into segments, $L_{1},\dots,L_{q}$, each of length no more than
$\delta_{i}$. For convenience, we imagine that the vertices of $\pi(x,y)$
appear from left to right, where $x$ is the leftmost vertex and $y$ is the
rightmost vertex. For a segment $L_{j}$, denote by $a_{j},b_{j}$ its leftmost
and rightmost vertices, respectively. For the first segment $L_{1}$, set
$a_{1}=x$. Given a left endpoint $a_{j}$ of a segment $L_{j}$, the right
endpoint $b_{j}$ of the segment is set to be the farthest vertex to the right
of $a_{j}$, that is within distance at most $\delta_{i}$ of $a_{j}$ in $G$.
Observe that it is possible that $a_{j}=b_{j}$, if the closest vertex to the
right of $a_{j}$ is within distance more than $\delta_{i}$ from it, or if
$a_{j}=y$. Given a right endpoint $b_{j}\neq y$, the next left endpoint
$a_{j+1}$ is the closest vertex to $b_{j}$ from the right. See Figure 4 for an
illustration.

Figure 4: The bounded hop path between $x,y$ in $G_{k}$. In the figure, the
straight line depicts the shortest path $\pi(x,y)$ in $G$ from $x$ to $y$. The
dashed vertical lines represent the partition of $\pi(x,y)$ into segments. The
thick curved lines represent edges of the original graph $G$, and the curved
lines represents bounded hop paths from the first to last vertex in each
segment.

Observe that for the last segment $L_{q}$, we have that $b_{q}=y$. Note that
for every $i\in[1,q-1]$ we have $d_{G}(a_{j},a_{j+1})>\delta_{i}$. It follows
that the number of segments $q$ is at most:

$q\quad\leq\quad\left\lceil\frac{d_{G}(x,y)}{\delta_{i}}\right\rceil$ (12)

Also note that for every $j\in[1,q]$, we have
$d_{G}(a_{j},b_{j})\leq\delta_{i}$. Thus the induction hypothesis is
applicable to all these segments, i.e.,

$d^{(h_{i})}_{G_{k}}(a_{j},b_{j})\leq(1+\epsilon_{k-1}+5\cdot
c(n)\cdot(i-1)\epsilon)\cdot d_{G}(a_{j},b_{j})+5\cdot\alpha\cdot
c(n)\cdot(1/\epsilon)^{i-1}$

For each $j\in[1,q]$, let $\pi^{\prime}(a_{j},b_{j})$ be the shortest
$h_{i}$-bounded $a_{j}-b_{j}$ path in $G_{k}$. Let $\pi^{\prime}(x,y)$ be a
path in $G_{k}$ constructed in the following manner. For $j\in[1,q]$, if
$a_{j}\neq b_{j}$, we replace the segment between $a_{j},b_{j}$ in $\pi(x,y)$
with the path $\pi^{\prime}(a_{j},b_{j})$ of at most $h_{i}$ hops and at most
$(1+\epsilon_{k-1}+5\cdot c(n)(i-1)\epsilon)\cdot
d_{G}(a_{j},b_{j})+5\cdot\alpha\cdot c(n)\cdot(1/\epsilon)^{i-1}$ length. In
addition, the path $\pi^{\prime}(x,y)$ contains all edges $b_{j},a_{j+1}$ from
$G$, for $j\in[1,q-1]$, i.e., all edges between segments. Therefore, the
length of the new path $\pi^{\prime}(x,y)$ is at most
$(1+\epsilon_{k-1}+5\cdot c(n)(i-1)\epsilon)\cdot d_{G}(x,y)+q\cdot
5\cdot\alpha\cdot c(n)\cdot(1/\epsilon)^{i-1}$, and the number of hops in
$\pi^{\prime}(x,y)$ is at most $qh_{i}+q-1$. Recall that
$\delta_{i}=\alpha\cdot\left({1}/{\epsilon}\right)^{i}$. By eq. 12, we have

$\begin{array}[]{lllll}d^{\left(\left\lceil\frac{d_{G}(x,y)}{\delta_{i}}\right\rceil\cdot(h_{i}+1)-1\right)}_{G_{k}}(x,y)&\leq&(1+\epsilon_{k-1}+5\cdot
c(n)(i-1)\epsilon)\cdot
d_{G}(x,y)+\quad\left\lceil\frac{d_{G}(x,y)}{\delta_{i}}\right\rceil\cdot
5\cdot\alpha\cdot c(n)\cdot(1/\epsilon)^{i-1}\\\
&\leq&(1+\epsilon_{k-1}+5\cdot c(n)(i-1)\epsilon+\frac{5\cdot\alpha\cdot
c(n)\cdot(1/\epsilon)^{i-1}}{\alpha\cdot\left({1}/{\epsilon}\right)^{i}})\cdot
d_{G}(x,y)+5\cdot\alpha\cdot c(n)\cdot(1/\epsilon)^{i-1}\\\
&=&(1+\epsilon_{k-1}+5\cdot c(n)\cdot i\cdot\epsilon)\cdot
d_{G}(x,y)+5\cdot\alpha\cdot c(n)\cdot(1/\epsilon)^{i-1}\\\ \end{array}$ (13)

Now, consider a pair $u,v\in V$ with
$d_{G}(u,v)\leq\alpha\cdot(1/\epsilon)^{{[}}i+1]=\delta_{i+1}$, such that all
vertices of a shortest path $\pi(u,v)$ in $G$ between them are clustered in
$U^{(i+1)}$.

Let $w_{1},w_{2}$ be the first and last $U_{i+1}$-clustered vertices of the
path $\pi(u,v)$. Let $C_{1},C_{2}\in P_{i+1}$ be the clusters of
$w_{1},w_{2}$, respectively. See Figure 5 for an illustration. Note that since
$w_{1},w_{2}$ lie on a path of length at most
$\alpha\cdot(1/\epsilon)^{{[}}i+1]$, we have
$d_{G}(w_{1},w_{2})\leq\alpha\cdot(1/\epsilon)^{{[}}i+1]$. By Lemma 2.8, we
have that

$d_{G_{k}}^{(2(i+1)+1)}(w_{1},w_{2})\leq(1+\epsilon_{k-1})d_{G}(w_{1},w_{2})+4R_{i+1}.$
(14)

Figure 5: The path between $u,v$ in $G_{k}$. In the figure, the straight line
depicts the shortest path $\pi(u,v)$ in $G$ from $u$ to $v$. The vertices
$w_{1},w_{2}$ are the first and last $U_{i}$-clustered vertices, and
$z_{1},z_{2}$ are their neighbors on the subpaths of $\pi(u,v)$ from $u$ to
$w_{1}$ and from $w_{2}$ to $v$, respectively. The curved dotted line depicts
the path from $w_{1}$ to $w_{2}$ obtained by Lemma 2.8. The solid thick lines
depict edges from the original graph $G$, and the solid curved lines depict
paths obtained by the induction hypothesis.

Let $z_{1},z_{2}$ be the neighbors of the vertices $w_{1},w_{2}$ on the
subpaths of $\pi(u,v)$ from $u$ to $w_{1}$ and from $w_{2}$ to $v$,
respectively. Note that $z_{1},z_{2}$ are both $U^{(i)}$-clustered.

The path $\pi^{\prime}(u,v)$ is constructed in the following manner. By eq.
13, there is are paths in $G_{k}$ from $u$ to $z_{1}$ and from $z_{2}$ to $v$,
each with a multiplicative stretch of $(1+\epsilon_{k-1}+5\cdot
c(n)\cdot\epsilon\cdot i)$ and an additive error of $5\cdot\alpha\cdot
c(n)\cdot(1/\epsilon)^{i}$, using up to
$p_{1}=\left(\left\lceil\frac{d_{G}(u,z_{1})}{\alpha\cdot(1/\epsilon)^{i}}\right\rceil\cdot(h_{i}+1)-1\right)$
and
$p_{2}=\left(\left\lceil\frac{d_{G}(z_{2},v)}{\alpha\cdot(1/\epsilon)^{i}}\right\rceil\cdot(h_{i}+1)-1\right)$
hops, respectively. By eq. 14, there is a path from $w_{1}$ to $w_{2}$ in
$G_{k}$ of length at most $(1+\epsilon_{k-1})\cdot
d_{G}(w_{1},w_{2})+4R_{i+1}$, using up to $2(i+1)+1$ hops. In addition, we use
the edges $(z_{1},w_{1})$ and $(w_{2},z_{2})$ of the original graph $G$. Since
the edges $(z_{1},w_{1}),(w_{2},z_{2})$ lie on a shortest path, we know that
$d_{G}(z_{1},w_{1})=\omega(z_{1},w_{1})$, and
$d_{G}(w_{2},z_{2})=\omega(w_{2},z_{2})$. It follows that

$\begin{array}[]{cllllclclclc}d^{(p_{1}+p_{1}+2i+5)}_{G_{k}}(u,v)&\leq&d^{(p_{1})}_{G_{k}}(u,z_{1})+d^{(1)}_{G_{k}}(z_{1},w_{1})+d^{(2i+3)}_{G_{k}}(w_{1},w_{2})+d^{(1)}_{G_{k}}(w_{2},z_{2})+d^{(p_{1})}_{G_{k}}(z_{2},v)\\\
&\leq&(1+\epsilon_{k-1}+5\cdot c(n)\cdot i\cdot\epsilon)\cdot
d_{G}(u,z_{1})+5\cdot\alpha\cdot
c(n)\cdot(1/\epsilon)^{i-1}+\omega(z_{1},w_{1})\\\ &&+(1+\epsilon_{k-1})\cdot
d_{G}(w_{1},w_{2})+4R_{i+1}+\omega(w_{2},z_{2})\\\ &&+(1+\epsilon_{k-1}+5\cdot
c(n)\cdot i\cdot\epsilon)\cdot d_{G}(z_{2},v)+5\cdot\alpha\cdot
c(n)\cdot(1/\epsilon)^{i-1}\\\ &\leq&(1+\epsilon_{k-1}+5\cdot c(n)\cdot
i\cdot\epsilon)\cdot d_{G}(u,v)+4R_{i+1}+10\cdot\alpha\cdot
c(n)\cdot(1/\epsilon)^{i-1}.\end{array}$ (15)

Recall that by eq. 11 we have that $R_{i+1}\leq
c(n)\cdot\alpha\cdot(1/\epsilon)^{i}$, and also that $\epsilon\leq 1/10$ (in
fact, we even require $\epsilon<\frac{1}{2(4{\log n}+1)}$). Therefore, we have

$\begin{array}[]{llllll}4R_{i+1}+10\cdot\alpha\cdot
c(n)\cdot(1/\epsilon)^{i-1}&\leq&4c(n)\cdot\alpha\cdot(1/\epsilon)^{i}+10\cdot\alpha\cdot
c(n)\cdot(1/\epsilon)^{i-1}\\\
&=&c(n)\cdot\alpha\cdot(1/\epsilon)^{i}(4+10\epsilon)\\\
&\leq&5c(n)\cdot\alpha\cdot(1/\epsilon)^{i}.\par\par\end{array}$ (16)

The number of hops in the path $\pi^{\prime}(u,v)$ satisfies:

$\begin{array}[]{lllclclclclc}p_{1}+p_{1}+2i+3&\leq&\left(\left\lceil\frac{d_{G}(u,z_{1})}{\alpha\cdot(1/\epsilon)^{i}}\right\rceil+\left\lceil\frac{d_{G}(z_{2},v)}{\alpha\cdot(1/\epsilon)^{i}}\right\rceil\right)\cdot(h_{i}+1)-2+2(i+1)+3\\\
&\leq&(1/\epsilon+2)\cdot(h_{i}+1)+2(i+1)+1\qquad=\qquad h_{i+1}.\\\
\end{array}$ (17)

For the last inequality, recall that $d_{G}(u,z_{1})+d_{G}(z_{2},v)\leq
d_{G}(u,v)\leq\delta_{i+1}=\alpha\cdot\left(\frac{1}{\epsilon}\right)^{i+1}$.
It follows by eqs. 15, 16 and 17, that the distance between $u,v$ in $G_{k}$
satisfies:

$d^{h_{i+1}}_{G_{k}}(u,v)\leq(1+\epsilon_{k-1}+5\cdot c(n)\cdot
i\cdot\epsilon)\cdot d_{G}(u,v)+5c(n)\cdot\alpha\cdot(1/\epsilon)^{i}.$

∎

We now provide an upper bound on $h_{\ell}$.

######  Lemma 3.4.

The recursive equation $h_{0}=1$, and
$h_{i}=(1/\epsilon+2)\cdot(h_{i-1}+1)+2i+1$ solves to

$h_{i}\leq(1/\epsilon+5)^{i}.$

###### Proof.

The proof is by induction on the index $i$. For $i=0$, both sides of the
equation are equal to $1$, and so the claim holds.

Assume that the claim holds for some index $i\in[0,\ell-1]$, and prove it for
$i+1$.

By definition, we have

$\begin{array}[]{lllclclclclc}h_{i+1}&=&(1/\epsilon+2)\cdot(h_{i}+1)+2(i+1)+1\par&=&(1/\epsilon+2)\cdot
h_{i}+1/\epsilon+2i+5.\end{array}$

Note that $1/\epsilon+2i+5\leq h_{i}+2$. This is since

$\begin{array}[]{lllclclclclc}h_{i}&=&(1/\epsilon+2)\cdot(h_{i-1}+1)+2i+1\\\
&=&1/\epsilon\cdot h_{i-1}+2h_{i-1}+1/\epsilon+2i+3\\\
&\geq&1/\epsilon+2i+3\end{array}$

Together with the induction hypothesis, it follows that we have

$\begin{array}[]{lllclclclclc}h_{i+1}&=&(1/\epsilon+2)\cdot
h_{i}+1/\epsilon+2(i+1)+3&\leq&(1/\epsilon+3)h_{i}+2&\leq&(1/\epsilon+5)^{i+1}.\end{array}$

∎

It follows that the hopbound of the hopset $H$ is

$h_{\ell}=(1/\epsilon+5)^{\ell}.$ (18)

###  3.4 Rescaling

In this section, we rescale $\epsilon$ to obtain our ultimate stretch
guarantee.

Set now $\epsilon^{\prime}=20({\log n})\epsilon(\ell+1)$. The condition
$\epsilon<\frac{1}{2(4{\log n}+1)}$ now translates to the condition
$\epsilon^{\prime}=O(\ell)$, which we replace by a stronger condition
$\epsilon^{\prime}<1$.

Recall by eq. 18 the hopbound of the hopset $H$ is $(1/\epsilon+5)^{\ell}$.
The hopbound is now rescaled to be

$h_{\ell}=(1/\epsilon+5)^{\ell}=\left(\frac{20(\ell+1){\log
n}}{\epsilon^{\prime}}+5\right)^{\ell}=O\left(\frac{\ell{\log
n}}{\epsilon^{\prime}}\right)^{\ell}.$

Next, we complete the analysis of the stretch guarantee.

######  Corollary 3.5.

Let $u,v$ be a pair of vertices with $d_{G}(u,v)\in(2^{k},2^{k+1}]$. Then it
holds that

$d^{(h_{\ell})}_{G_{k}}(u,v)\leq(1+\epsilon_{k-1})(1+\epsilon^{\prime})d_{G}(u,v).$

###### Proof.

Recall that $\alpha=2^{k+1}\epsilon^{\ell}$, and that
$c(n)=4(1+\epsilon_{k-1})\cdot{\log n}$. Then, By Lemma 3.3, we have

$\begin{array}[]{lllclclclclc}d^{(h_{\ell})}_{G_{k}}(u,v)&\leq&(1+\epsilon_{k-1}+5\cdot
c(n)(\ell-1)\epsilon)\cdot d_{G}(u,v)+5\cdot\alpha\cdot
c(n)\cdot(1/\epsilon)^{\ell-1}\\\ &=&(1+\epsilon_{k-1}+5\cdot
c(n)(\ell-1)\epsilon)\cdot d_{G}(u,v)+10c(n)\cdot 2^{k}\epsilon\\\
&\leq&(1+\epsilon_{k-1}+5\cdot c(n)\epsilon(\ell+1))\cdot d_{G}(u,v)\\\
&=&(1+\epsilon_{k-1}+5\cdot 4(1+\epsilon_{k-1})\cdot{\log
n}\cdot\epsilon(\ell+1))\cdot d_{G}(u,v)\\\ &=&(1+\epsilon_{k-1})(1+20{\log
n}\cdot\epsilon(\ell+1))\cdot d_{G}(u,v)\\\
&=&(1+\epsilon_{k-1})(1+\epsilon^{\prime})\cdot
d_{G}(u,v).\par\par\end{array}$

∎

Recall that $\epsilon_{k-1}$ is the value such that $G_{k-1}$ provides stretch
$(1+\epsilon_{k-1})$, and that $k_{0}={\lfloor{\log\beta}\rfloor}$ (see eq. 2)
and $\lambda=\lceil{\log\Lambda}\rceil$. For $k<k_{0}$, note that
$\epsilon_{k}=0$. We now bound $\epsilon_{k}$ for $k\geq k_{0}$.

######  Lemma 3.6.

For $k\in[k_{0},\lambda]$ we have

$1+\epsilon_{k}\leq(1+\epsilon^{\prime})^{k}.$

###### Proof.

The proof is by induction on the index of the scale $k$. For $k=k_{0}$, we
have
$1+\epsilon_{k_{0}}=(1+\epsilon_{k_{0}-1})(1+\epsilon^{\prime})=1+\epsilon^{\prime}$
since $\epsilon_{k_{0}-1}=0$. Thus the claim holds.

Assume that the claim holds for some $k\in[k_{0},\lambda-1]$ and prove it for
$k+1$. By definition and the induction hypothesis, we have

$1+\epsilon_{k+1}=(1+\epsilon_{k})(1+\epsilon^{\prime})\leq(1+\epsilon^{\prime})^{k}(1+\epsilon^{\prime})=(1+\epsilon^{\prime})^{k+1}.$

∎

Observe that Lemma 3.6 implies that the overall stretch of our hopset is at
most $(1+\epsilon^{\prime})^{\lambda}$.

Define $\epsilon^{\prime\prime}=2\lambda\epsilon^{\prime}$. The condition
$\epsilon^{\prime}<1$ is replaced by a stronger condition,
$\epsilon^{\prime\prime}<1$. It follows that our hopset guarantees a stretch
of

$1+\epsilon_{\lambda}=\left(1+\frac{\epsilon^{\prime\prime}}{2\lambda}\right)^{\lambda}\leq
1+\epsilon^{\prime\prime}.$

The hopbound $h_{\ell}$ now translates to

$h_{\ell}=O\left(\frac{\lambda\ell{\log
n}}{\epsilon^{\prime\prime}}\right)^{\ell}=O\left(\frac{\lambda({\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1}){\log
n}}{\epsilon^{\prime\prime}}\right)^{\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1}.$
(19)

We set $\beta=h_{\ell}$. Write now $\epsilon=\epsilon^{\prime\prime}$. Observe
that this setting of $\beta$ is consistent with eq. 2. See Lemma 3.1 for the
time and work complexities, and eq. 10 for the size. We conclude:

######  Theorem 3.7.

Given a weighted undirected graph $G=(V,E,\omega)$ on $n$ vertices with aspect
ratio $\Lambda$, and parameters $0<\epsilon<1$, $\kappa=2,3,\dots$, and
$0<\rho<1/2$, our algorithm deterministically computes a
$(1+\epsilon,\beta)$-hopset $H$ of size at most
$\lceil{\log\Lambda}\rceil\cdot n^{1+\frac{1}{\kappa}}$ in
$O({\log\Lambda}({\log\kappa\rho}+1/\rho)\beta{\log^{2}n})$ time in the PRAM
CREW model using $O((|E|+n^{1+\frac{1}{\kappa}})\cdot n^{\rho})$ processors,
where

$\beta=O\left(\frac{{\log{\Lambda}}{\log
n}({\log\kappa\rho}+1/\rho)}{\epsilon}\right)^{\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1}.$

Note also that for the result to be meaningful, we must have
$\kappa,1/\rho=O({\log n})$, and thus ${\log(\kappa\rho)}+1/\rho=O({\log n})$.
Hence, $\beta=\left(\frac{{\log\Lambda}{\log
n}}{\epsilon}\right)^{O({\log\kappa\rho}+1/\rho)}$, and the running time is
bounded by $\left(\frac{{\log\Lambda}{\log
n}}{\epsilon}\right)^{O({\log\kappa\rho}+1/\rho)}$ as well.

Using the reduction provided in Appendix C, one can eliminate the dependence
of our result on the aspect ratio $\Lambda$ (see Theorem C.2). Specifically,
we show that one can obtain a $(1+\epsilon,\beta)$-hopset of size at most
$O\left(n^{1+\frac{1}{\kappa}}\cdot{\log n}\right)$, using
$O\left(n^{\rho}{\log n}\left(|E|+n^{1+\frac{1}{\kappa}}\cdot{\log
n}\right)\right)$ processors and
$O(({\log\kappa\rho}+1/\rho)\beta{\log^{3}n})$ time, where

$\beta=O\left(\frac{{\log^{2}n}({\log\kappa\rho}+1/\rho)}{\epsilon}\right)^{\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1}.$

Given a $(1+\epsilon,\beta)$-hopset $H$ for a graph $G=(V,E)$, one can execute
a Bellman-Ford exploration from a vertex $v\in V$ limited to $\beta$ hops.
Such an exploration requires $O(\beta{\log n})$ time and uses $O(1)$
processors to simulate every vertex and every edge of $E\cup H$. For every
vertex $u\in V$, this exploration provides the $\beta$-hop bounded distance
between $u$ and the source $v$, which is at most $(1+\epsilon)d_{G}(u,v)$.
Therefore, our hopset can be used to solve the $(1+\epsilon)$-approximate-
single-source-shortest distance (aSSSD) problem. Moreover, given a set of
sources $S$, one can execute $|S|$ parallel Bellman-Ford explorations, each
limited to $\beta$ hops, and solve the $(1+\epsilon)$-approximate-multiple-
source-shortest distance (aMSSD) problem. Executing $|S|$ Bellman-Ford
explorations limited to $\beta$ hops can therefore be performed in
$O(\beta{\log n})$ time, using $O(|S|)$ processors to simulate every vertex
and every edge of $E\cup H$.

######  Theorem 3.8.

Given a weighted undirected graph $G=(V,E,\omega)$ on $n$ vertices, parameters
$0<\epsilon<1$, $\kappa=2,3,\dots$, and $0<\rho<1/2$, and a set of sources
$S\subseteq V$, our deterministic algorithm computes
$(1+\epsilon)$-approximate-distances for all pairs of vertices in $S\times V$
in $O(({\log\kappa\rho}+1/\rho)\beta{\log^{3}n})$ time in the PRAM CREW model
using $O\left(n^{\rho}{\log n}\left(|E|+n^{1+\frac{1}{\kappa}}\cdot{\log
n}\right)\right)$ processors, where

$\beta=O\left(\frac{\log
n}{\epsilon}\right)^{O({\log\kappa\rho}+\frac{1}{\rho})}.$

In particular, for the single-source $(1+\epsilon)$-approximate shortest
distance problem, one can set $\rho=1/\kappa$, and obtain a deterministic
polylogarithmic-time algorithm (the time is $\left(\frac{{\log
n}}{\epsilon}\right)^{O(1/\rho)}$), with $O(|E|\cdot n^{\rho})$ processors. To
our knowladge, this is the first deterministic polylogarithmic time algorithm
for this problem that employs less than $O(n^{\omega})$ processors [Zwi98].
(Here, $\omega$ is the matrix multiplication exponent.)

##  4 Path-Reporting Hopsets

In this section, we modify our algorithm and show that the modified algorithm
constructs path-reporting hopsets. Roughly speaking, a hopset is called path-
reporting if it can be used to retrieve actual paths, and not just approximate
distances. Unlike previous path-reporting hopsets [EN17b, EN19], our
construction enables us to retrieve a $(1+\epsilon)$-SPT (see below).

Given a graph $G=(V,E)$, a source $s\in V$ and a parameter $0<\epsilon<1$, we
compute in polylogarithmic time a $(1+\epsilon)$-approximate-single-source-
shortest-path tree (henceforth, $(1+\epsilon)$-SPT) $T=(V,E_{T})$ with
$E_{T}\subseteq E$, rooted at $s$. For every vertex $v\in V$, the distances in
the tree $T$ will satisfy

$d_{T}(s,v)\leq(1+\epsilon)d_{G}(s,v).$

Moreover, every vertex $v\in V$ will know its parent with respect to $T$ and
also the distance $d_{T}(s,v)$ between $v$ and the source $s$.

We compute a $(1+\epsilon)$-SPT rooted at $s$ in the following way. First, a
$(1+\epsilon,\beta)$-hopset $H$ for $G$ is constructed. A Bellman-Ford
exploration is executed from $s$ in the graph $\mathcal{G}=(V,E\cup H)$ to
depth $\beta$. Let $\mathcal{T}$ be the shortest path tree in $\mathcal{G}$
obtained by the exploration. For every vertex $v\in V$, the fields $p(v),d(v)$
are initialized to be the parent of $v$ with respect to the tree
$\mathcal{T}$, and the distance $d_{\mathcal{T}}(s,v)$ between $s$ and $v$ in
$\mathcal{T}$, respectively. Note that some of the edges of $\mathcal{T}$ may
be edges of the hopset $H=\bigcup_{k\in[k_{0},\lambda]}H_{k}$.

The algorithm proceeds for $\lambda-k_{0}+1$ iterations. The input for every
iteration $j\in[0,\lambda-k_{0}]$ is a tree $\mathcal{T}_{\lambda-j}$ rooted
at the source vertex $s$. Moreover, we will show that the tree
$\mathcal{T}_{\lambda-j}$ contains only edges of the graph
${\mathcal{G}}_{\lambda-j}=(V,E\cup\bigcup_{k^{\prime}\in[k_{0},\lambda-j]}H_{k^{\prime}})$.
The input $\mathcal{T}_{\lambda}$ for the first iteration, i.e., $j=0$, is the
tree $\mathcal{T}$. For every iteration $j\in[0,\lambda-k_{0}]$, denote
$k=\lambda-j$. During every iteration $j\in[0,\lambda-k_{0}]$, edges of the
hopset $H_{k}$ that belong to $\mathcal{T}_{k}$ are removed from
$\mathcal{T}_{k}$. Each hopset edge $(v,v^{\prime})$ in $\mathcal{T}_{k}$ is
replaced by a path from $G_{k-1}$ between the vertices $v$ and $v^{\prime}$,
with weight no greater than $\omega_{H_{k}}(v,v^{\prime})$. The details of
this edge-replacing process are discussed later in the sequel. At the end of
this process, each vertex $v\in V\setminus\\{s\\}$ is left with a single
parent. The graph that contains all the edges from vertices in
$V\setminus\\{s\\}$ to their respective parents is the input
$\mathcal{T}_{k-1}$ for the next iteration. We will later show that for every
$k\in[k_{0},\lambda]$, the graph $\mathcal{T}_{k}$ is indeed a tree rooted at
$s$, and that all its edges belong to $E\cup\bigcup_{j\in[k_{0},k]}H_{j}$.

Note that a vertex $v\in V$ may belong to a path from $G_{k-1}$ for more than
one hopset edge in $H_{k}$. The vertex $v$ will update its parent and distance
estimate according to the edge that provides it with the smallest distance
estimate. In particular, during this iteration, vertices $v\in V$ that have
$(p(v),v)\in E\cup\bigcup_{k^{\prime}\in[k_{0},k-1]}H_{k^{\prime}}$, update
their distance estimate and parent only when it improves upon their existing
distance estimate.

When this process terminates, each vertex $v\in V$ knows a parent $p(v)$ such
that $(p(v),v)\in E$. The output of the procedure is the tree
$T=\mathcal{T}_{k_{0}-1}$. We will show that this tree contains only edges
from the original graph $G$. We note that when the edge-replacing process
terminates, some vertices $v\in V$ may have a distance estimate $d(v)$ that is
slightly higher than the actual distance $d_{T}(s,v)$. Therefore, we use a
pointer-jumping algorithm, described in Section 4.2, to compute distances in
$T$. This completes the high-level description of the procedure. The
pseudocode of the algorithm is given in Algorithm 1.

Algorithm 1 Path Reporting Overview

1:Input: a weighted, undirected graph $G=(V,E,\omega)$, a source $s\in V$

2:Output: a $(1+\epsilon)$-approximate shortest path tree $T$ rooted at $s$,
such that every vertex $v\in V$ knows its parent $p(v)$ w.r.t. $T$, and
$d(v)=d_{T}(s,v)$

3:compute $(1+\epsilon,\beta)$-hopset $H=\bigcup_{k\in[k_{0},\lambda]}H_{k}$
with weights $\omega_{H}$ for $G$

4:$\mathcal{G}=(V,E\cup H,\omega_{\mathcal{G}})$ where
$\omega_{\mathcal{G}}(u,v)={\min\\{\omega(u,v),\omega_{H}(u,v)\\}}$ for all
$(u,v)\in E\cup H$

5:execute a Bellman-Ford exploration from $s$, limited to $\beta$ hops in the
graph $\mathcal{G}$, and let $\mathcal{T}=\mathcal{T}_{\lambda}$ be the
resulting tree

6:for $k=\lambda,\lambda-1,\dots,k_{0}$ do

7: Let $\mathcal{T}_{k-1}$ be the tree obtained by replacing edges of
$\mathcal{T}_{k}$ that belong to $H_{k}$ with edges of $E\cup H_{k-1}$

8:$T=\mathcal{T}_{k_{0}-1}$

9:execute pointer-jump algorithm to obtain $d(v)=d_{T}(s,v)$ for all $v\in V$

###  4.1 Replacing Hopset Edges

In this section, we describe the execution of every iteration $j\in[0,\lambda-
k_{0}]$. Denote $k=\lambda-j$.

We begin by introducing a property of hopset edges. A hopset edge $(u,v)$ that
belongs to some hopset $H_{k}$ is said to have the memory property, if it is
associated with an array $A(u,v)$ that contains a path $\pi_{G_{k-1}}(u,v)$
from the graph $G_{k-1}$ between the vertices $u$ and $v$, with weight at most
$\omega_{k}(u,v)$. Recall that $\omega_{k}$ is the weight function of the
graph $G_{k}$, i.e., for every edge $(u,v)\in E\cup H_{k}$ the weight
$\omega_{k}(u,v)$ is the minimum between the weight of $(u,v)$ in the original
graph $G$, and in the hopset $H_{k}$. The path $P=\pi_{G_{k-1}}(u,v)$ is also
required to contain at most $\sigma$ hops, for some parameter $\sigma$ that
will be specified in the sequel. For every vertex $x$ along $P$, the array
$A(u,v)$ also contains the distance of $x$ from the endpoints $u$ and $v$,
along the path $P$. The path $P$ is also referred to as the memory-path of the
edge $(u,v)$.

We assume that all hopset edges of $H$ possess the memory property. Moreover,
for edges that belong to more than one hopset among
$H_{k_{0}},H_{k_{0}+1},\dots,H_{\lambda}$, we assume that they satisfy the
memory property w.r.t. all hopsets to which they belong. In Section 4.3 we
show how to modify the construction of hopsets in order to guarantee this
property, and specify the value of $\sigma$.

For convenience, we imagine that the path $s-v$ between the source $s$ and
some vertex $v$ in $\mathcal{T}_{k}$, goes from left to right, and so also go
the paths $\pi(p(u),u)$, for every vertex $u$ and its parent $p(u)$. Consider
a vertex $v\in V$ such that $(p(v),v)\in H_{k}$, and let $A(p(v),v)=\langle
p(v)=x_{0},x_{1},\dots,x_{t}=v\rangle$ be the memory path of $(p(v),v)$. The
vertex $v$ is responsible for replacing the edge $(p(v),v)$ in
$\mathcal{T}_{k}$ with the memory path of $(p(v),v)$. Specifically, $v$ will
set its parent to be $x_{t-1}$. (There are processors associated with the
vertex $v$, and these processors will perform these operations.) It will also
inform all vertices $x_{1},x_{2},\dots,x_{t-1}$ that they belong to the memory
path $A(p(v),v)$. For this end, we use a global array $M$ of size $\sigma\cdot
n$, such that every vertex $v\in V$ has $\sigma$ cells in $M$ associated with
it. We will soon provide more details about the way that the algorithm
manipulates with the array $M$.

For every index $i\in[1,t-1]$ let $d_{\pi}(p(v),x_{i})$ be the distance from
$p(v)$ to $x_{i}$ on the path $\pi=A(p(v),v)$. Let $d^{\prime}_{v}(x_{i})$ be
the distance estimate that the vertex $v$ has for the vertex $x_{i}$, i.e.,
$d^{\prime}_{v}(x_{i})=d(p(v))+d_{\pi}(p(v),x_{i})$. This estimate corresponds
to a path obtained by concatenating the $s-p(v)$ path in $\mathcal{T}_{k}$
with the $p(v)-x_{i}$ subpath of the path $\pi$. Let
$p^{\prime}_{v}(x_{i})=x_{i-1}$, i.e., $p^{\prime}_{v}(x_{i})$ is the neighbor
of $x_{i}$ along the path $\pi$, that is closer to $p(v)$ than $x_{i}$.

For every index $i\in[1,t-1]$, the vertex $v$ writes the triplet $\langle
x_{i},d^{\prime}_{v}(x_{i}),p^{\prime}_{v}(x_{i})=x_{i-1}\rangle$ to the array
$M$. Then, the vertex $v$ updates its parent $p(v)$ to be its left neighbor on
the path $\pi(p(v),v)$, i.e., $x_{t-1}$. See Figure 6 for an illustration.
Observe that at this time point, for every vertex $v\in V$, the edge
$(p(v),v)$ is either an edge from the original graph $G$, or it belongs to
some hopset $H_{k^{\prime}}$ where $k^{\prime}<k$. This is since the input
tree $\mathcal{T}_{k}$ contains edges from the set
$E\cup\bigcup_{k^{\prime}\in[k_{0},k]}H_{k^{\prime}}$. During the current
iteration, every edge of $H_{k}$ in $\mathcal{T}_{k}$ is deleted, and the only
edges that are added to the tree $\mathcal{T}_{k}$ are edges from the graph
$G_{k-1}$.

Figure 6: Removing hopset edges from the tree $\mathcal{T}_{k}$. In the
figure, the thick curved lines depict edges of $\mathcal{T}_{k}$. The straight
lines depict the edges of $G_{k-1}$ in the memory path of $(p(v),v)$. The
numbers above each edge represent its weight. The edge $(p(v),v)$ is an edge
of the hopset $H_{k}$. The vertex $v$ writes to $M$ the three elements in $M$,
which it computes using the array $A(p(v),v)$, and the distance estimate
$d(p(v))$.

Some vertices $x\in V$ may appear on more than one hopset edge. The array $M$
is sorted according to IDs. Ties are broken according to distance estimates.
Then, every vertex $x\in V$ uses a binary search to find the first entry
$M[ind]$ in $M$ that contains its ID. If the entry $M[ind]$ contains a
distance estimate that is smaller than $d(x)$, then $x$ updates its distance
estimate and its parent $p(x)$ accordingly. Otherwise, it ignores the new
information.

Observe that each edge added to the tree $\mathcal{T}_{k}$ by this procedure
is an edge of the graph $G_{k-1}$. It follows that at this point, every edges
of the tree $\mathcal{T}_{k}$ either belongs to $E$, or to some hopset
$H_{k^{\prime}}$ where $k^{\prime}<k$. Let $\mathcal{T}_{k-1}$ be the graph
obtained from $\mathcal{T}_{k}$ when the $j$th iteration terminates.

This completes the description of the $j$th iteration of the edge-replacing
procedure.

Next, we show that after every iteration $j\in[0,\lambda-k_{0}]$ of the
algorithm, the tree $\mathcal{T}_{\lambda-j-1}$ is a $(1+\epsilon)$-SPT rooted
at $s$. Note also that all its edges belong to
$E\cup\bigcup_{k^{\prime}\in[k_{0},\lambda-j-1]}H_{k^{\prime}}$. We begin by
showing that at the end of every iteration $j$, $\mathcal{T}_{\lambda-j-1}$ is
indeed a tree. Recall that every vertex (other than $s$) has only one parent
in $\mathcal{T}_{\lambda-j-1}$. Therefore, the number of edges in
$\mathcal{T}_{\lambda-j-1}$ is $n-1$. The following lemma shows that there are
no cycles in $\mathcal{T}_{\lambda-j-1}$, and as a result, it follows that
$\mathcal{T}_{\lambda-j-1}$ is a tree. For notational purposes, we introduce
another iteration to the algorithm, $j=\lambda-k_{0}+1$. As
$H_{k_{0}-1}=\emptyset$, this iteration does nothing.

######  Lemma 4.1.

At the beginning of every iteration $j\in[0,\lambda-k_{0}+1]$, for every
vertex $x\in V\setminus\\{s\\}$ we have $d(x)>d(p(x))$.

###### Proof.

Assume inductively that the claim holds at the beginning of iteration $j$, for
some $j\in[0,\lambda-k_{0}]$, and prove that it holds also at the end of the
$j$th iteration . Note that at the beginning of iteration $0$, the tree
$\mathcal{T}_{\lambda}$ and the distance estimates are a result of a Bellman-
Ford exploration in the graph $\mathcal{G}$, and so the claim holds. (Recall
that the minimal edge weight is $1$, and therefore all edge weights are
positive.)

Consider some iteration $j\in[0,\lambda-k_{0}]$, and let $k=\lambda-j$.
Consider a vertex $x\in V\setminus\\{s\\}$. The proof splits into two cases:

Case 1: $x$ did not change its distance estimate and its parent during the
$j$th iteration. Then, by the induction hypothesis, at the beginning of the
$j$th iteration, the distance estimate of $p(x)$ is smaller than the distance
estimate of $x$. Recall that distance estimates never increase throughout the
algorithm. It follows that at the end of the $j$th iteration, we also have
$d(x)>d(p(x))$.

Case 2: $x$ has changed its distance estimate or its parent during the $j$th
iteration. Let $(p(v),v)\in H_{\lambda-j}$ be the edge according to which $x$
changed its fields, and let $x^{\prime}$ be the left neighbor of $x$ along the
memory path of $(p(v),v)$. Note that $x^{\prime}$ becomes the new parent of
$x$.

If $x^{\prime}=p(v)$ then $x$ sets its parent to be $p(v)=x^{\prime}$, and its
estimate to be
$d(p(v))+\omega(p(v),x)=d(x^{\prime})+\omega(p(v),x)>d(x^{\prime})$.

Since the distance estimate of $x^{\prime}$ never increases, at the end of the
iteration we have $d(x)>d(x^{\prime})$.

Otherwise, $x^{\prime}\neq p(v)$. Therefore, the vertex $v$ wrote to $M$ the
distance estimate (and parent) that $x^{\prime}$ gets according to the memory
path $(p(v),v)$. This distance estimate is smaller than the estimate given to
$x$ by $v$. It follows that at the end of the iteration, we have
$d(x)>d(x^{\prime})$. ∎

######  Lemma 4.2.

After $\lambda-k_{0}$ iterations of the algorithm, $T=\mathcal{T}_{k_{0}-1}$
is a $(1+\epsilon)$-SPT rooted at $s$. Moreover, all edges of
$\mathcal{T}_{k_{0}-1}$ belong to the original graph $G$.

###### Proof.

For the first assertion of the lemma, recall that at the beginning of the
first iteration, the tree $\mathcal{T}_{\lambda}$ is a $(1+\epsilon)$-SPT
rooted at $s$. By Lemma 4.1 and since there are exactly $n-1$ edges in every
subgraph
$\mathcal{T}_{\lambda},\mathcal{T}_{\lambda-1},\dots,\mathcal{T}_{k_{0}-1}$,
we conclude that every subgraph
$\mathcal{T}_{\lambda},\mathcal{T}_{\lambda-1},\dots,\mathcal{T}_{k_{0}-1}$,
is a spanning tree of
$\mathcal{G}_{\lambda},\mathcal{G}_{\lambda-1},\dots,\mathcal{G}_{k_{0}-1}$,
respectively. Since distances can only decrease during the algorithm, we have
that at the beginning of every iteration $j\in[0,\lambda-k_{0}+1]$, the tree
$\mathcal{T}_{\lambda-j}$ is a $(1+\epsilon)$-SPT of $\mathcal{G}_{\lambda-j}$
rooted at $s$.

For the second assertion of the lemma, observe that during every iteration
$j\in[0,\lambda-k_{0}]$, every edge of the hopset $H_{\lambda-j}$ that
belonged to $\mathcal{T}_{\lambda-j}$ is eliminated. Every edge that is added
to $\mathcal{T}_{\lambda-j-1}$ during the $j$th iteration belongs to the graph
$G_{\lambda-j-1}$, i.e., it is either an edge of $E$ or an edge of
$H_{\lambda-j-1}$. It follows that after $\lambda-k_{0}$ iterations, the tree
$\mathcal{T}_{k_{0}-1}$ does not contain any hopset edges, and so it contains
only edges of the original graph $G$. ∎

###  4.2 Computing Exact Distance Estimates

When the algorithm terminates, some vertices $v\in V$ may have an estimate
$d(v)>d(p(v))+\omega(p(v),v)$. To ensure that for every vertex $v$ we have
$d(v)=d(p(v))+\omega(p(v),v)$, we use a pointer-jumping procedure (see, e.g.,
[SV82]). As a result of this procedure, for every vertex $v\in V$, the
estimate that it will have will be equal to its distance in
$T=\mathcal{T}_{k_{0}-1}$ to the root $s$ of ${T}$.

For the source vertex $s$, set $p(s)=s$ and $\omega(s,s)=0$. For every vertex
$v\in V$, define $q(v)=p(v)$. In addition, every vertex maintains a field
$d^{\prime}(v)$ that contains the distance in ${T}$ from $v$ to $q(v)$. This
field is initialized to contain $d^{\prime}(v)=\omega(p(v),v)$. Then, for
${\log n}$ iterations, each vertex updates:

$\begin{array}[]{clclcl}d^{\prime}(v)=d^{\prime}(v)+d^{\prime}(q(v)),\\\
q(v)=q(q(v)).\end{array}$

Next, we show that after ${\log n}$ iterations, we have
$d^{\prime}(v)=d_{{T}}(s,v)$. We will consider the initialization step as
iteration $0$ of the procedure. For every iteration $j\in[0,{\log n}]$, denote
$q_{j}(v)$ and $d^{\prime}_{j}(v)$ the values of the fields
$q(v),d^{\prime}(v)$ at the end of the $j$th iteration, respectively.

######  Lemma 4.3.

At the end of every iteration $j\in[0,{\log n}]$, we have
$d^{\prime}_{j}(v)=d_{T}(q_{j}(v),v)$.

###### Proof.

The proof is by induction on the index of the iteration $j$. For $j=0$, recall
that $q(v)=p(v)$ and
$d^{\prime}_{0}(v)=d^{\prime}(v)=\omega(p(v),v)=d_{T}(p(v),v)$, and so the
claim holds.

Assume that the claim holds for some $j\in[0,{\log n}-1]$ and prove it for
$j+1$. Let $v\in V$. At the end of iteration $j+1$, we have
$d^{\prime}_{j+1}(v)=d^{\prime}_{j}(v)+d^{\prime}_{j}(q(v))$ and also
$q_{j+1}(v)=q_{j}(q_{j}(v))$. By the induction hypothesis, we have

$d^{\prime}_{j+1}(v)=d^{\prime}_{j}(v)+d^{\prime}_{j}(q(v))=d_{T}(q_{j}(v),v)+d_{T}(q_{j}(q_{j}(v)),q_{j}(v))=d_{T}(q_{j}(q_{j}(v)),v)=d_{T}(q_{j+1}(v),v).$

∎

After ${\log n}$ iterations, each vertex $v\in V$ updates
$d(v)=d^{\prime}_{{\log n}}(v)$. Observe that, for every vertex $v\in V$ we
have $q_{{\log n}}(v)=s$. Therefore, Lemma 4.3 implies that when the procedure
terminates, we have $d(v)=d_{{T}}(s,v)$.

###  4.3 Constructing the Path-Reporting Hopset

In this section we modify our algorithm for building hopsets, so that every
hopset edge will satisfy the memory property (see Section 4.1).

Let $k\in[k_{0},\lambda]$, and let $i\in[0,\ell]$. We say that a vertex $v$
that belongs to a cluster $C\in P_{i}$ has a cluster-memory, if it is
associated with arrays $CP(v)$ and $CD(v)$ that contain a path $P$ from $v$ to
the center $r_{C}$ of the cluster $C$, and the distances of each vertex in
$CP(v)$ from the center of the cluster along the path $CP(v)$, respectively.
Moreover, the path $P$ is required to be contained in $E\cup H_{k-1}$. See
Figure 7 for an illustration. If $v$ does not belong to a cluster in phase
$i$, we say that it has a cluster-memory _vacuously_.

Recall that a hopset edge $(u,v)$ is added to $H_{k}$ in phase $i$, because
some exploration that has originated, w.l.o.g., in the cluster of $u$ has
reached the cluster of $v$. Specifically, the vertex $u$ wrote some
information regarding its own exploration to its memory cells. This
information was then read by some other vertices, which in turn wrote some
information regarding $u$’s exploration to their memory cells, etc. For
convenience, we will say that when a vertex $u\in V$ initiates an exploration,
it sends a message $m$ along edges of the graph. If a vertex $v$ was
discovered by this exploration, and added an edge to $u$, we say that the
message $m$ has reached $v$. Let $d$ be the weight of the hopset edge $(u,v)$.
We require the message $m$ to contain a path from $u$ to $v$ with weight at
most $d$.

When the vertex $u$ first writes the message $m$ to its memory, it writes the
triplet $\langle u,\langle u\rangle,\langle 0\rangle\rangle$. The first field
in $m$ is the ID of the vertex in which the message originated. The second
field in $m$, is a list $\mathcal{L}_{P}$ that contains the path of $G_{k-1}$
that this message has traversed. The third field in $m$, is a list
$\mathcal{L}_{dist}$ of the distances the message has traversed before
arriving at each vertex of the list, such that the $j$th distance in
$\mathcal{L}_{dist}$ corresponds to the $j$th vertex on $\mathcal{L}_{P}$. See
Figure 7 for an illustration.

Figure 7: The path of a message from a cluster center to a vertex $x_{3}$. The
solid arrows represent the path that the message traversed. The dashed lines
represent the path in $G_{k-1}$ between $u_{3}$ and its cluster center $r$,
that is stored in the array $CP(u_{3})$. The small arrays depict the arrays
$CP(u_{3}),CD(u_{3})$. From $r$, the message reaches the vertex $u_{3}$, which
appends $CP(u_{3})$ and $CD(u_{3})$ to the message. Then, the message is
delivered to $x_{1},x_{2},x_{3}$, which in turn append their IDs and the total
weighted length that the message has traveled to get to them.

Every vertex $x$ that receives a message $m$ adds the required information to
the path and distance lists in $m$. Every vertex $x$ that receives this
message from its neighbor $y$ in $G_{k-1}$ adds to $m$ the weight
$\omega_{k-1}(y,x)$ to the weight field of $m$, and its ID to the path field,
before delivering it further. When a message $m=\langle
x,\mathcal{L}_{P},\mathcal{L}_{dist}\rangle$ originated at a vertex $x$ is
delivered from a vertex $z\in C$ to the center $r$ of $C$ along a hopset edge
$(z,r)$, it is the responsibility of the vertex $z$ to update the information
in $\mathcal{L}_{P},\mathcal{L}_{dist}$ according to $CP(z),CD(z)$. Therefore,
$z$ concatenates the path between $z$ and $r$ (i.e., $CP(z)$) to the field
$\mathcal{L}_{P}$ in the message $m$. Additionally, it also computes for every
vertex $w$ along $CP(z)$ the distance from the source $x$, according to
$CD(z)$ and the message $m$. The list of distances is concatenated to the list
$\mathcal{L}_{dist}$. Similarly, when a message $m=\langle
x,\mathcal{L}_{P},\mathcal{L}_{dist}\rangle$ is delivered to a vertex $z\in C$
from the center $r$ of $C$ along a hopset edge $(z,r)$, it is the
responsibility of the vertex $z$ to update the information in
$\mathcal{L}_{P},\mathcal{L}_{dist}$ according to $CP(z),CD(z)$.

Next, we explain how every vertex $v$ that belongs to a cluster $C\in P_{i}$
maintains the arrays $CP(v)$ and $CD(v)$. Consider a vertex $v\in V$. In phase
$0$, the cluster of $v$ is a singleton, and so it writes $CP(v)=\langle
v\rangle$ and $CD(v)=\langle 0\rangle$, and therefore it has a cluster-memory
in phase $0$.

Assume inductively that every vertex $v\in V$ has a cluster-memory in phase
$i$, for some $i\in[0,\ell-1]$. We will show that $v$ also has a cluster-
memory in phase $i+1$. If $v$ does not belong to a cluster in $P_{i+1}$, then
the claim holds vacuously. Consider the case where $v$ belongs to a cluster
$\widehat{C}\in P_{i+1}$, formed in phase $i$ around a cluster $C\in P_{i}$.
Let $r_{C}$ be the center of $C$, and let $C^{\prime}\in P_{i}$ be the cluster
such that $v\in C^{\prime}$. If $C={C^{\prime}}$, than by the induction
hypothesis $v$ has a cluster-memory also in phase $i+1$. Otherwise, the center
$r_{C^{\prime}}$ of the cluster $C^{\prime}$ has added the superclustering
edge $(r_{C},r_{C^{\prime}})$ to the hopset. Note that the memory property of
the edge $(r_{C},r_{C^{\prime}})$ relies only on edges of $G_{k-1}$, and on
the fact that all vertices have cluster-memory in phase $i$. Therefore, the
edge $(r_{C},r_{C^{\prime}})$ satisfies the memory property, i.e., it is
associated with an array $A(r_{C},r_{C^{\prime}})$ that contains the vertices
of a path between $r_{C}$ and $r_{C^{\prime}}$, and the distance of all
vertices along this path from its endpoints. Since the vertex $v$ has a
cluster-memory in phase $i$, the arrays $CP(v)$ and $CD(v)$ contain the
details of a path to $r_{C^{\prime}}$. The vertex $v$ adds to $CP(v)$ and
$CD(v)$ the information from the array $A(r_{C},r_{C^{\prime}})$, and updates
the distances accordingly. Therefore, the vertex $v$ has cluster-memory in
phase $i+1$.

Note that the length of the vertex arrays ($CP(\cdot)$ and $CD(\cdot)$) are
dominated by the length of the edges arrays ($A(\cdot,\cdot)$). It is left to
bound the length of the array $A(r_{C},r_{C^{\prime}})$ for every hopset edge.

Recall that $\sigma_{0}=0$ and $\sigma_{i+1}=(4{\log
n}+1)\sigma_{i}+2(2\beta+1){\log n}$, for all $i=1,2,\dots,\ell$.

Lemma 2.9 implies that the number of hops along the path that implements an
interconnection edge added to the hopset in phase $i$ of the algorithm, for
$i\in[0,\ell]$, is at most $2\sigma_{i}+(2\beta+1)$, and that the weight of
this path is at most the weight of the edge in the hopset.

For superclustering edges, Lemma 2.3 implies that the number of hops along the
path that implements a superclustering edge added to the hopset in phase $i$
of the algorithm, for $i\in[0,\ell-1]$, is at most $\sigma_{i+1}-\sigma_{i}$,
and that the weight of this path is at most the weight of the edge in the
hopset.

Note that $2\sigma_{\ell}+(2\beta+1)>\sigma_{\ell}-\sigma_{\ell-1}$, and
therefore, the maximal number $\sigma$ of edges in an array of a hopset edge
is set to be $\sigma=2\sigma_{\ell}+(2\beta+1)$. We now provide an explicit
bound on $\sigma_{i}$, for all $i\in[0,\ell]$.

######  Lemma 4.4.

For every $i\in[0,\ell]$, we have

$\sigma_{i}=2(2\beta+1){\log n}\cdot\sum_{j=0}^{i-1}(4{\log n}+1)^{j}.$

###### Proof.

The proof is by induction on the index of the phase $i$. For $i=0$, both sides
of the equation are equal to $0$.

Assume that the claim holds for some $i\in[0,\ell-1]$, and prove it holds for
$i+1$. By definition and the induction hypothesis, we have

$\begin{array}[]{lclcllcclclclclclc}\sigma_{i+1}&=&2(2\beta+1){\log n}+(4{\log
n}+1)\sigma_{i}\\\ &=&2(2\beta+1){\log n}+(4{\log n}+1)\left[2(2\beta+1){\log
n}\cdot\sum_{j=0}^{i-1}(4{\log n}+1)^{j}\right]\\\ &=&2(2\beta+1){\log
n}+\left[2(2\beta+1){\log n}\cdot\sum_{j=0}^{i-1}(4{\log n}+1)^{j+1}\right]\\\
&=&2(2\beta+1){\log n}\cdot\sum_{j=0}^{i}(4{\log n}+1)^{j}.\par\end{array}$

∎

Observe that Lemma 4.4 implies that

$\begin{array}[]{lclcllcclclclclclc}\sigma_{i}=2(2\beta+1){\log
n}\cdot\left[\frac{(4{\log n}+1)^{i}-1}{4{\log
n}}\right]\leq\frac{1}{2}(2\beta+1)\cdot{(4{\log n}+1)^{i}}.\end{array}$

Recall that by eq. 19 we have $\beta=O\left(\frac{\lambda\ell{\log
n}}{\epsilon}\right)^{\ell}$. It follows that the parameter $\sigma$ satisfies

$\sigma=2\sigma_{\ell}+2\beta+1=O(\sigma_{\ell})=O(\beta\cdot{(4{\log
n}+1)^{\ell}}).$ (20)

Observe that the current variant of the algorithm differs from the algorithm
described in Section 2 only by the number of processors it uses. By using
$O(\sigma n^{\rho})$ processors to simulate every edge and every vertex, one
can satisfy the memory property and maintain the same running time as in the
variant from Section 2. This is summarized in the following theorem.

######  Theorem 4.5.

Given a weighted undirected graph $G=(V,E,\omega)$ on $n$ vertices with aspect
ratio $\Lambda$, and parameters $0<\epsilon<1$, $\kappa=2,3,\dots$, and
$0<\rho<1/2$, our algorithm deterministically computes a path-reporting
$(1+\epsilon,\beta)$-hopset $H$ of size at most
$\lceil{\log\Lambda}\rceil\cdot n^{1+\frac{1}{\kappa}}$ in
$O({\log\Lambda}({\log\kappa\rho}+1/\rho)\beta{\log^{2}n})$ time in the PRAM
CREW model using $(|E|+n^{1+\frac{1}{\kappa}})\cdot\beta\cdot n^{\rho}\cdot
O({\log
n})^{\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1}$
processors, where

$\beta=O\left(\frac{{\log{\Lambda}}{\log
n}({\log\kappa\rho}+1/\rho)}{\epsilon}\right)^{\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1}.$

Note that $\beta\cdot O({\log
n})^{\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1}=\left(\frac{{\log\Lambda}{\log
n}}{\epsilon}\right)^{O({\log\kappa\rho}+1/\rho)}$. Thus, the number of
processors is

$\left(|E|+n^{1+\frac{1}{\kappa}}\right)\cdot
n^{\rho}\cdot\left(\frac{{\log\Lambda}{\log
n}}{\epsilon}\right)^{O({\log\kappa\rho}+1/\rho)}.$

See also the discussion that follows Theorem 3.7. It is applicable to Theorem
4.5 as well.

###  4.4 Complexity Analysis

In this section, we provide the analysis of the work and time required to
compute approximate shortest paths from a single source in the graph
$G=(V,E)$.

By Theorem 4.5, the hopset $H$ can be constructed in
$O({\log\Lambda}({\log\kappa\rho}+1/\rho)\beta{\log^{2}n})$ time using
$O((|E|+n^{1+\frac{1}{\kappa}})\cdot\sigma n^{\rho})$ processors.

The Bellman-Ford exploration that computes $\mathcal{T}$ requires
$O(\beta{\log n})$ time using $O(|E|+|H|)$ processors.

The edge replacing procedure executes $\lambda-k_{0}+1=O(\lambda)$ iterations.
In each iteration $j\in[0,\lambda-k_{0}]$, each vertex $v$ that has
$(p(v),v)\in H_{\lambda-j}$ updates its parent. It also uses the array
$A(p(v),v)$ to compute distance and parent estimates to all vertices along the
memory path of $(p(v),v)$. These estimates are written to the array $M$.
Recall that the length of $A(p(v),v)$ is $O(\sigma)$. This can be executed in
$O(1)$ time, using $O(\sigma)$ processors to simulate every vertex $v\in V$.

Recall that the length of the array $M$ is $\sigma n$. Sorting $M$ using
$O(\sigma)$ processors for every vertex $v\in V$ can be performed in
$O({\log|M|})=O({\log(\sigma n)})$ time (see, e.g., [AKS83]).

Each vertex $v\in V$ uses binary search to find the smallest element in $M$
that concerns $v$ in $O({\log(\sigma n)})$ time, using a single processor. It
then updates its parent and distance estimate in constant time.

It follows that every iteration of the edge replacing procedure can be
performed using $O(\sigma)$ processors to simulate every edge of $E\cup H$ and
every vertex in $V$.

Finally, the exact distances in the tree $T$ are computed using the pointer-
jumping algorithm. This requires $O({\log n})$ time and $O(1)$ processors to
simulate every vertex.

Recall that by eq. 20, we have $\sigma=O(\beta\cdot{(4{\log
n}+1)^{\ell}})=\left(\frac{{\log\Lambda}{\log n}}{\epsilon}\right)^{O(\ell)}$.
It follows that the running time of the algorithm is dominated by
$O({\log\Lambda}({\log\kappa\rho}+1/\rho)\beta{\log^{2}n})$, which is the time
required to compute the hopset $H$, and the number of processors required for
the simulation of every vertex of $V$ and edge in $E\cup H$ is
$O(n^{\rho}\cdot\sigma)=O(\beta\cdot{(4{\log n}+1)^{\ell}}\cdot n^{\rho})$.

The following theorem summarizes the properties of the path-reporting
algorithm.

######  Theorem 4.6.

Given a weighted undirected graph $G=(V,E,\omega)$ on $n$ vertices with aspect
ratio $\Lambda$, a source vertex $s\in V$ and parameters $0<\epsilon<1$,
$\kappa=2,3,\dots$, and $0<\rho<1/2$, our algorithm deterministically computes
a $(1+\epsilon)$-SPT for $G$ rooted at $s$ in
$O({\log\Lambda}({\log\kappa\rho}+1/\rho)\beta{\log^{2}n})$ time in the PRAM
CREW model using $(|E|+n^{1+\frac{1}{\kappa}})\cdot
n^{\rho}\cdot\left(\frac{{\log\Lambda}{\log
n}}{\epsilon}\right)^{O({\log\kappa\rho}+1/\rho)}$ processors, where

$\beta=O\left(\frac{{\log{\Lambda}}{\log
n}({\log\kappa\rho}+1/\rho)}{\epsilon}\right)^{\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1}.$

In Appendices C and D, based on [KS97], we argue that the dependence on
$\Lambda$ in this result can be eliminated, while keeping the running time and
work complexity of our algorithm essentially intact.

Appendix

##  Appendix A Simulating Parallel BFS Explorations in the Virtual Graph
$\tilde{G}_{i}$

This section contains the details for the explorations in the virtual graph
$\tilde{G}_{i}$ (see Section 2.1.1 for its definition). Given a set of source
clusters $S\subseteq P_{i}$, an upper bound $x\leq n^{\rho}+1$ on the number
of parallel explorations that traverse any vertex and a distance threshold
parameter $d$, each cluster $C\in P_{i}$ will learn the IDs and distances to
(up to) $x$ sources $C^{\prime}\in S$ (including $C$ itself, if $C\in S$),
that are within (unweighted) distance at most $d$ from $C$ in the virtual
graph $\tilde{G}_{i}$.

We note that our algorithm for constructing hopsets uses the exploration
algorithm only in the case where $1\leq x\leq n^{\rho}+1$ and $d=1$ (for the
popular clusters detection), and in the case where $x=1$ and $d\geq 1$ (for
simulating a single, multiple source BFS exploration in $\tilde{G}_{i}$). We
provide here a general algorithm, but prove the correctness only for the two
scenarios that our construction uses (i.e., the scenario where $x=1$ and the
scenario where $d=1$).

###  A.1 Overview

We begin with an intuitive overview of the algorithm. At the beginning of the
algorithm, each cluster writes to its memory whether or not it belongs to the
set of sources $S$. The algorithm proceeds in pulses. In every pulse
$p\in[1,d]$, each cluster $C\in P_{i}$ aggregates the knowledge that its
neighbors in the virtual graph $\tilde{G}_{i}$ obtained so far, regarding
sources in $S$. The cluster $C$ then writes to its memory the IDs and
distances to the closest $x$ sources it has learned about so far. (Recall that
the cluster $C$ is simulated by the processors that simulate its center
$r_{C}$, and that the memory used for the simulation of $r_{C}$ is also used
for the simulation of $C$.)

Each pulse is divided into three parts. In the distributing part, each vertex
$v$ that belongs to a cluster $C\in P_{i}$ copies the information that its
cluster $C$ possesses. Note that in the first pulse, this information is
whether $C$ is in $S$ or not. Then, in the propagation part, the information
obtained by each vertex propagates to its neighbors in $G_{k-1}$.
Specifically, for $2\beta+1$ steps, each vertex $u\in V$ reads the information
obtained by its neighboring vertices in $G_{k-1}$, and updates its own
information accordingly. Finally, in the aggregation part, each cluster $C\in
P_{i}$ accumulates the information obtained by vertices $v\in C$, and updates
its information accordingly. This completes the overview of the algorithm.

###  A.2 Technical Details and Complexity Analysis

This section provides the technical details and analysis of running time and
work of the algorithm. The pseudocode of the algorithm is given in Algorithm
2.

Algorithm 2 Parallel Limited BFS Exploration

1:Input: a weighted, undirected graph $G_{k-1}=(V,E\cup
H_{k-1},\omega_{k-1})$, sets of clusters $P_{i}$, $S\subseteq P_{i}$, distance
and hop threshold parameters $(1+\epsilon_{k-1})\delta_{i},2\beta+1$, number
of explorations parameter $x$, depth parameter $d$

2:for every vertex $v\in V$ do in parallel

3: $m(v)=\ $an array of length $(deg(v)+1)\cdot x$

4: $\mathcal{L}(v)=\ $a list of length $x$

5:for every cluster $C\in P_{i}$ do in parallel

6: $m(C)=\ $an array of length $|C|\cdot x$

7: if $C\in S$ then add the tuple $\langle C,0\rangle$ as the first record of
$m(C)$

8:for $d$ iterations do

9: distribution-part:

10: for each vertex $v$ that belongs to a cluster $C\in P_{i}$ in parallel do

11: copy the first $x$ records in $m(C)$ to $m(v)$

12: propagation-part:

13: for $2\beta+1$ steps do

14: for every vertex $u\in V$ in parallel do

15: copy $\mathcal{L}(u)$ to $m(u)$

16: let $x_{1},x_{2},\dots,x_{deg(u)}$ be the neighbors of $u$ in $G_{k-1}$

17: for $t\in[1,deg(u)]$ in parallel do

18: copy $\mathcal{L}(x_{t})$ to $m(u)$ and add $\omega_{k-1}(u,x_{t})$ to the
distance value of each record

19: remove all records with distance value grater than
$(1+\epsilon_{k-1})\delta_{i}$ from $m(u)$

20: apply Algorithm 3 on $m(u)$

21: copy the first $x$ elements of $m(u)$ to $\mathcal{L}(u)$

22: aggregation-part:

23: for each vertex $v$ that belongs to a cluster $C\in P_{i}$ in parallel do

24: copy the list $\mathcal{L}(v)$ to $m(C)$

25: apply Algorithm 3 on $m(C)$

Algorithm 3 Sort Array

1:Input: an array $m[]$ that contains entries $\langle C,d\rangle$.

2:sort $m[]$ according to IDs. Break ties according to distances.

3:for every entry $ind$ in $m[]$ in parallel  do

4: if $m[ind-1]$ (if exists) has the same source as $m[ind]$ then

5: set $m[ind]=\langle null,\infty\rangle$

6:sort $m[]$ according to distances. Break ties by IDs.

At the beginning of the algorithm, each vertex $v\in V$ is allocated an empty
list $\mathcal{L}(v)$ that can contain up to $x$ elements and an array $m(v)$
of length $(deg(v)+1)\cdot x$, where $deg(v)$ is the degree of the vertex $v$
in the graph $G_{k-1}$. Each cluster $C\in P_{i}$ is allocated an array $m(C)$
of length $|C|\cdot x$. Each center $r_{C}$ of a cluster $C\in S$ writes
$\langle C,0\rangle$ to $m(C)$. The second element of the pair $\langle
C,dist\rangle$ is referred to as the distance value of the pair.

Recall that we use at least $x$ processors to simulate each vertex and each
edge of $G_{k-1}$, and that the number of edges in $G_{k-1}$ is
$|E|+|H_{k-1}|$. We now describe the distribution, propagation and aggregation
parts for each pulse $p\in[1,d]$.

Distribution part. During the distribution part of pulse $p$, each vertex $u$
that belongs to a cluster $C\in P_{i}$ copies the first $x$ records in the
array $m(C)$ to its list $\mathcal{L}(u)$. This can be executed in $O(1)$ time
using $x$ processors for each vertex.

Propagation part. The propagation part is composed of $2\beta+1$ steps. In
each step $j\in[1,2\beta+1]$, the processors that simulate each vertex $v\in
V$ copy the contents of the list $\mathcal{L}(v)$ to the array $m(v)$. In
addition, the processors that simulate each edge $(v,u)$ incident to $v$ in
the graph $G_{k-1}$ copy the contents of the list $\mathcal{L}(u)$ to $m(v)$,
and add the weight $\omega_{k}(v,u)$ to the distance value of each copied
pair. If a record in $m(v)$ now has a distance value greater than
$(1+\epsilon_{k-1})\delta_{i}$, the record is deleted. Since each vertex and
each edge are simulated by at least $x$ processors, this requires $O(1)$ time.

Observe that the array $m(v)$ might contain multiple entries regarding the
same source. Therefore, the array $m(v)$ is now sorted according to the source
ID. Ties are broken by distance. For each index $ind\in[1,|m(v)|]$, we check
if the entry $m(v)[ind-1]$ (if exists) has the same source as the entry
$m(v)[ind]$. If the answer is positive, then the entry $m(v)[ind]$ is deleted,
i.e., replaced with $\langle null,\infty\rangle$. Then, the array $m(v)$ is
sorted again, now according to distances. See Algorithm 3 for the pseudocode
of this sorting procedure. The smallest $x$ elements in $m(v)$ are copied to
the list $\mathcal{L}(v)$. This completes the description of the propagation
part.

Observe that for every vertex $v\in V$, we have that the length of the array
$m(v)$ is $(deg(v)+1)x$, i.e., polynomial in $n$. Therefore, sorting it using
$(deg(v)+1)x$ processors that simulate $v$ and its edges requires $O({\log
n})$ time [AKS83]. Copying the smallest $x$ elements in the sorted array
$m(v)$ requires $O(1)$ time, using the processors that simulate the vertex
$v$. It follows that the propagation part can be executed in $O(\beta{\log
n})$ time, using $x$ processors to simulate each edge in $G_{k-1}$, i.e.,
using $O((|E|+|H_{k-1}|)\cdot x)$ processors.

Aggregation part. For each cluster $C\in P_{i}$, each vertex $u\in C$ copies
the contents of the list $\mathcal{L}(u)$ into the array $m(C)$. To remove
duplicates and find the smallest elements in $m(C)$, the array is sorted as
described in the propagation part above (see Algorithm 3). Observe that the
size of the array $m(C)$ is $|C|\cdot x$, i.e., polynomial in $n$. Therefore,
it can be sorted in $O({\log n})$ time using $|C|\cdot x$ processors (see
[AKS83]). It follows that the aggregation part can be executed in $O({\log
n})$ time, using $O((|E|+|H_{k-1}|)\cdot x)$ processors.

To summarize, each pulse $p\in[1,d]$ can be executed in $O(\beta{\log n})$
time using $O((|E|+|H_{k-1}|)\cdot x)$ processors.

######  Corollary A.1.

Given a weighted undirected graph $G_{k-1}=(V,E\cup H_{k-1},\omega_{k-1})$ on
$n$ vertices, sets of clusters $P_{i}$, $S\subseteq P_{i}$, distance and
hopbound parameters $(1+\epsilon_{k-1})\delta_{i},2\beta+1$, number of
explorations parameter $x$ and a depth parameter $d$, Algorithm 2 can be
executed in $O(d\beta{\log n})$ time using $O((|E|+|H_{k-1}|)\cdot x)$
processors.

###  A.3 Correctness

In this section, we prove the correctness of the two variants of the algorithm
we use. The first variant is used to detect popular clusters from $P_{i}$. The
second variant is used for BFS explorations to depth $d\geq 1$ in
$\tilde{G}_{i}$.

#### A.3.1 Variant 1: Detecting Popular Clusters

In this section, we show that by setting $d=1$, $x=deg_{i}+1$ and $S=P_{i}$,
Algorithm 2 can be used for the detection of popular clusters.

For a vertex $u\in V$ and an index $j\in[0,2\beta+1]$, let
$\mathcal{N}^{j}(u)$ be the set of clusters $C\in P_{i}$ such that
$d_{G_{k-1}}^{(j)}(u,C)\leq(1+\epsilon_{k-1})\delta_{i}$, where
$d_{G_{k-1}}^{(j)}(u,C)={\min\\{d_{G_{k-1}}^{(j)}(u,v)|v\in C\\}}$. Let
$\mathcal{N}^{j}[x](u)$ be the subset of the $x$ closest reachable within $j$
hops clusters to $u$, from the set $\mathcal{N}^{j}(u)$, i.e., the set of (up
to) $x$ clusters $C$ from $\mathcal{N}^{j}(u)$ with minimal
$d^{(j)}_{G_{k-1}}(u,C)$. Ties are broken according to the cluster ID. For
convenience, we refer to the initialization, i.e., 2, 3, 4, 5, 6 and 7 of
Algorithm 2, as step $0$ of the propagation part.

######  Lemma A.2.

For every index $j\in[0,2\beta+1]$, when step $j$ of the propagation part
terminates, for every vertex $u\in V$ the list $\mathcal{L}(u)$ contains the
IDs and the $j$-hop distance from all clusters in $\mathcal{N}^{j}[x](u)$.

###### Proof.

The proof is by induction on the index of the step $j$. Consider a vertex
$u\in V$. For $j=0$, if the vertex $u$ belongs to a cluster $C\in P_{i}$, then
the set $\mathcal{N}^{0}[x](u)$ contains the cluster $C$. Otherwise, by
definition, the set $\mathcal{N}^{0}[x](u)$ is empty. Indeed, if $u$ belongs
to a cluster $C$, then the list $\mathcal{L}(u)$ contains the entry $\langle
C,0\rangle$. Otherwise, it is empty, and so the claim holds for the base case.

We assume that the claim holds for some $j\in[0,2\beta]$ and prove that it
holds also for $j+1$. Let $u$ be a vertex in $V$, and let
$C\in\mathcal{N}^{j+1}[x](u)$. If $u\in C$, then the list $\mathcal{L}(u)$
contains the element $\langle C,0\rangle$, and it will never be removed from
$\mathcal{L}(u)$. Consider the case where $u\notin C$. Let $v\in C$ such that
$d_{G_{k-1}}^{(j+1)}(u,v)=d_{G_{k-1}}^{(j+1)}(u,C)$, and let $\pi(v,u)=\langle
v=v_{0},v_{1},\dots,v_{s-1},v_{s}=u\rangle$ be a path between $u,v$ with
weight $d_{G_{k-1}}^{(j+1)}(u,C)$, where $s\leq j+1$.

By the induction hypothesis, the list $\mathcal{L}(v_{s-1})$ of the vertex
$v_{s-1}$ contains the IDs and the $j$-hop distance from all clusters in
$\mathcal{N}^{j}[x](v_{s-1})$. If $\langle
C,d^{(j)}_{G_{k-1}}(v_{s-1},C)\rangle\notin\mathcal{L}(v_{s-1})$, then by the
induction hypothesis $C\notin\mathcal{N}^{j}[x](v_{s-1})$. Therefore, there
are at least $x$ other clusters $C^{\prime}$ on the list
$\mathcal{N}^{j}[x](v_{s-1})$, with distance
$d^{(j)}_{G_{k-1}}(v_{s-1},C^{\prime})$ smaller than
$d^{(j)}_{G_{k-1}}(v_{s-1},C)$ (we assume that there are no equalities, as
ties are broken according to the clusters ID). For each such cluster
$C^{\prime}$, let $\pi(C^{\prime},v_{s-1})$ be a path with up to $j$ hops of
weight $d^{(j)}_{G_{k-1}}(v_{s-1},C^{\prime})$. See Figure 8 for an
illustration. By concatenating the edge $(v_{s-1},u)$ to every such path
$\pi(C^{\prime},v_{s-1})$, we obtain a path from $C^{\prime}$ to $u$ of at
most $j+1$ hops, and weight smaller than $d^{(j+1)}_{G_{k-1}}(u,C)$. Thus
$C\notin\mathcal{N}^{j+1}[x](u)$, contradiction.

Figure 8: The path in ${G_{k-1}}$ from the cluster
$C\in\mathcal{N}^{j+1}[x](u)$ to $u$. The gray circle depicts the cluster $C$.
The vertex $v_{s-1}$ is the neighbor of $u$ on the path from $C$ to $u$. The
dashed lines depict paths of at most $j$ hops from clusters to $v_{s-1}$. The
white circles depict clusters that are in $\mathcal{N}^{j}[x](v_{s-1})$.

Then, $\langle C,d^{(j)}_{G_{k-1}}(v_{s-1},C)\rangle\in\mathcal{L}(v_{s-1})$.
Note that $d^{(j)}_{G_{k-1}}(v_{s-1},C)=d_{G_{k-1}}^{(j)}(v,v_{s-1})$, and
that
$d_{G_{k-1}}^{(j+1)}(v,u)=d_{G_{k-1}}^{(j)}(v,v_{s-1})+\omega_{k-1}(v_{s-1},u)$.
The edge $(v_{s-1},u)$ records the element $\langle
C,d_{G_{k-1}}^{(j+1)}(v,u)\rangle$ to $m(u)$. If it is not recorded to
$\mathcal{L}(u)$ by the end of step $j+1$, it is because there exist at least
$x$ clusters that have $(j+1)$-hop bounded distance to $u$ that is smaller
than $d_{G_{k-1}}^{(j+1)}(v,u)$, contradiction. Therefore, by the end of phase
$i$, we have $\langle C,d_{G_{k-1}}^{(j+1)}(v,u)\rangle\in\mathcal{L}(u)$. ∎

We are now ready to show that Algorithm 2 can be used to detect popular
clusters. Recall that for the popular clusters detection, we set
$x=deg_{i}+1$, $d=1$ and $S=P_{i}$.

######  Lemma A.3.

Given a weighted undirected graph $G_{k-1}=(V,E\cup H_{k-1},\omega_{k-1})$ on
$n$ vertices, a set of clusters $P_{i}$, distance parameter
$(1+\epsilon_{k-1})\delta_{i}$, degree parameter $deg_{i}$ and a hopbound
$2\beta+1$, Algorithm 2 requires $O(\beta{\log n})$ time and
$O((|E|+|H_{k-1}|)\cdot n^{\rho})$ processors. When the algorithm terminates,
every cluster $C\in P_{i}$ is associated with an array $m(C)$ such that:

  1. 1.

If $C$ is popular, then the first $deg_{i}+1$ cells of $m(C)$ contain
information regarding $deg_{i}+1$ clusters from $P_{i}$. One of them is $C$,
and the other are neighboring clusters of $C$.

  2. 2.

If $C$ is _unpopular_ then $m(C)$ contains the identities and $(2\beta+1)$-hop
bounded distances in $G_{k-1}$ between $C$ and all its neighboring clusters.
In addition, the $(deg_{i}+1)$st cell in $m(C)$ is empty.

###### Proof.

By Corollary A.1, executing Algorithm 2 with $x=deg_{i}+1$, $d=1$ and
$S=P_{i}$ requires $O(\beta{\log n})$ time using $O((|E|+|H_{k-1}|)\cdot
deg_{i})$ processors.

Consider a cluster $C\in P_{i}$. Lemma A.2 implies that when the propagation
part terminates, for every vertex $v\in C$, the list $\mathcal{L}(v)$ contains
the IDs of all clusters of $\mathcal{N}^{2\beta+1}[x](v)$, and the
$(2\beta+1)$-hop bounded distances to them.

During the aggregation part of the algorithm, each vertex $v\in C$ copies
$\mathcal{L}(v)$ to $m(C)$. When 25 of Algorithm 2 terminates, the first
$deg_{i}+1$ records of the array $m(C)$ contain the IDs and the
$(2\beta+1)$-hop bounded distances in $G_{k-1}$ from $C$ to the closest
$deg_{i}+1$ clusters to $C$ (including $C$ itself).

If the cluster $C$ has at least $deg_{i}$ neighboring clusters, then when the
algorithm terminates, the first $deg_{i}+1$ cells in $m(C)$ contains records
regarding at least $deg_{i}+1$ clusters (including $C$). Therefore, the
assertion of item 1 holds.

If the cluster $C$ has less than $deg_{i}$ neighboring clusters, then the
array $m(C)$ contains the ID and distance
$d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})$ for each neighboring cluster
$C^{\prime}$ of $C$, i.e., each cluster $C^{\prime}\in\Gamma(C)$. In addition,
since the array $m(C)$ was sorted, the $(deg_{i}+1)$st cell of $m(C)$ is
empty, and therefore the assertion of item 2 holds.

∎

#### A.3.2 Variant 2: A BFS Exploration to Depth $\mathbf{d}$

In this section, we prove the correctness of Algorithm 2 for the case where