$d\geq 1$, $x=1$ and $S\subseteq P_{i}$. For convenience, we refer to the
initialization, i.e., 2, 3, 4, 5, 6 and 7 of Algorithm 2, as pulse $0$ of the
algorithm. We say that a cluster $C\in P_{i}$ is detected during a pulse
$p\in[0,d]$ if $p$ is the first index such that the array $m(C)$ is not empty
when pulse $p$ terminates. Intuitively, we show that each pulse of the
exploration is equivalent to one round of a BFS exploration in the virtual
graph $\tilde{G}_{i}$. (See Section 2.1.1 for its definition.)

For a cluster $C\in P_{i}$ and a collection of clusters $S\subseteq P_{i}$,
define $d_{\tilde{G}_{i}}(C,S)={\min\\{d_{\tilde{G}_{i}}(C,C^{\prime})\ |\
C^{\prime}\in S\\}}$.

######  Lemma A.4.

Let $C\in P_{i}$. For any $p\in[0,d]$, the cluster $C$ is detected during
pulse $p$ if and only if $d_{\tilde{G}_{i}}(C,S)=p$.

###### Proof.

The proof is by induction on the index of the pulse $p$. For $p=0$, the claim
is trivial as only (and all) clusters of $S$ are detected during pulse $0$.

We assume that the claim holds for some $p\in[0,d-1]$ and prove it for $p+1$.
Consider some $C\in P_{i}$.

If the cluster $C$ has been detected in pulse $p+1$, then the information that
detected it was written by some cluster $C^{\prime}$ that has been detected in
pulse $p$. The cluster $C^{\prime}$ wrote to its memory at the beginning of
pulse $p+1$ that it has been detected. This information has traversed at most
$2\beta+1$ hops and up to $(1+\epsilon_{k-1})\delta_{i}$ distance before
arriving at $C$. Therefore, we have
$d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})\leq(1+\epsilon_{k-1})\delta_{i}$,
i.e., $d_{\tilde{G}_{i}}(C,C^{\prime})=1$. By the induction hypothesis, since
$C^{\prime}$ has been detected in pulse $p$, we conclude that
$d_{\tilde{G}_{i}}(C^{\prime},S)=p$. It follows that we have
$d_{\tilde{G}_{i}}(C,S)=p+1$.

If the distance $d_{\tilde{G}_{i}}(C,S)$ is equal to $p+1$, then there exists
a cluster $C^{\prime}$ such that $d_{\tilde{G}_{i}}(C^{\prime},S)=p$ and
$d_{\tilde{G}_{i}}(C,C^{\prime})=1$, i.e.,
$d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})\leq(1+\epsilon_{k-1})\delta_{i}$. Let
$u\in C$ and $u^{\prime}\in C^{\prime}$ be a pair of vertices such that
$d^{(2\beta+1)}_{G_{k-1}}(u,u^{\prime})=d^{(2\beta+1)}_{G_{k-1}}(C,C^{\prime})$,
and let $\pi(u^{\prime},u)$ be the shortest $(2\beta+1)$-hops bounded path in
$G_{k-1}$ from $u^{\prime}$ to $u$. By the induction hypothesis, the cluster
$C^{\prime}$ has been detected during pulse $p$. Therefore, during the
distribution part of pulse $p+1$, the vertex $u^{\prime}$ wrote to its memory
that it has been detected. By arguments similar, though simpler than those
used in Lemma A.2 from Appendix A.3.1, we have that during the propagation
part of pulse $p+1$, all vertices of the path $\pi(u^{\prime},u)$ are
detected. Therefore, when the propagation part terminates, the vertex $u$ has
been detected by the exploration. During the aggregation part of pulse $p+1$,
the cluster $C$ learns that it has a detected vertex, and becomes detected. ∎

Recall that by Corollary A.1, Algorithm 2 can be executed in $O(d\beta{\log
n})$ time using $O((|E|+|H_{k-1}|)\cdot x)$ processors. Recall that here we
have $x=1$. Together with Lemma A.4 we derive the following corollary.

######  Corollary A.5.

Given a graph $G_{k-1}=(V,E\cup H_{k-1},\omega_{k-1})$, a set $P_{i}$, a
subset $S\subseteq P_{i}$, distance and hop threshold parameters
$(1+\epsilon_{k-1})\delta_{i},2\beta_{i}+1$ and a depth parameter $d\geq 1$,
Algorithm 2 simulates a BFS exploration to depth $d$ from the set of sources
$S$ in 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}\\}$.
The algorithm requires $O(d\beta{\log n})$ CREW PRAM time, and
$O(|E|+|H_{k-1}|)$ processors.

##  Appendix B Ruling Sets

In this section, we provide the details of the PRAM CREW model implementation
of the algorithm of [AGLP89, SEW13, KMW18] for constructing ruing sets.

We are given a weighted undirected graph $G_{k-1}$, a set $P_{i}$ of clusters,
a set $W_{i}\subseteq P_{i}$ of popular clusters and distance and hop
thresholds $\delta_{i}$ and $h=2\beta+1$, respectively. Recall that each
vertex $v\in V$ has a unique ID in the range $\\{0,1,\dots,n-1\\}$. For every
cluster $C\in P_{i}$ centered around a vertex $r_{C}$, let $I(C)$ be the
binary representation of the ID of $r_{C}$ by exactly ${\log n}$ bits.
Throughout this section, we will refer to the field $I(C)$ as the ID of the
cluster $C$. (The notation $I(C)$ is introduced so that we can delete bits
from the ID of $C$, without actually changing the ID.) Recall that
$\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}\\}$.
The current algorithm constructs a $(3,2{\log n})$-ruling set $Q_{i}$ for the
set $W_{i}$ of popular clusters, with respect to the graph $\tilde{G}_{i}$.
(See Section 2.1.1 for the definition of $W_{i}$.)

We begin with an intuitive description of the algorithm. The algorithm works
recursively, using a divide-and-conquer approach. The input for the algorithm
is a set of clusters $W_{i}$. Given a recursive invocation $\mathcal{A}$ with
input $A=\\{C_{1},C_{2},\dots\\}$, let $h$ be the number of bits in $I(C_{t})$
for every $C_{t}\in A$. Observe that for the initial invocation, we have
$h={\log n}$. If $h=0$, then return $B=A$. Otherwise, the set $A$ is
partitioned into two sets $A_{0},A_{1}$ according to the most significant bit
in the ID of every cluster $C\in A$. For a cluster $C$, let $msb(C)$ be the
most significant bit of $I(C)$. The set $A_{0}$ contains all clusters $C\in A$
with $msb(C)=0$. The set $A_{1}$ contains all clusters $C\in A$ with
$msb(C)=1$. Then, for every cluster $C\in A$, the most significant bit of
$I(C)$ is deleted.

The algorithm recursively computes ruling sets $B_{0}\subseteq A_{0}$,
$B_{1}\subseteq A_{1}$. All clusters in $B_{0}$ join the output set $B$. Then,
a BFS exploration to depth $2$ is executed from all clusters in $B_{0}$ in the
graph $\tilde{G}_{i}$, using Algorithm 2 from Appendix A (with $d=2$ and
$x=1$). Each cluster $C\in B_{1}$ that is detected by the exploration is
removed from $B_{1}$. The clusters that remain in $B_{1}$ also join the output
set $B$, which is then returned.

Let $\mathcal{T}$ be the recursion tree for the input $W_{i}$. For every
recursive invocation $\mathcal{A}$ in the tree $\mathcal{T}$, the _height_ of
$\mathcal{A}$ is defined to be distance from $\mathcal{A}$ to a leaf of
$\mathcal{T}$ that is a descendant of $\mathcal{A}$. Observe that for every
recursive invocation $\mathcal{A}$ with input $A$, the number of bits in
$I(C)$ for all $C\in A$ is also the height of the invocation $\mathcal{A}$ in
the tree $\mathcal{T}$.

Note that there may be many recursive invocations that are executed in
parallel. Therefore, we say that a cluster $C\in B_{1}$ is knocked-out if it
is detected by an exploration originated at some cluster $C^{\prime}$, not
necessarily a cluster of $B_{0}$. Therefore, all these exploration can be
executed in parallel, without additional processors. See Figure 9 for an
illustration. Observe that by allowing clusters to be knocked-out by other
recursive invocations, the output of each invocation does not necessarily rule
its input. However, we will show that throughout the algorithm, every cluster
in $W_{i}$ has some cluster that rules it in the output of some recursive
invocation.

This completes the description of the algorithm. The pseudo-code of the
algorithm is given in Algorithm 4.

Figure 9: The recursion tree $\mathcal{T}$. Clusters from a recursive call
$\mathcal{A}^{j}_{1}$ can be knocked-out by clusters from any recursive call
$\mathcal{A}^{j^{\prime}}_{0}$, possibly for $j\neq j^{\prime}$. The arrows in
the figure illustrate the knock-out messages sent from clusters in
$B^{1}_{0},B^{2}_{0},\dots$, that can knock-out clusters in $B^{2}_{1}$.
Algorithm 4 Ruling Set

1:input: The graph $G_{k-1}$ and the supergraph $\tilde{G}_{i}$, a collection
of clusters $P_{i}$, a subset $A\subseteq P_{i}$ of popular clusters, a field
$I(C)$ for every $C\in A$ and a distance parameter
$(1+\epsilon_{k-1})\delta_{i}$.

2:output: A set $B\subseteq A$.

3:let $h$ be the number of bits in $I(C)$ for every $C\in A$

4:if $h=0$ then return $A$

5:else

6: $A_{0}=\\{C\in A\ |\textit{ the most significant bit in }I(C)\textit{ is
}0\ \\}$

7: $A_{1}=\\{C\in A\ |\textit{ the most significant bit in }I(C)\textit{ is
}1\ \\}$

8: for every $C\in A$, delete the most significant bit from $I(C)$

9: compute recursively sets $B_{0},B_{1}$ for the sets $A_{0},A_{1}$

10: execute a multiple sources BFS exploration in $\tilde{G}_{i}$ to depth $2$
from all clusters in $B_{0}$

11: remove from $B_{1}$ all clusters detected by an exploration

12: $B=B_{0}\cup B_{1}$

The following lemmas summarize the properties of Algorithm 4. Recall that
$\mathcal{T}$ is the recursion tree for the input $W_{i}$. We begin by
analyzing the running time and number of processors used by the algorithm.

######  Lemma B.1.

Given the graph $G_{k-1}=(V,E\cup H_{k-1},\omega_{k-1})$, a set of clusters
$P_{i}$, a subset $W_{i}\subset P_{i}$ and distance and hopbound parameters
$(1+\epsilon_{k-1})\delta_{i},2\beta+1$, respectively, Algorithm 4 uses
$O(|E|+|H_{k-1}|)$ processors and terminates in $O(\beta{\log^{2}n})$ time.

###### Proof.

There are ${\log n}+1$ levels in the recursion tree $\mathcal{T}$. In every
level of the recursion tree (other than the last level), the algorithm
simulates a BFS exploration to depth $2$ in the graph $\tilde{G}_{i}$. By
Corollary A.5, this requires $O(\beta\cdot{\log n})$ time and
$O(|E|+|H_{k-1}|)$ processors.

In the last level of the recursion, there are $n$ recursive invocations. Each
recursive invocation returns its input as its output. This can be done in
$O(1)$ time using $O(n)$ processors.

Therefore, the running time of Algorithm 4 is $O(\beta{\log^{2}n})$, and it
uses $O(|E|+|H_{k-1}|)$ processors. ∎

The following two lemmas prove that $Q_{i}$ is indeed a $(3,2{\log n})$-ruling
set for $W_{i}$ with respect to the graph $\tilde{G}_{i}$. (See Section 2.1.1
for the definition of $Q_{i}$ and $W_{i}$.)

######  Lemma B.2.

For every recursive invocation $\mathcal{A}$, its output $B$ is $3$-separated
w.r.t. the graph $\tilde{G}_{i}$.

###### Proof.

The proof is by induction on $h$, i.e., the height of the recursive invocation
in the tree $\mathcal{T}$. For the base case, let $\mathcal{A}$ be a recursive
invocation with height $h=0$ in the tree $\mathcal{T}$. Observe that the path
from the root of $\mathcal{T}$ to the leaf of $\mathcal{T}$ corresponds to the
bits that were removed from $I(C)$ for every $C\in A$. Since $h=0$, we have
that $I(C)$ contains now zero bits. Therefore, $A$ is a singleton, and the
output $B=A$ is $3$-separated w.r.t. the graph $\tilde{G}_{i}$.

Assume that the claim holds for some $h\in[0,{\log n}-1]$ and prove it for
$h+1$.

Let $\mathcal{A}$ be a recursive invocation with input $A$ and height $h+1$.
The invocation $\mathcal{A}$ deletes a single bit from $I(C)$ for every $C\in
A$, and initiates two recursive invocations $\mathcal{A}_{0}$ and
$\mathcal{A}_{1}$, each with height $h$. By the induction hypothesis, each set
$B_{0},B_{1}$ returned by an invocations $\mathcal{A}_{0}$, $\mathcal{A}_{1}$
is $3$-separated w.r.t. the graph $\tilde{G}_{i}$. Then, all clusters in
$B_{0}$ initiate a BFS exploration to depth $2$ in $\tilde{G}_{i}$. Each
cluster in $B_{1}$ that is detected by the exploration is removed from
$B_{1}$. All clusters that remain in $B_{1}$ and all clusters in $B_{0}$ join
the output $B$. Therefore, the output set $B$ is $3$-separated w.r.t. the
graph $\tilde{G}_{i}$. ∎

For every index $h\in[0,{\log n}]$, let $\mathcal{B}^{h}$ be the union of
outputs of all recursive invocations with height $h$ in $\mathcal{T}$.

######  Lemma B.3.

For every index $h\in[0,\ell]$, for every cluster $C\in W_{i}$ there exists a
cluster $C^{\prime}\in\mathcal{B}^{h}$ such that
$d_{\tilde{G}_{i}}(C,C^{\prime})\leq 2h$.

###### Proof.

We prove the claim by induction on the index $h$.

For $h=0$, for every invocation $\mathcal{A}$ with height $h=0$ the output $B$
is equal to the input $A$ of $\mathcal{A}$. Note that for every cluster $C\in
W_{i}$ there exists a recursive invocation $\mathcal{A}$ with input $A$ and
height $h=0$ such that $C\in A$. Thus the claim holds.

Assume that the claim holds for some $h\in[0,{\log n}-1]$ and prove it for
$h+1$.

Let $C\in W_{i}$. By the induction hypothesis, there exists a cluster
$C^{\prime}\in\mathcal{B}^{h}$, with $d_{\tilde{G}_{i}}(C,C^{\prime})\leq 2h$.

If $C^{\prime}\in\mathcal{B}^{h+1}$, the claim holds. Otherwise, $C^{\prime}$
has been detected by the exploration originated in a cluster
$C^{\prime\prime}\in\mathcal{B}^{h+1}$. Since $C^{\prime\prime}$ knocked-out
$C^{\prime}$, we conclude that
$d_{\tilde{G}_{i}}(C^{\prime},C^{\prime\prime})\leq 2$. Therefore, we have
$d_{\tilde{G}_{i}}(C,C^{\prime\prime})\leq
d_{\tilde{G}_{i}}(C,C^{\prime})+d_{\tilde{G}_{i}}(C^{\prime},C^{\prime\prime})\leq
2h+2$.

It follows that in both cases, there exists a cluster in $\mathcal{B}^{h+1}$
with distance at most $2(h+1)$ from $C$ w.r.t. the graph $\tilde{G}_{i}$. ∎

Observe that Lemma B.3 implies that the output $Q_{i}$ for the initial input
$W_{i}$ satisfies that for every cluster $C\in W_{i}$, there exists a cluster
$C^{\prime}\in Q_{i}$ with $d_{\tilde{G}_{i}}(C,C^{\prime})\leq 2{\log n}$. As
a corollary to Lemmas B.1, B.2 and B.3 we have

######  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}\\}$.

##  Appendix C Eliminating the Dependence on the Aspect Ratio

In this section we show that the reduction devised by Klein and Sairam [KS97]
can be used by our algorithm from Section 2 to eliminate the dependence of the
hopbound $\beta$ and of the running time on the aspect ratio $\Lambda$. This
reduction was also previously used by Elkin and Neiman [EN19] in their
construction of hopsets, for the same purpose. The result of applying the
reduction to our algorithm is summarized in Theorems C.2 and C.3. In this
section we describe the algorithm for ordinary (not path-reporting) hopsets.
In Appendix D we extend this result also to the path-reporting case.

###  C.1 Overview

Fix a parameter $0<\epsilon\leq 1/2$. Recall that
$k_{0}=\lfloor{\log\beta}\rfloor$ and that
$\lambda=\lceil{\log\Lambda}\rceil-1$. For every index $k\in[k_{0},\lambda]$
we build a graph $\mathcal{G}^{k}$ that contains only edges with weight in the
range $((\epsilon/n)\cdot 2^{k},(1+\epsilon)2^{k+1}]$. This is done by
deleting heavy edges, and grouping vertices that have short edges between them
into supervertices, which we call nodes. As a result, for every
$k\in[k_{0},\lambda]$, the graph $\mathcal{G}^{k}$ has aspect ratio
$O(n/\epsilon)$.

For every index $k\in[k_{0},\lambda]$, a $(1+\epsilon,\beta)$-hopset for the
scale $(2^{k},2^{k+1}]$ is computed for the graph $\mathcal{G}^{k}$, using our
algorithm from Section 2. This is done in parallel for all
$k\in[k_{0},\lambda]$. In addition, every node $X$ formed by the algorithm has
a designated center vertex $x^{*}\in X$. A spanning star centered around
$x^{*}$ is added to a set of edges $S$, i.e., for every node $X$, the set $S$
contains the set of edges $\\{(x^{*},x)\ |\ x\in X\setminus\\{x^{*}\\}\\}$.
The weight of these star edges will be specified in the sequel.

The ultimate hopset $H$ is constructed as follows. For every
$k\in[k_{0},\lambda]$, let $\mathcal{H}^{k}$ be the single-scale
$(1+\epsilon,\beta)$-hopset for the scale $(2^{k},2^{k+1}]$ for the graph
$\mathcal{G}^{k}$. For every $k\in[k_{0},\lambda]$ and for every edge $(X,Y)$
with weight $d$ in the hopset $\mathcal{H}^{k}$, an edge $(x^{*},y^{*})$
between the respective centers of the nodes $X,Y$ is added to $H$, also with
weight $d$. To ensure that the number of hops within nodes is also small, the
set of (weighted) star edges $S$ is also added to $H$. This completes the
overview of the reduction.

###  C.2 Constructing $\mathcal{G}^{k}$

Klein and Sairam [KS92] have shown that the graphs
$\mathcal{G}^{k_{0}},\mathcal{G}^{k_{0}+1},\dots$ can be computed in the EREW
PRAM model in $O({\log^{3}n})$ time, using $O(|E|)$ processors. Their
algorithm is based on combining parallel prefix computation with the connected
components algorithm of Shiloach and Vishkin [SV82]. As a byproduct of the
connected components algorithm, for every node $U$ in a graph
$\mathcal{G}^{k}$, $k\in[k_{0},\lambda]$, a spanning tree $T_{U}$ that
contains only edges of weight at most $(\epsilon/n)\cdot 2^{k}$ is computed.

The algorithm of Klein and Sairam does not assign centers to nodes. For our
algorithm, we require each node $U$ to have a designated center $u^{*}\in U$.
In Section C.3 we explain how the centers are selected in a way that ensures
that the number of star edges is $O({n\log n})$.

We now describe the construction of $\mathcal{G}^{k}$, for every scale index
$k\in[k_{0},\lambda]$. The nodes of $\mathcal{G}^{k}$ are formed in the
following way. Let $\mathcal{V}^{k}$ be the set of connected components in the
graph $G$, after all edges of weight at least $(\epsilon/n)\cdot 2^{k}$ are
removed from it. (In other words, here we _contract_ all edges of weight at
most $(\epsilon/n)\cdot 2^{k}$. ) The set $\mathcal{V}^{k}$ is the set of
nodes of the graph $\mathcal{G}^{k}$. For every pair of distinct nodes
$X,Y\in\mathcal{V}^{k}$ such that there exists an edge $(x,y)\in E\cap(X\times
Y)$, let $x\in X$ and $y\in Y$ be a pair of vertices such that $\omega(x,y)$
is minimal. If $\omega(x,y)\leq 2^{k+1}$, an edge $(X,Y)$ is added to
$\mathcal{G}^{k}$ with weight

$\mathcal{W}(X,Y)=\omega(x,y)+(|X|+|Y|)\cdot(\epsilon/n)\cdot 2^{k}.$ (21)

Observe that the minimal edge weight in $\mathcal{G}^{k}$ is at least
$(\epsilon/n)\cdot 2^{k}+2(\epsilon/n)\cdot 2^{k}\geq(\epsilon/n)2^{k+1}$, and
the maximal edge weight is at most $2^{k+1}+n(\epsilon/n)\cdot
2^{k}\leq(1+\frac{\epsilon}{2})2^{k+1}$. Therefore, the aspect ratio of the
graph $\mathcal{G}^{k}$ is at most

$\frac{(1+\frac{\epsilon}{2})2^{k+1}}{(\epsilon/n)2^{k+1}}=O(n/\epsilon).$
(22)

This completes the construction of $\mathcal{G}^{k}$, for all
$k\in[k_{0},\lambda]$. We note that this process is equivalent to deleting
edges of weight greater than $2^{k+1}$, and sequentially contracting edges of
weight at most $(\epsilon/n)\cdot 2^{k}$, i.e., identifying their endpoints,
while retaining the lightest among parallel edges.

###  C.3 Selecting Node Centers

In this section, we select node centers in a way that guarantees that the
number of star edges satisfies $|S|=O({n{\log n}})$.

For every node $X\in\mathcal{V}^{k_{0}}$, an arbitrary vertex $x^{*}\in X$ is
selected to be the center of the node $X$. For every vertex $z\in
X\setminus\\{x^{*}\\}$, the edge $(x^{*},z)$ is added to the set $S$. The
weight of the edge will be specified in the sequel.

Consider a node $U\in\mathcal{V}^{k}$, for some $k\in[k_{0}+1,\lambda]$. Let
$X_{1},X_{2},\dots,X_{t}$ be the nodes in $\mathcal{V}^{k-1}$ such that
$|X_{1}|\geq|X_{2}|\geq|\dots|\geq|X_{t}|$ and also
$U=\bigcup_{j\in[1,t]}X_{j}$. Note that the set of nodes on all different
levels $k\in[k_{0},\lambda]$ forms a laminar family. The center $x^{*}_{1}$ of
the node $X_{1}$ is set to be the center of the node $U$. For every vertex
$z\in U\setminus X_{1}$, the edge $(x_{1}^{*},z)$ is added to the set $S$.

We now specify the weights of star edges. Consider an index
$k\in[k_{0},\lambda]$, and let $U\in\mathcal{V}^{k}$, such that $x^{*}$ is the
center of $U$. Let $z\in U\setminus\\{x^{*}\\}$. Observe that since the
vertices $x^{*}$ and $z$ both belong to the node $U$, we have that
$d_{G}(x^{*},z)\leq|U|\cdot(\epsilon/n)\cdot 2^{k}$. In their implementation
of the reduction, Elkin and Neiman [EN19] set the weight of the edge
$(x^{*},z)$ to be $\mathcal{W}(x^{*},z)=|U|\cdot(\epsilon/n)\cdot 2^{k}$. This
assignment of edge weight is enough for the basic variant of our algorithm. In
Appendix D, we show that the current reduction also enables us to obtain path-
reporting hopsets with no dependence on the aspect ratio of the graph $G$. To
support the path-reporting property, the weight of the star edges has to be
assigned in a more careful way. Recall that a byproduct of computing a node
$U$ is a spanning tree $T_{U}$. For every vertex $z\in U\setminus\\{x^{*}\\}$,
we set the weight of the edge $(z,x^{*})$ to be the weight of the path in
$T_{U}$ from $z$ to $x^{*}$. To compute the weight of this path, we use
standard pointer-jumping techniques (see, e.g., [SV82]). We note that for
every $z\in U\setminus\\{x^{*}\\}$, we have
$d_{T_{U}}(z,x^{*})<|U|\cdot(\epsilon/n)\cdot 2^{k}$, and therefore the
stretch analysis of the hopset provided in [EN19] also holds under the current
assignment of weights.

Next, we show that this consistent way of selecting node centers ensures that
$|S|\leq n{\log n}$. For every node $U$ formed by the algorithm, let
$\widehat{S}(U)$ be the set of edges with both endpoints in $U$ in the set
$S$, i.e., $\widehat{S}(U)=\\{(x,y)\in S\ |\ x,y\in U\\}$. The following lemma
provides an upper bound on the number edges in $\widehat{S}(U)$ for every node
$U$. It is later used to bound the size of the set $S$.

######  Lemma C.1.

For every scale $k\in[k_{0},\lambda]$, for every node $U\in\mathcal{V}^{k}$,
the set $\widehat{S}(U)$ contains at most $|U|\cdot{\log|U|}$ edges.

###### Proof.

The proof is by induction on the index $k$. For $k=k_{0}$ and for every node
$U\in\mathcal{V}^{k_{0}}$, the set $\widehat{S}(U)$ contains exactly $|U|-1$
edges.

We assume that the claim holds for some $k\in[k_{0},{\lambda}-1]$, and prove
that it also holds for $k+1$. Let $U$ be a node in $\mathcal{V}^{k+1}$, and
let $X_{1},X_{2},\dots,X_{t}$ be the nodes in $\mathcal{V}^{k}$ such that
$U=\bigcup_{j\in[1,t]}X_{j}$, and $|X_{1}|\geq|X_{2}|\geq,\dots,\geq|X_{t}|$.
Denote $s=|U|$, and for every $j\in[1,t]$, denote $s_{j}=|X_{j}|$.

The set $\widehat{S}(U)$ contains all edges of the sets
$\\{\widehat{S}(X_{j})\ |\ j\in[1,t]\\}$, and also the edges added from the
center of the node $X_{1}$ to all vertices of $U\setminus X_{1}$. By the
induction hypothesis, for every index $j\in[1,t]$, we have
$|\widehat{S}(X_{j})|\leq s_{j}{\log s_{j}}$. It follows that

$\begin{array}[]{lclclclclclclclc}|\widehat{S}(U)|&=&|U|-|X_{1}|+\sum_{j=1}^{t}\widehat{S}(X_{j})\\\
&=&\sum_{j=2}^{t}s_{j}+\sum_{j=1}^{t}s_{j}{\log s_{j}}\\\ &\leq&s_{1}{\log
s_{1}}+\sum_{j=2}^{t}s_{j}(1+{\log s_{j}})\\\ &\leq&s_{1}{\log
s_{1}}+\sum_{j=2}^{t}s_{j}{\log(2s_{2})}&&(note:s\geq s_{1}+s_{2}\geq
2s_{2})\\\ &\leq&s_{1}{\log s}+(s-s_{1}){\log s}&\leq&s{\log s}.\end{array}$
(23)

∎

Observe that for every $k\in[k_{0},\lambda]$, every node $U\in\mathcal{V}^{k}$
is fully contained in a node of the set $\mathcal{V}^{\lambda}$. Therefore, by
convexity of the function $f(x)=x{\log x}$, Lemma C.1 implies that the number
of edges in $S$ satisfies

$|S|=\sum\limits_{U\in\mathcal{V}^{\lambda}}|\widehat{S}(U)|\
\leq\sum\limits_{U\in\mathcal{V}^{\lambda}}|U|{\log|U|}\ \leq\ n{\log n}.$
(24)

Note also that it follows that the total number of pairs $(u,U)$, such that
$U$ is a node computed by the algorithm and $u\in U$ is $O(n{\log n})$. As a
part of the computation of the set $S$ of star edges, the algorithm can also
compute an array $B$ of size $O(n{\log n})$ that records all these pairs.

###  C.4 Sketch of Analysis

In this section we provide a short sketch of the analysis of the properties of
the resulting hopset $H$. For every index $k\in[k_{0},\lambda]$, the hopset
$\mathcal{H}^{k}$ is used to approximate distances of pairs of vertices
$u,v\in V$ with $d_{G}(u,v)\in(2^{k},2^{k+1}]$. Consider an index
$k\in[k_{0},\lambda]$. If there are no edges with weight in the range
$(2^{k}/n,2^{k+1}]$, then there is no pair of vertices with distance in the
range $(2^{k},2^{k+1}]$. In this case, the hopset $\mathcal{H}^{k}$ is
redundant. Define a scale $k$ to be relevant if there exists an edge $(u,v)\in
E$ with weight $\omega(u,v)\in(2^{k}/n,2^{k+1}]$. Let $K$ be the set of all
relevant scale indexes from the range $[k_{0},\lambda]$.

Observe that every edge $(u,v)\in E$ can induce a logarithmic number of
relevant scales, and so

$|K|=O(|E|\cdot{\log n}).$ (25)

Our algorithm constructs a $(1+\epsilon,\beta)$-hopset $\mathcal{H}^{k}$ for
the scale $(2^{k},2^{k+1}]$ only for the graphs $\mathcal{G}^{k}$ with $k\in
K$. Recall that for every edge $(X,Y)$ with weight $d$ in some hopset
$\mathcal{H}^{k}$, the algorithm adds to our ultimate hopset $H$ the edge
$(x^{*},y^{*})$ between the respective centers of $X,Y$, also with weight $d$.
In addition, the set $H$ also contains the set $S$ of star edges.

Elkin and Neiman [EN19] have provided a detailed analysis of the reduction in
the centralized model (see Section $4$ in [EN19]). In particular, they have
shown that the hopset $H$ is a $(1+6\epsilon,6\beta+5)$-hopset for $G$. See
Lemma 4.3. in [EN19].

#### C.4.1 Size

For every $k\in K$, let $m_{k}$ denote the number of edges in
$\mathcal{G}^{k}$, and let $n_{k}$ denote the number of nodes in
$\mathcal{V}^{k}$ that are not isolated in $\mathcal{G}^{k}$. By arguments
similar to those used in [KS97, Coh97, EN19], one can show that the number of
non-isolated nodes in all graphs $\\{\mathcal{G}^{k}\ |\ k\in K\\}$ is at most

$\sum_{k\in K}n_{k}\leq\sum_{k\in K}|\mathcal{V}^{k}|=O(n{\log n}).$ (26)

Note that $\epsilon^{-1}\leq n$ (otherwise, $\beta>n$ and the result becomes
meaningless). Since every edge $e\in E$ belongs to at most
$O({\log(n/\epsilon)})=O({\log n})$ relevant scales, the number of edges in
all graphs $\\{\mathcal{G}^{k}\ |\ k\in K\\}$ is at most

$\sum_{k\in K}m_{k}\leq O(|E|\cdot{\log n}).$ (27)

Recall that for every $k\in K$, the hopset $\mathcal{H}^{k}$ is a _single-
scale_ hopset. Therefore, by eq. 9 we have $|\mathcal{H}^{k}|\leq
n_{k}^{1+1/\kappa}$. By eqs. 26 and 24, the size of the hopset $H$ satisfies

$|H|=|S|+\sum_{k\in K}|\mathcal{H}^{k}|\leq n{\log n}+\sum_{k\in
K}n_{k}^{1+1/\kappa}\leq n{\log n}+n^{1/\kappa}\sum_{k\in
K}n_{k}=O\left(n^{1+\frac{1}{\kappa}}\cdot{\log n}\right).$ (28)

#### C.4.2 Computational Complexity

Computing the graphs $\\{\mathcal{G}^{k}\ |\ k\in K\\}$ can be done using
$O(|E|)$ processors in $O({\log^{3}n})$ time (see, e.g., [KS92]).

We next explain how to efficiently compute the edge sets of graphs
$\mathcal{G}^{k}$, for $k\in K$. Every edge $(x,y)\in E$ participates in
$O({\log(n/\epsilon)})=O({\log n})$ scales, and on each scale it connects a
pair of nodes $(X,Y)$, $x\in X$, $y\in Y$. We allocate an array $A$ of size
$O(|E|\cdot{\log n})$, and also, designate $O({\log n})$ processors for every
$e\in E$, and $O({\log n})$ slots in the array $A$ associated with $e$. These
processors write in parallel into $A$ tuples
$\langle(X,Y),k,\omega(e),e\rangle$, for all possible
$(X,Y)\in\mathcal{G}^{k}$, for some $k$, such that $x\in X$, $y\in Y$, and $e$
is relevant for scale $k$ (i.e., its weight is within interval
$((\epsilon/n)\cdot 2^{k},2^{k+1}]$).

This array is then sorted according to the superedges $(X,Y)$, and within each
segment that has to do with a specific superedge $(X,Y)$, by the scale index
$k$, and within each such segment, by the weight of $e$. For each superedge
$(X,Y)$ and scale $k$, the lightest edge $e$ is selected, and its weight
$\omega(e)$ determines the weight $\mathcal{W}(X,Y)$ of the superedge $(X,Y)$
in $\mathcal{G}^{k}$. This completes the description of this computation. It
can be carried over in $O({\log n})$ time using $\tilde{O}(n+|E|)$ processors.

Once all the graphs $\\{\mathcal{G}^{k}\ |\ k\in K\\}$, node centers are
selected. We now provide an implementation of the procedure that selects node
centers. Observe that the nodes in $\\{\mathcal{V}^{k}\ |\ k\in K\\}$ form a
laminar family, and so there are at most $2n-1$ distinct nodes computed
throughout the algorithm. A nodes graph $\bar{\mathcal{G}}$ is computed. The
vertices of this graph are the (up to $2n-1$) nodes formed by the algorithm.
Let $\widehat{k}_{0}$ be the smallest index in $K$. For every node
$U\in\bigcup_{k\in K\setminus\\{\widehat{k}_{0}\\}}\mathcal{V}^{k}$, let $X$
be the largest lower-scale node $X\subset U$, if exists. Recall that the
center of $U$ is set to be the center of $X$. The node $U$ defines $X$ as its
parent, i.e., it writes to its memory $p(U)=X$. The node $U$ also adds the
edge $(U,X)$ to the graph $\bar{\mathcal{G}}$. Every node
$X\in\mathcal{V}^{\widehat{k}_{0}}$ writes $p(X)=X$, and selects the smallest
ID vertex $x^{*}\in X$ to be its center. See Figure 10 for an illustration.

Observe that every node constructed by the algorithm has (at most) one parent.
Moreover, every node can be a parent of at most one node. Therefore, the
maximal degree in $\bar{\mathcal{G}}$ is at most $2$. In addition, the number
of vertices in a node $U$ is always greater than the number of vertices of its
parent $X$, and so $\bar{\mathcal{G}}$ does not contain cycles. Hence,
$\bar{\mathcal{G}}$ is a forest of paths, and the maximal length of a path in
$\bar{\mathcal{G}}$ is $2n-1$.

Figure 10: The nodes forest $\bar{\mathcal{G}}$. Each node constructed by the
algorithm is a vertex in this graph. Edges are drawn from each node $U$ to the
largest lower-scale node $X\subset U$, if such a node exists.

A standard pointer-jumping algorithm (see, e.g., Section 4.2 for an example)
is used to compute the centers of all nodes. For ${\log{2n}}$ iterations,
every node $U$ in $\bar{\mathcal{G}}$ writes $p(U)=p(p(U))$. When the
algorithm terminates, the pointer $p(U)$ contains the identity of the root of
its tree in the forest $\bar{\mathcal{G}}$, and the node $U$ selects the
center of $p(U)$ to be its center.

The graph $\bar{\mathcal{G}}$ can be constructed using $O(n)$ processors in
$O({\log n})$ time. The pointer-jumping procedure requires additional $O({\log
n})$ time, using $O(n)$ processors. It follows that overall, centers can be
selected in $O({\log n})$ time, using $O(n)$ processors. This completes the
description of the procedure that selects node centers.

Finally, we discuss the resources used to compute the hopsets
$\mathcal{H}^{k}$ for all $k\in K$, and the final hopset $H$. We note that in
the centralized model, one can construct a single-scale hopset efficiently for
a particulate scale $(2^{k},2^{k+1}]$. On the other hand, in parallel models,
in order to construct a hopset that takes care of distances $(2^{k},2^{k+1}]$
for $\mathcal{G}^{k}$, one needs to first construct hopsets for all lower
scales for $\mathcal{G}^{k}$. (Note, however, that one does not need to
compute hopsets for
$\mathcal{G}^{k_{0}},\mathcal{G}^{k_{0}+1},\dots\mathcal{G}^{k-1}$, before
computing the hopset for $\mathcal{G}^{k}$.) These lower scales hopsets are
only used to compute the hopset for the scale $(2^{k},2^{k+1}]$, and do not
belong to the ultimate hopset. Since the aspect ratio of every graph
$\mathcal{G}^{k}$ is $O(n/\epsilon)$, by Lemma 3.1, for every $k\in K$, the
hopset $\mathcal{H}^{k}$ for the graph $\mathcal{G}^{k}$ can be constructed in
$O(({\log\kappa\rho}+1/\rho)\beta{\log^{3}n})$ time using
$O((m_{k}+n^{1+\frac{1}{\kappa}}_{k})n^{\rho})$ processors. By eqs. 26 and 27
we have that the total number of processors used to compute the hopsets is at
most

$\sum_{k\in
K}O((m_{k}+n^{1+\frac{1}{\kappa}}_{k})n^{\rho})=O(n^{\rho}\cdot(|E|\cdot{\log
n}+n^{1+\frac{1}{\kappa}}{\log n})).$

Computing $H$ requires adding all star edges $S$ to an empty set $H$, and also
for every edge $(X,Y)$ that belongs to a hopset $\mathcal{H}^{k}$ for some
$k\in K$, the edge between the respective centers of $X,Y$ is also added to
$H$. This can be performed in $O(1)$ time using
$O\left(n^{1+\frac{1}{\kappa}}\cdot{\log n}\right)$ processors. This completes
the analysis of the computational complexity of the algorithm. Observe that
the running time and work used by the entire algorithm are dominated by the
respective time and work requires to compute the hopsets $\\{\mathcal{H}^{k}\
|\ k\in K\\}$.

The following theorem summarizes the properties of the entire algorithm.

######  Theorem C.2.

Given a weighted undirected graph $G=(V,E,\omega)$ on $n$ vertices, and
parameters $0<\epsilon<1/2$, $\kappa=2,3,\dots$, and $0<\rho<1/2$, our
algorithm deterministically computes a $(1+\epsilon,\beta)$-hopset $H$ of size
at most $O\left(n^{1+\frac{1}{\kappa}}\cdot{\log n}\right)$ 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}}\right)\right)$
processors, 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}.$
(29)

Recall that the hopset $H$ can be used to compute approximate distances in the
graph $G$. Given a set of sources $\mathcal{S}\subseteq V$, one can execute
$|\mathcal{S}|$ parallel Bellman-Ford explorations in the graph $G\cup H$,
each limited to $\beta$ hops, and solve the $(1+\epsilon)$-approximate-
multiple-source-shortest distance (aMSSD) problem. (When $|\mathcal{S}|=1$,
this approach solves the $(1+\epsilon)$-approximate-single-source-shortest
distance (aSSSD) problem.) Executing $|\mathcal{S}|$ Bellman-Ford exploration
limited to $\beta$ hops can be performed in $O(\beta{\log n})$ time, using
$O(|\mathcal{S}|)$ processors to simulate every vertex and every edge of
$E\cup H$.

######  Theorem C.3.

Given a weighted undirected graph $G=(V,E,\omega)$ on $n$ vertices, parameters
$0<\epsilon<1/2$, $\kappa=2,3,\dots$, and $0<\rho<1/2$, and a set of sources
$\mathcal{S}\subseteq V$, our deterministic algorithm computes
$(1+\epsilon)$-approximate distances for all pairs of vertices in
$\mathcal{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}+|\mathcal{S}|)\cdot\left(|E|+n^{1+\frac{1}{\kappa}}\cdot{\log
n}\right)\right)$ processors, 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}.$

##  Appendix D Path-Reporting Hopsets Without Dependency on the Aspect Ratio

In this section, we show how to eliminate the dependency on the aspect ratio
in the context of path-reporting hopsets. In particular, 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$.
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 know555In other words, the processor
associated with the vertex $v$ will know this information. its parent with
respect to $T$ and also the distance $d_{T}(s,v)$ between $v$ and the source
$s$.

To achieve this, we combine the Klein-Sairam reduction provided in Appendix C,
with the construction of the path-reporting hopset of Section 4. Namely, we
execute the algorithm from Appendix C, but use the path-reporting hopset
construction from Section 4 instead of the construction provided in Section 2.
Once the path-reporting $(1+\epsilon,\beta)$-hopset $H$ is computed, a
Bellman-Ford exploration is executed from the source $s$ to depth $\beta$ in
the graph $G\cup H$. As a result, a tree $\mathcal{T}$ is formed. For every
vertex $v\in V$, let $p(v),d(v)$ be the parent and distance of $v$ from the
source $s$, respectively. Note that the tree $\mathcal{T}$ may contain edges
that belong to $H$, and not to the original graph $G$. A procedure that
replaces edges of $H$ with paths from $G$ is executed, to obtain a
$(1+\epsilon)$-SPT $T=(V,E_{T})$, with $E_{T}\subseteq E$. This procedure is
more complicated than the procedure used to retrieve paths in Section 4,
because we must replace edges between centers of nodes computed by the
reduction (including star edges) with edges of the original graph.

###  D.1 Constructing the Hopset $H$

As in Appendix C, define $k$ to be relevant if there exists an edge $(u,v)\in
E$ with weight in the range $(2^{k}/n,2^{k+1}]$. Let $K$ be the set of all
relevant scale indexes from the range $[k_{0},\lambda]$. We begin by computing
the graphs $\\{\mathcal{G}^{k}\ |\ k\in K\\}$, as in Appendix C. For every
$k\in K$, we execute the algorithm provided in Section 4 to construct a path-
reporting $(1+\epsilon,\beta)$-hopset $\mathcal{H}^{k}$ for the graph
$\mathcal{G}^{k}$. In Appendix C, the hopset was used only to estimate
distances. Therefore, for every $k\in K$, it sufficed to only use the hopset
constructed for the scale $(2^{k},2^{k+1}]$ in $\mathcal{G}^{k}$. To support
path reporting, the hopset $\mathcal{H}^{k}$ must also be a hopset for all
scales lower than $k$.

Recall that for every edge $(X,Y)$ with weight $d$ in the hopset
$\mathcal{H}^{k}$, an edge $(x^{*},y^{*})$ between the respective centers of
the nodes $X,Y$ is added to $H$, also with weight $d$. Recall also that every
edge $(X,Y)$ in the path-reporting hopset $\mathcal{H}^{k}$ is associated with
a memory path, which in this case is a path of nodes. Instead of maintaining
the memory path as a list of nodes, we maintain the list of corresponding node
centers.

Recall that the nodes of each graph $\mathcal{G}^{k}$ are computed by removing
all edges of weight at least $(\epsilon/n)\cdot 2^{k}$ from $G$, and finding
the connected components in the new graph. The connected components are
computed using the algorithm of Shiloach and Vishkin [SV82]. We note that a
byproduct of this computation, is a spanning tree $T_{U}$ for every node $U$
computed by the algorithm. We use the procedure provided in Appendix C.3 to
select a designated center for each node and compute the set of star edges
$S$. The set $S$ is also added to the hopset $H$. For every node $U$ centered
around a vertex $u^{*}$, we orient its tree $T_{U}$ such that every vertex
$u\in U\setminus\\{u^{*}\\}$ knows its parent $p_{u^{*}}(u)$ in $T_{U}$. We
also use a pointer-jumping algorithm to compute for each vertex $u\in
U\setminus\\{u^{*}\\}$ its distance from the center $u^{*}$ in the tree
$T_{U}$.

Observe that the set $H$ contains two types of edges. The first type is edges
between pairs of node centers, such that there is an edge between their
corresponding nodes in some hopset $\mathcal{H}^{k}$, for some $k\in K$. For
brevity, we will henceforth refer to edges of the first type as _hop-edges_.
The second type is star edges.

We now analyze the stretch and size of the hopset $H$, as well as the
complexity of the algorithm. In Appendix D.2 we show how to employ $H$ for the
construction of a $(1+\epsilon)$-SPT for the original graph $G$.

#### D.1.1 Stretch

By a similar argument to the one provided in Appendix C.4, we have that $H$ is
a $(1+\epsilon,\beta)$-hopset for the graph $G$, with $\beta$ given by eq. 29.

#### D.1.2 Size

As in Appendix C, denote by $n_{k}$ the number of not isolated nodes in
$\mathcal{G}^{k}$, for all $k\in K$. Recall that by eq. 26 we have $\sum_{k\in
K}n_{k}=O(n{\log n})$.

For every $k\in K$, $\mathcal{H}^{k}$ is a hopset for $\mathcal{G}^{k}$. By
Theorem 4.5 and since the aspect ratio of $\mathcal{G}^{k}$ is
$O(n/\epsilon)=O(n^{2})$, we have that

$|\mathcal{H}^{k}|\leq O(n_{k}^{1+1/\kappa}{\log n}).$

By arguments similar to those used in eq. 28, we have that

$|H|=|S|+\sum_{k\in K}|\mathcal{H}^{k}|=O(n^{1+\frac{1}{\kappa}}{\log^{2}n}).$
(30)

#### D.1.3 Computational Complexity

Computing the graphs $\\{\mathcal{G}^{k}\ |\ k\in K\\}$ can be done using
$O(|E|)$ processors in $O({\log^{3}n})$ time (see, e.g., [KS92]). Selecting
nodes centers can be done in $O({\log n})$ time, using $\tilde{O}(n)$
processors, using the procedure described in Appendix C (see the discussion in
Appendix C.4 for details).

By Theorem 4.5, for every index $k\in K$, the path-reporting hopset
$\mathcal{H}^{k}$ can be constructed in
$O(({\log\kappa\rho}+1/\rho)\beta{\log^{3}n})$ time in the PRAM CREW model
using $\beta\cdot n^{\rho}\cdot O({\log
n})^{\lfloor{\log\kappa\rho}\rfloor+\lceil\frac{\kappa+1}{\kappa\rho}\rceil-1}$
processors to simulate every vertex and every edge of the graph
$\mathcal{G}^{k}$, and every edge of the hopset $\mathcal{H}^{k}$. By eq. 26,
the number of nodes in all graphs $\\{\mathcal{G}^{k}\ |\ k\in K\\}$ is at
most $\sum_{k\in K}|\mathcal{V}^{k}|\leq O(n{\log n})$. By eq. 27, the number
of edges in all these graphs is at most $O(|E|\cdot{\log n})$. By eq. 30, the
number of edges in all hopsets $\\{\mathcal{H}^{k}\ |\ k\in K\\}$ is
$O(n^{1+\frac{1}{\kappa}}{\log^{2}n})$. Hence, all the hopsets
$\\{\mathcal{H}^{k}\ |\ k\in K\\}$ can be constructed in parallel in
$O(({\log\kappa\rho}+1/\rho)\beta{\log^{3}n})$ time, using $(n\log
n+|E|\cdot\log n+n^{1+1/\kappa}\log^{2}n)\cdot\beta n^{\rho}\cdot O(\log
n)^{\log\kappa\rho+1/\rho-1})=O((|E|\cdot\log
n+n^{1+1/\kappa}\cdot\log^{2}n)n^{\rho}\cdot O(\log
n)^{\log\kappa\rho+1/\rho-1}$ processors.

Once all hopsets $\\{\mathcal{H}^{k}\ |\ k\in K\\}$ are constructed, the
hopset $H$ is computed. For every edge $(X,Y)$ in a hopset $\mathcal{H}^{k}$,
for some $k\in K$, a single edge is added to $H$. This can be done in $O(1)$
time using $O(n^{1+\frac{1}{\kappa}}{\log^{2}n})$ processors.

It follows that the number of processors used by the algorithm is bounded by

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

The following theorem summarizes the properties of the hopset $H$.

######  Theorem D.1.

Given a weighted undirected graph $G=(V,E,\omega)$ on $n$ vertices, and
parameters $0<\epsilon<1/2$, $\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
$O\left(n^{1+\frac{1}{\kappa}}\cdot{\log^{2}n}\right)$ in
$O(({\log\kappa\rho}+1/\rho)\beta{\log^{3}n})$ time in the PRAM CREW model
using $(|E|+n^{1+\frac{1}{\kappa}})\cdot n^{\rho}\cdot\left({\log
n}\right)^{O({\log\kappa\rho}+1/\rho)}$ processors, 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}.$

###  D.2 Retrieving Paths

In this section, we show how one can use the hopset $H$ described in Appendix
D.1 to construct a $(1+\epsilon)$-SPT $T=(V,E_{T})$ where $E_{T}\subseteq E$.
First, a parallel Bellman-Ford exploration is executed in the graph
$\mathcal{G}=(V,E\cup H)$ from the source $s$ to depth $\beta$. As a result, a
$(1+\epsilon)$-SPT $\mathcal{T}$ is computed. For every vertex $v\in V$, let
$p(v),d(v)$ be the parent and distance of $v$ from $s$ obtained by the
exploration, respectively. Observe that for all $v\in V$, we have
$d(v)\leq(1+\epsilon)d_{G}(s,v)$ and also $d(v)=d(p(v))+\omega(p(v),v)$, where
$\omega(p(v),v)$ is the weight of the edge $(p(v),v)$.

We now replace hopset edges of $\mathcal{T}$ with paths that belong to the
original graph $G$. This is done in three steps. First, we replace hop-edges
from $\bigcup_{k\in K}\mathcal{H}^{k}$ with paths that contain edges (of
$\bigcup_{k\in K}\mathcal{G}^{k}$) between neighboring node centers. Then, we
replace edges between neighboring node centers with star edges and original
graph edges. Finally, we replace star edges with original graph edges. See
Figures 11 for an illustration.

(a) The output $\mathcal{T}$ of the Bellman-Ford exploration. The tree
$\mathcal{T}$ contains original graph edges (solid arrows), hop-edges (dashed
arrows) and star edges (dotted arrows).

(b) The tree $\mathcal{T}$ after the first step. The hopset edge between the
node centers of $X,Y$ is replaced by a path that contains edges between
neighboring node centers.

(c) The tree $\mathcal{T}$ after the second step. Each edge between
neighboring node centers is replaced by a path that contains two star edges
(dotted arrows) and one graph edge (solid arrows).

(d) The tree $\mathcal{T}$ after the third (and final) step. Star edges
(dotted arrows) are replaced by graph edges (solid arrows).

Figure 11: The three steps for replacing hopset edges with graph edges.

The first step consists of executing Algorithm 1 described in Section 4 to
replace each _hop-edge_ $(x^{*},y^{*})$ with the memory paths associated with
it. Recall that this procedure replaces _all_ hop-edges, i.e., when it
terminates, there are no hop-edges left in $\mathcal{T}$. This procedure is
executed in parallel for every $k\in K$. When the procedure terminates, each
vertex selects the best distance estimate (and parent) provided to it by the
respective procedure. We note that some vertices may receive distance
estimates from more then one procedure. Each vertex chooses the smallest
distance estimate it receives. Observe that for every vertex $v\in V$ that has
updated its parent during this step, we have that at the end of this step both
$p(v)$ and $v$ are centers of neighboring nodes. Recall that during Algorithm
1 vertices do not increase their distance estimate. By arguments similar to
those given in Section 4, one can show that for every vertex $v\in
V\setminus\\{s\\}$, we have that $d(v)$ is an upper bound on the distance of
$v$ from $s$ in the tree $\mathcal{T}$, and also $d(p(v))<d(v)$. Therefore, we
have that at the end of the first step, $\mathcal{T}$ is still a
$(1+\epsilon)$-SPT for $G\cup H$.

The second step consists of replacing edges between neighboring nodes centers
with star edges and original graph edges. Let $(p(v),v)$ be an edge in
$\mathcal{T}$, such that $X,Y$ are the nodes centered around $p(v),v$,
respectively. Since $X,Y$ are neighboring nodes, by construction there exists
an edge $(x,y)\in E$ such that $x\in X$ and $y\in Y$. Let $(x,y)\in E$ be the
lightest edge such that $x\in X$ and $y\in Y$. (For every superedge $(X,Y)$ in
$\bigcup_{k\in K}\mathcal{H}^{k}$, the lightest edge $(x,y)\in E\cup\\{X\times
Y\\}$ was already computed.) See Figure 12 for an illustration. The edge
$(p(v),v)$ is now replaced by the path $P=\langle p(v)-x-y-v\rangle$. First,
the vertex $v$ changes its parent and sets $p(v)=y$. Then, $v$ informs $x,y$
of the estimates they obtain from the estimate of $p(v)$ and the path $P$. Let
$d_{1}=d(p(v))+\omega(p(v),x)$, where $\omega(p(v),x)$ is the weight of the
star edge between $p(v)$ and $x$. Let $d_{2}=d_{1}+\omega(x,y)$.

We maintain a global array $M$, in which every vertex has two designated
cells. The vertex $v$ writes the triplets $\langle x,d_{1},p(v)\rangle$ and
$\langle y,d_{2},x\rangle$ to its cells in $M$. The array $M$ is now sorted
according to the first field of the triplets. Ties are broken according to the
second field. Every vertex $u\in V\setminus\\{s\\}$ now searches for the best
distance estimate that $M$ provides for it, i.e., the first triplet $\langle
u,d,u^{\prime}\rangle$ in $M$. If $d<d(u)$, then $u$ sets $p(u)=u^{\prime}$
and $d(u)=d$. This concludes the description of the second step. When this
step terminates, for every vertex $v\in V\setminus\\{s\\}$, the edge
$(p(v),v)$ is either an edge of the original graph or a star edge.

Observe that during the second step, vertices do not increase their distance
estimates. In addition, for every vertex $v\in V$ that has updated its parent
during this step, we have that its current parent and distance estimate
$d(v),p(v)$ satisfy $d(p(v))+\omega(p(v),v)\leq d(v)$. Since all edge weights
are positive, we also have $d(p(v))<d(v)$. Hence, there are no cycles in
$\mathcal{T}$. Therefore, $\mathcal{T}$ is still a $(1+\epsilon)$-SPT for
$G\cup H$.

Figure 12: The second step. The curved line depicts an edge $(p(v),v)$ in the
tree $\mathcal{T}$ that belongs to some graph $\mathcal{G}^{k}$. The dashed
edge $(x,y)$ is the lightest edge in $E$ such that $x$ belongs to the node of
$p(v)$ and $y$ belongs to the node of $v$. The arrows depict the spanning tree
of each node. The dotted curved edges represent star edges. In the second
step, the edge $(p(v),v)$ is replaced by the path $\langle p(v)-x-y-v\rangle$,
where $(p(v),x),(y,v)$ are star edges.

The third step consists of replacing star edges from $\mathcal{T}$ with
original graph edges. Recall that for each node $U$ centered around a vertex
$u^{*}$, a spanning tree $T_{U}$ was computed. In addition, each vertex $u\in
U\setminus\\{u^{*}\\}$ knows its neighbor $p_{u^{*}}(u)$ on the path from $u$
to $u^{*}$ in the spanning tree $T_{U}$, and also the distance in $T_{U}$
between $u^{*}$ and $u$. We replace star edges with edges of the spanning
trees of the corresponding nodes. Let $(p(v),v)$ be a star edge . We say that
$(p(v),v)$ is an edge of _type A_ if $p(v)$ is the center of the node of
$p(v)$ and $v$. Otherwise (i.e., $v$ is the center of the node of $p(v)$ and
$v$), it is said to be an edge of _type B_.

Consider an edge $(p(v),v)$ of type $A$. The vertex $v$ updates its parent
$p(v)$ to be $p_{p(v)}(v)$. We note that it is possible that at this point,
$d(p(v))+\omega(p(v),v)>d(v)$. To remedy this, every vertex $u\in V$ now
checks if there exists a node $U$ such that $u\in U$, and such that the center
$u^{*}$ of $U$ satisfies $d(u^{*})+d_{T_{U}}(u^{*},u)<d(u)$. (Note that this
computation can be performed in $O({\log n})$ time using $O(n{\log n})$
processors, using the array $B$ computed together with the set of star edges
$S$. See the discussion that follows Lemma C.1.) If there exists such node,
then $u$ updates its parent and distance estimate accordingly. Let $U,u^{*}$
be the node and node center such that $u\in U$, and
$d(u^{*})+d_{T_{U}}(u^{*},u)$ is minimal. Then, $u$ sets
$d(u)=d(u^{*})+d_{T_{U}}(u^{*},u)$ and also $p(u)=p_{u^{*}}(u)$. Observe that
at this point there are no edges of type $A$, and for every $v\in
V\setminus\\{s\\}$ we have $d(p(v))+\omega(p(v),v)\leq d(v)$. See Figure 13
for an illustration.

We now remove edges of type $B$ from $\mathcal{T}$. Consider an edge
$(u,u^{*})$ of type $B$, such that $u^{*}$ is the center of a node $U$ and
$u\in U$. Intuitively, replacing this edge requires flipping the direction of
the parent-child relationship along the $u-u^{*}$ path $\pi_{U}(u,u^{*})$ in
the spanning tree $T_{U}$.

This is done in the following manner. First, $u^{*}$ informs $u$ that the star
edge must be replaced. Then, a pointer-jumping algorithm is used to inform all
vertices on the path $\pi_{U}(u,u^{*})$ that they belong to this path. Every
vertex $v$ (other than $u^{*}$) along this path now writes to a designated
array $c_{U}(p(v))=v$, to inform its parent $p(v)$ that $v$ is its child along
this path. The vertex $u^{*}$ now sets $p(u^{*})=c_{U}(u^{*})$. At this point,
there are no more edges of type $B$ in $\mathcal{T}$. However, $d(u^{*})$ may
be smaller than $d(p(u^{*}))+\omega(p(u^{*}),u^{*})$. To remedy this, a
pointer-jumping algorithm is used again to compute for every $v\in P$ the
distance $d_{P}(u,v)$, i.e., its distance from $u$ along the path
$\pi_{U}(u,u^{*})$. Observe that $u$ may belong to multiple paths that require
flipping. For every vertex $v\in V$, let $P=\pi_{U}(u,u^{*})$ be the path such
that $d(u)+d_{P}(u,v)$ is minimal. If $d(u)+d_{P}(u,v)<d(v)$, then $v$ updates
$p(v)=c_{U}(v)$ and $d(v)=d(u)+d_{P}(u,v)$. When this process terminates, we
have $d(p(v))+\omega(p(v),v)\leq d(v)$ for every vertex $v\in
V\setminus\\{s\\}$.

Figure 13: Replacing edges of type $A$. The dotted edge $(p(v),v)$ is an edge
of type $A$, where $p(v)$ is the center of the node $U$. The straight lines
depict edges of the spanning tree $T_{U}$ of the node $U$. The vertex $v$ sets
its parent to be its neighbor on the path in $T_{U}$ from it to $p(v)$. In
addition, every vertex $u\in U$ ensures that its distance estimate is no
greater than $d(p(v))+d_{T_{U}}(u)$.

(a)

(b)

Figure 14: Replacing edges of type $B$. The dotted edge $(u,u^{*})$ is an edge
of type B, where $u^{*}$ is the center of the node $U$. In Figure 14(a), the
arrows depict the path $P$ from $u$ to $u^{*}$ in the spanning tree $T_{U}$ of
a node $U$. In Figure 14(b) the arrows depict the path $P$ after the direction
of all edges has been flipped.

This completes the description of the path-reporting algorithm. Define now
$T=(V,E_{T})$ as the tree obtained by executing steps $1-3$. Observe that
throughout the algorithm, the distance estimate of each vertex did not
increase w.r.t. the estimate it obtained by the Bellman-Ford exploration in
$G\cup H$. Therefore, at the end of the exploration, for every $v\in V$ we
have that $d(v)\leq(1+\epsilon)d_{G}(s,v)$. In addition, for every vertex
$v\in V\setminus\\{s\\}$, we have $d(v)\geq d(p(v))+\omega(p(v),v)$, where
$\omega(p(v),v)$ is the weight of the edge $(p(v),v)$ in the original graph
$G$. Since the edge weights are positive, there are no cycles in
$\mathcal{T}$.

When the three steps terminate, for every vertex $v\in V\setminus\\{s\\}$ we
have $(p(v),v)\in E$. Let now $T=(V,E_{T})$, where $E_{T}=\\{(p(v),v)\ |\ v\in
V\setminus\\{s\\}\\}$. As in Section 4, we now use a pointer-jumping algorithm
to compute for every vertex $v\in V$ its distance from $s$ w.r.t. the tree
$T$. Observe that for every vertex $v\in V$, its final distance estimate is at
most the original estimate we obtained by the Bellman-Ford exploration. Hence
$T$ is a $(1+\epsilon)$-SPT for $G$, and also $E_{T}\subseteq E$.

#### D.2.1 Complexity

By Theorem D.1, the hopset $H$ can be computed in
$O(({\log\kappa\rho}+1/\rho)\beta{\log^{3}n})$ time using
$(|E|+n^{1+\frac{1}{\kappa}})\cdot n^{\rho}\cdot\left({\log
n}\right)^{O({\log\kappa\rho}+1/\rho)}$ processors.

As in Section 4, the time and work required for the Bellman-Ford exploration
and for the first step are dominated by the time and work required for
constructing the hopset $H$.

The second step requires some vertices to write to $O(1)$ cells in an array of
length $O(n)$, sorting the array, and executing $n$ binary search processes
(in parallel). This can be done in $O(\log n)$ time using $O(n)$ processors.

The third step consists of two parts, i.e., replacing edges of type $A$ and of
type $B$. Replacing edges of type $A$ requires each vertex to check whether a
center of its node provides it with a better distance estimate than the
estimate it currently possesses. Observe that some vertices may be members of
a linear number of nodes. Therefore, a naive implementation of this step that
uses only $O(n^{\rho})$ processors to simulate each vertex may require
polynomial time. However, for every center $u^{*}$ of a node $U$ that a vertex
$u$ belongs to, there is a star edge $(u,u^{*})$ in $S$. This edge was
allocated $O(n^{\rho})$ processors. To execute this step efficiently, each
star edge $(u,u^{*})\in S$ contributes a single processor $proc_{(u,u^{*})}$
to assist $u$ with checking whether this star edge provides it with a better
distance estimate. To select the best distance estimate, the star edges
processor $proc_{(u,u^{*})}$ writes the distance estimate that $(u,u^{*})$
provides for $u$ to a designated array, which is then sorted to find its
minimum. This can be done using $\tilde{O}(n)$ processors in $O({\log n})$
time.

The second part, requires _flipping_ the direction of some paths in the
spanning trees of some nodes. For every node $U$, this can be done using
$O(|U|)$ processors in $O({\log n})$ time in the CREW PRAM model. This
algorithm is executed in parallel for all nodes. Every vertex $u\in U$ is
simulated by the star edge from $u$ to the center of $U$. The center of $U$ is
simulated by an additional processor. Recall that by eq. 24, we have $|S|\leq
n{\log n}$. Therefore, this algorithm can be executed in $O({\log n})$ time
using $\tilde{O}(n)$ processors.

It follows that the overall time and work required to complete the
construction of the path-reporting hopset and to retrieve a $(1+\epsilon)$-SPT
in $G$ is dominated by the time and work required for constructing the hopset
$H$. The following theorem summarizes the properties of the path-reporting
algorithm.

######  Theorem D.2.

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

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

Note that $\rho\geq 1/{\log n}$, as otherwise the result is meaningless. Thus,
$\beta=\left(\frac{\log n}{\epsilon}\right)^{O({\log\kappa\rho}+1/\rho)}$, and
the time is bounded by this expression as well.

## References

  * [ABP17] Amir Abboud, Greg Bodwin, and Seth Pettie.  A hierarchy of lower bounds for sublinear additive spanners.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 568–576, 2017.
  * [AGHP92] Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta.  Simple construction of almost k-wise independent random variables.  Random Struct. Algorithms, 3(3):289–304, 1992.
  * [AGLP89] Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin.  Network decomposition and locality in distributed computation.  In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 364–369, 1989.
  * [AGM97] Noga Alon, Zvi Galil, and Oded Margalit.  On the exponent of the all pairs shortest path problem.  J. Comput. Syst. Sci., 54(2):255–262, 1997.
  * [AKS83] Miklós Ajtai, János Komlós, and Endre Szemerédi.  An o(n log n) sorting network.  In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 1–9, 1983\.
  * [ASZ19] Alexandr Andoni, Clifford Stein, and Peilin Zhong.  Parallel approximate undirected shortest paths via low hop emulators.  CoRR, abs/1911.01956, 2019.
  * [Ber09] Aaron Bernstein.  Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 693–702. IEEE Computer Society, 2009.
  * [BKKL16] Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen.  Approximate undirected transshipment and shortest paths via gradient descent.  CoRR, abs/1607.05127, 2016.
  * [BR11] Aaron Bernstein and Liam Roditty.  Improved dynamic algorithms for maintaining approximate shortest paths under deletions.  In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1355–1365. SIAM, 2011.
  * [BRS94] Bonnie Berger, John Rompel, and Peter W. Shor.  Efficient NC algorithms for set cover with applications to learning and geometry.  J. Comput. Syst. Sci., 49(3):454–477, 1994.
  * [Coh94] Edith Cohen.  Polylog-time and near-linear work approximation scheme for undirected shortest paths.  In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 16–26, 1994.
  * [Coh97] Edith Cohen.  Using selective path-doubling for parallel shortest-path computations.  J. Algorithms, 22(1):30–56, 1997.
  * [CW87] Don Coppersmith and Shmuel Winograd.  Matrix multiplication via arithmetic progressions.  In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 1–6. ACM, 1987.
  * [EGN19] Michael Elkin, Yuval Gitlitz, and Ofer Neiman.  Almost shortest paths and PRAM distance oracles in weighted graphs.  CoRR, abs/1907.11422, 2019.
  * [EM19] Michael Elkin and Shaked Matar.  Near-additive spanners in low polynomial deterministic CONGEST time.  CoRR, abs/1903.00872, 2019.
  * [EN17a] Michael Elkin and Ofer Neiman.  Efficient algorithms for constructing very sparse spanners and emulators.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 652–669, 2017.
  * [EN17b] Michael Elkin and Ofer Neiman.  Linear-size hopsets with small hopbound, and distributed routing with low memory.  CoRR, abs/1704.08468, 2017.
  * [EN18] Michael Elkin and Ofer Neiman.  Near-optimal distributed routing with low memory.  In Calvin Newport and Idit Keidar, editors, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 207–216. ACM, 2018.
  * [EN19] Michael Elkin and Ofer Neiman.  Hopsets with constant hopbound, and applications to approximate shortest paths.  SIAM J. Comput., 48(4):1436–1480, 2019.
  * [EN20] Michael Elkin and Ofer Neiman.  Centralized and parallel multi-source shortest paths via hopsets and fast matrix multiplication.  CoRR, abs/2004.07572, 2020.
  * [EP01] Michael Elkin and David Peleg.  (1+epsilon, beta)-spanner constructions for general graphs.  In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 173–182, 2001.
  * [GM97] Zvi Galil and Oded Margalit.  All pairs shortest paths for graphs with small integer length edges.  J. Comput. Syst. Sci., 54(2):243–254, 1997.
  * [GPS88] Andrew V. Goldberg, Serge A. Plotkin, and Gregory E. Shannon.  Parallel symmetry-breaking in sparse graphs.  SIAM J. Discrete Math., 1(4):434–446, 1988.
  * [GU18] Francois Le Gall and Florent Urrutia.  Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1029–1046. SIAM, 2018.
  * [HKN16] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai.  A deterministic almost-tight distributed algorithm for approximating single-source shortest paths.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 489–498, 2016.
  * [HP19] Shang-En Huang and Seth Pettie.  Thorup-zwick emulators are universally optimal hopsets.  Inf. Process. Lett., 142:9–13, 2019.
  * [JáJ92] Joseph JáJá.  An Introduction to Parallel Algorithms.  Addison-Wesley, 1992.
  * [KMW18] Fabian Kuhn, Yannic Maus, and Simon Weidner.  Deterministic distributed ruling sets of line graphs.  In Structural Information and Communication Complexity - 25th International Colloquium, SIROCCO 2018, Ma’ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers, pages 193–208, 2018.
  * [KP83] Richard. Karp and Nicholas Pippenger.  A time-randomness tradeoff.  In AMS Conference on Probabilistic Computational Complexity, volume 111, 1983.
  * [KR88] Howard J. Karloff and Prabhakar Raghavan.  Randomized algorithms and pseudorandom numbers.  In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 310–321. ACM, 1988.
  * [KR90] Richard M. Karp and Vijaya Ramachandran.  Parallel algorithms for shared-memory machines.  In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, pages 869–942. Elsevier and MIT Press, 1990.
  * [KS92] Philip N. Klein and Sairam Sairam.  A parallel randomized approximation scheme for shortest paths.  In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 750–758. ACM, 1992.
  * [KS97] Philip N. Klein and Sairam Subramanian.  A randomized parallel algorithm for single-source shortest paths.  J. Algorithms, 25(2):205–220, 1997.
  * [KW85] Richard M. Karp and Avi Wigderson.  A fast parallel algorithm for the maximal independent set problem.  J. ACM, 32(4):762–773, 1985.
  * [Li19] Jason Li.  Faster parallel algorithm for approximate shortest path.  CoRR, abs/1911.01626, 2019.
  * [Lub86] Michael Luby.  A simple parallel algorithm for the maximal independent set problem.  SIAM J. Comput., 15(4):1036–1053, 1986.
  * [Mad13] Aleksander Madry.  Navigating central path with electrical flows: From flows to matchings, and back.  In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 253–262. IEEE Computer Society, 2013.
  * [NN93] Joseph Naor and Moni Naor.  Small-bias probability spaces: Efficient constructions and applications.  SIAM J. Comput., 22(4):838–856, 1993.
  * [NW88] Noam Nisan and Avi Wigderson.  Hardness vs. randomness (extended abstract).  In 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988, pages 2–11. IEEE Computer Society, 1988.
  * [SEW13] Johannes Schneider, Michael Elkin, and Roger Wattenhofer.  Symmetry breaking depending on the chromatic number or the neighborhood growth.  Theor. Comput. Sci., 509:40–50, 2013.
  * [She16] Jonah Sherman.  Generalized preconditioning and network flow problems.  CoRR, abs/1606.07425, 2016.
  * [Spe97] Thomas H. Spencer.  Time-work tradeoffs for parallel algorithms.  J. ACM, 44(5):742–778, 1997.
  * [SS99] Hanmao Shi and Thomas H. Spencer.  Time-work tradeoffs of the single-source shortest paths problem.  J. Algorithms, 30(1):19–32, 1999.
  * [SV82] Yossi Shiloach and Uzi Vishkin.  An o(log n) parallel connectivity algorithm.  J. Algorithms, 3(1):57–67, 1982.
  * [TZ01] Mikkel Thorup and Uri Zwick.  Compact routing schemes.  In Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, pages 1–10. ACM, 2001.
  * [TZ06] Mikkel Thorup and Uri Zwick.  Spanners and emulators with sublinear distance errors.  In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 802–809, 2006.
  * [UY91] Jeffrey D. Ullman and Mihalis Yannakakis.  High-probability parallel transitive-closure algorithms.  SIAM J. Comput., 20(1):100–125, 1991.
  * [Wil12] Virginia Vassilevska Williams.  Multiplying matrices faster than coppersmith-winograd.  In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 887–898. ACM, 2012.
  * [Zwi98] Uri Zwick.  All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms.  In 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, November 8-11, 1998, Palo Alto, California, USA, pages 310–319. IEEE Computer Society, 1998.
  * [Zwi02] Uri Zwick.  All pairs shortest paths using bridging sets and rectangular matrix multiplication.  J. ACM, 49(3):289–317, 2002.