[1]${O}\left(#1\right)$ [1]${\tilde{{O}}}\left(#1\right)$
[1]${o}\left(#1\right)$ [1]${\tilde{{o}}}\left(#1\right)$
[1]${\Omega}\left(#1\right)$ [1]${\tilde{{\Omega}}}\left(#1\right)$
[1]${\omega}\left(#1\right)$ [1]${\tilde{{\omega}}{\left(#1\right)}}$
[1]${\Theta}\left(#1\right)$ [1]${\tilde{{\Theta}}\left(#1\right)}$

# Improved All-Pairs Approximate Shortest
Paths in Congested Clique

Hong Duc Bui111National University of Singapore. Email<EMAIL_ADDRESS>Shashwat Chandra222National University of Singapore. Email:
<EMAIL_ADDRESS>Yi-Jun Chang333National University of Singapore.
Email<EMAIL_ADDRESS>Michal Dory444University of Haifa. Email:
<EMAIL_ADDRESS>Dean Leitersdorf555National University of Singapore.
Email<EMAIL_ADDRESS>
###### Abstract

In this paper, we present new algorithms for approximating All-Pairs Shortest
Paths (APSP) in the Congested Clique model. We present randomized algorithms
for weighted undirected graphs.

Our first contribution is an $O(1)$-approximate APSP algorithm taking just
$O(\log\log\log n)$ rounds. Prior to our work, the fastest algorithms that
give an $O(1)$-approximation for APSP take $\operatorname{poly}(\log{n})$
rounds in weighted undirected graphs, and
$\operatorname{poly}(\log\log\allowbreak n)$ rounds in unweighted undirected
graphs.

If we terminate the execution of the algorithm early, we obtain an
$O(t)$-round algorithm that yields an $O\big{(}(\log n)^{1/2^{t}}\big{)}$
distance approximation for a parameter $t$. The trade-off between $t$ and the
approximation quality provides flexibility for different scenarios, allowing
the algorithm to adapt to specific requirements. In particular, we can get an
$O\big{(}(\log n)^{1/2^{t}}\big{)}$-approximation for any constant $t$ in
$O(1)$-rounds. Such result was previously known only for the special case that
$t=0$.

A key ingredient in our algorithm is a lemma that allows to improve an
$O(a)$-approximation for APSP to an $O(\sqrt{a})$-approximation for APSP in
$O(1)$ rounds. To prove the lemma, we develop several new tools, including
$O(1)$-round algorithms for computing the $k$ closest nodes, a certain type of
hopset, and skeleton graphs.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contribution
  2. 2 Technical Overview
  3. 3 Preliminaries
    1. 3.1 Definitions and Notation
    2. 3.2 Handling Zero Edge Weights
    3. 3.3 Useful Tools
  4. 4 Approximation to Hopset
    1. 4.1 Algorithm Description
    2. 4.2 Correctness
  5. 5 Fast Computation of the $k$-Nearest Nodes
    1. 5.1 Overview and Comparison with Existing Algorithms
    2. 5.2 Algorithm Description
    3. 5.3 Complexity
    4. 5.4 Correctness
    5. 5.5 Repeating the Algorithm
  6. 6 Skeleton Graph Reduction
    1. 6.1 Algorithm Description
    2. 6.2 Complexity
    3. 6.3 Correctness
  7. 7 The Main Algorithm
    1. 7.1 Preliminaries
    2. 7.2 Approximation Factor Reduction
    3. 7.3 Special Case: When the Diameter $d\in(\log n)^{O(1)}$
    4. 7.4 Reduction From the General Problem to the Small Weighted Diameter Problem
    5. 7.5 Special Case 2: When the Bandwidth is $\log^{4}n$ Bits
    6. 7.6 General Case
    7. 7.7 Limiting the Number of Rounds
  8. 8 Discussion
  9. A Missing Proofs from Section 3

##  1 Introduction

The All-Pairs Shortest Paths (APSP) problem is one of most central and well-
studied problems in graph algorithms. It is especially important in
distributed algorithms because of its connections to network routing. In this
paper, we study the APSP problem in the distributed Congested Clique model. In
this model, we have a fully connected communication network of $n$ nodes that
communicate with each other by sending $\Theta(\log{n})$-bit messages in
synchronous rounds. The input graph $G=(V,E)$ to the APSP problem is given
locally to the nodes, such that each node knows the weights of the edges
adjacent to it in $G$, and at the end it should know its distances from other
nodes. We emphasize that while $G$ can be an arbitrary graph on $n$ nodes, the
communication network is a clique. The main goal is to minimize the number of
communication rounds needed to solve a problem. The Congested Clique model has
received a lot of attention in recent years, partly because of its connections
to modern parallel settings such as the Massively Parallel Computation model.

The problem of computing APSP in Congested Clique has been widely studied in
recent years [4; 11; 5; 2; 9; 8; 6]. The first algorithms for the problem are
based on matrix multiplication and require polynomial time [4; 11; 5]. For
example, APSP in directed weighted graphs can be computed in
$\tilde{O}(n^{1/3})$ rounds, where $O(n^{0.158})$-round algorithms are known
for unweighted undirected graphs [4]. Obtaining faster algorithms for _exact_
APSP may be a hard task, since as proved in [7; 10] obtaining any
approximation better than 2 already solves matrix multiplication, so it
requires developing faster algorithms for matrix multiplication. The same
holds for _any_ approximation in directed graphs, which motivates the study of
the problem in undirected graphs.

Hence, a natural approach for obtaining faster algorithms is to allow
approximation algorithms. A recent line of work [2; 9; 8; 6] led to faster
approximation algorithms for the problem. First, [2] exploits _sparse_ matrix
multiplication algorithms to obtain constant approximation for APSP in _poly-
logarithmic_ number of rounds. This approach gives
$(3+\epsilon)$-approximation for APSP in weighted undirected graphs and
$(2+\epsilon)$-approximation in unweighted undirected graphs. In both cases,
the running time is $O(\log^{2}{n}/\epsilon)$ rounds. A subsequent work gives
faster $\operatorname{poly}(\log\log n)$-round algorithms for a
$(2+\epsilon)$-approximation of APSP in unweighted undirected graphs [9]. The
approach in [9] combines sparse matrix multiplication with fast construction
of emulators, sparse graphs that approximate the distances in the input graph.
Finally, recent works give $O(1)$-round algorithms that give
$O(\log{n})$-approximation for APSP in weighted undirected graphs via a fast
construction of multiplicative spanners [8; 6]. Here the goal is to construct
a sparse graph of size $O(n)$ that approximates the distances in the graph and
broadcast it to the whole network. Because of the known trade-offs between the
size and approximation guarantee of spanners this approach leads to an
$\Omega(\log{n})$-approximation.

To conclude, by now there are very fast algorithms that take just $O(1)$
rounds and give $O(\log{n})$-approximation to APSP. On the other hand, if our
goal is to optimize the approximation ratio, we can get an
$O(1)$-approximation in $\operatorname{poly}(\log{n})$ rounds in weighted
undirected graphs, or in $\operatorname{poly}(\log{\log{n}})$ rounds in
unweighted undirected graphs. A natural goal is to obtain both
$O(1)$-approximation and $O(1)$ rounds simultaneously.

######  Question 1.1.

Can we obtain $O(1)$ approximation to APSP in $O(1)$ rounds?

In the case of weighted undirected graphs, the gap is even larger, as the
fastest $O(1)$-approximation algorithms take $\operatorname{poly}\log n$
rounds, which raises the following question.

######  Question 1.2.

Can we obtain $O(1)$ approximation to APSP on weighted graphs in $o(\log{n})$
rounds?

###  1.1 Our Contribution

In this work, we make progress in answering the above questions, by providing
a positive answer to 1.2. Specifically, we show the following:

######  Theorem 1.1.

There is a randomized666All our randomized algorithms work with high
probability, i.e., they are successful with probability
$1-1/\operatorname{poly}(n)$. $O(1)$-approximation algorithm for weighted
undirected APSP in the Congested Clique model that takes $O(\log\log\log n)$
rounds.

Our result improves exponentially on the number of rounds needed to obtain
$O(1)$-approximation for APSP even in unweighted undirected graphs, and it is
the first sub-logarithmic algorithm for the problem in weighted undirected
graphs.

Our approach also leads to trade-offs between the running time and
approximation. More concretely, our algorithm starts with an
$O(\log{n})$-approximation for APSP and successively improves it. If we
terminate the algorithm early, we obtain the following trade-off between the
number of rounds needed and the approximation factor.

######  Theorem 1.2.

There is a randomized $O(\log^{2^{-t}}n)$-approximation algorithm for weighted
undirected APSP in the Congested Clique model that takes $O(t)$ rounds, where
$t\geq 1$ is provided as a parameter.

In particular, we can get an $O\big{(}(\log n)^{1/2^{t}}\big{)}$-approximation
for any constant $t$ in $O(1)$-rounds. Previously, $O(1)$-round algorithms
were only known for the case of an $O(\log{n})$-approximation.

##  2 Technical Overview

At a high-level, we start with an $O(\log{n})$-approximation and iteratively
improve it. Our algorithm relies crucially on the following lemma that
transforms an $O(a)$-approximation into an $O(\sqrt{a})$-approximation in a
constant number of rounds. By starting with an $O(\log n)$-approximation (that
can be obtained in $O(1)$ rounds from [6]), and repeating the algorithm for
$1$, $2$, $3$, … times, we get an $O(\sqrt{\log n})$, $O(\log^{1/4}n)$,
$O(\log^{1/8}n)$, …-approximation, so that after $O(\log\log\log n)$
repetitions, we are done. For simplicity, many technical details are omitted
from this overview — for instance, the actual lemma only works when $a\in(\log
d)^{\Omega(1)}$ where $d$ is the weighted diameter, afterwards we need to use
a different strategy.

######  Lemma 2.1 (name=Approximation factor
reduction,restate=approximatereduction).

Let $a\geq 1$ be some value such that $a\in O(\log n)$. Assume the graph has
weighted diameter $d$ such that $\log d\in a^{O(1)}$.

There is a randomized $O(1)$-approximation algorithm for weighted undirected
APSP in the Congested Clique model that takes in the value $a$, and a
$(16a)$-approximation of APSP, takes $O(1)$ rounds, and with high probability
computes a $(16\sqrt{a})$-approximation of APSP.

To prove the above lemma, we use the following building blocks, which may be
of interest independently as well.

####  $k$-nearest hopset (Section 4).

As we will see, a main building block in our algorithm is a fast algorithm
that allows each node to compute the distances to its $k$ closest nodes. In
order to get an efficient algorithm for this problem, we use a _hopset_. A
$\beta$-hopset is a set of edges $H$ added to the graph $G$ such that in
$G\cup H$ for any pair of nodes $u,v$ there is a path of at most $\beta$ edges
with weight $d_{G}(u,v)$, where $d_{G}(u,v)$ is the distance between $u$ and
$v$ in the graph $G$. Note that hopsets allow us to consider only paths with a
small number of hops when computing distances. For this reason, hopsets have
found many applications for computing or approximating distances, especially
in distributed and parallel settings. However, existing algorithms for
constructing hopsets in the Congested Clique model require at least a poly-
logarithmic number of rounds [2; 13; 9]. As we aim for a faster running time,
we need a different approach. To overcome it, we introduce a new type of
hopset called a $k$-nearest $\beta$-hopset. In this hopset we are guaranteed
to have $\beta$-hop paths that preserve the distances only for pairs of nodes
$u$ and $v$ such that $v$ is among the $k$-nearest nodes to $u$ (or vice
versa). As our first goal is just to compute distances to the $k$-nearest
nodes, a $k$-nearest hopset is good enough for our needs.

We show a surprisingly simple $O(1)$-round algorithm for constructing a
$k$-nearest hopset $H$ given an $a$-approximation for APSP. We focus on the
case that $k=\sqrt{n}$.

######  Lemma 2.2 (name=Approximation to Hopset, restate=ahop).

Let $G$ be a graph with positive integer weights and weighted diameter $d$,
and assume we are given an $a$-approximation of APSP. Then we can
deterministically compute a $\sqrt{n}$-nearest $\beta$-hopset $H$ in $O(1)$
rounds, where $\beta\in O(a\log d)$.

At a high-level, to construct the hopset $H$, each node $u$ starts by
computing a set $\tilde{N}_{\sqrt{n}}(u)$ of the approximately
$\sqrt{n}$-nearest nodes to $u$. This set is computed by taking the
$k$-nearest nodes according to the given $a$-approximation. Then $u$ learns
from each node $v\in\tilde{N}_{\sqrt{n}}(u)$ about the $\sqrt{n}$ minimum
weight edges adjacent to $v$. The node $u$ computes shortest paths in the
received graph (including also all the edges adjacent to $u$), and based on
this information $u$ adds edges to the hopset $H$ (see Section 4 for full
details). The algorithm takes $O(1)$ rounds as each node just needs to learn
$O(n)$ edges, which can done in $O(1)$ rounds (using Lemma 3.2). We prove that
the computed set $H$ is a $\sqrt{n}$-nearest $\beta$-hopset for $\beta\in
O(a\log d)$. To get an intuition for the proof, denote by $l(u)$ the smallest
distance such that there are at least $\sqrt{n}$ nodes at distance $l(u)$ from
$u$. We can show that the set $\tilde{N}_{\sqrt{n}}(u)$ of the approximately
closest $\sqrt{n}$ nodes already contains all nodes at distance $(l(u)-1)/a$
from $u$. We can use this fact to show that for any node $v$ in $u$’s
$\sqrt{n}$-nearest nodes we can use 2 edges of $G\cup H$ to cover at least
$\frac{1}{a}$ fraction of the distance to $v$. We next show a triangle-
inequality-like property for the values $l(u)$, that allows to prove that we
can use 2 other edges to cover $\frac{1}{a}$ fraction of the remaining
distance, and so on. Overall, we show that after $O(a\log{d})$ hops we reach
$v$. For details see Section 4.

#### Fast computation of the $k$-nearest nodes (Section 5).

Our next goal is to use the hopset to compute the $k$-nearest nodes for each
node. Naively this may take $\Omega(a\log{d})$ rounds, as this is the number
of hops in the hopset. A faster algorithm can be obtained using fast matrix
multiplication as shown in [2; 9]. At a high-level, this approach works in $i$
iterations where in iteration $i$ nodes learn about paths with $2^{i}$ hops.
Using this approach in our case will take at least
$\Omega(\log{(a\log{d})})\subseteq\Omega(\log{\log{n}})$ rounds, as our
initial approximation is $a\in O(\log{n})$ and the weighted diameter $d$ is
polynomial (we assume that the weights are polynomial as standard in this
model). This running time is still too high. To get a faster algorithm, we
identify cases in which the $k$-nearest nodes can be computed in just $O(1)$
rounds, in particular we show the following.

######  Lemma 2.3 (name=Fast $k$-nearest,restate=matrixexp).

Given a graph $G$ with positive integer weights and a $k$-nearest
$h^{O(1)}$-hopset $H$ for $G$ such that any node can reach the $k\in
O(n^{1/h})$ nodes closest to it in $h^{O(1)}$ hops, then each node can
deterministically compute the exact distance to the $k$ nodes closest to it in
$O(1)$ rounds.

Note that this lemma allows computing distances to a non-constant number $k$
of closest nodes in $O(1)$ rounds. As an example, we can combine it with our
$k$-nearest hopset to compute distances to $k=2^{\sqrt{\log{n}}}$ nodes in
$O(1)$ rounds. To see this choose $h=\sqrt{\log{n}}$, and note that since the
number of hops in our hopset is $O(\log^{2}{n})$ we can write it as $h^{i}$
for a constant $i$.

The proof idea of Lemma 2.3 is to distribute the edges of the graph $G\cup H$
between the nodes such that each relevant $h$-hop path from a node $u$ to a
node $v$ in its $k$-nearest nodes will be known by some node $w$, that will
then send the information back to $u$. The approach is inspired by algorithms
for path listing [3] and neighborhood collection [6] that work for sparse
graphs (in one case graphs without small cycles, and in the other low-degree
graphs). While in our case the input graph is not necessarily sparse, we can
exploit the fact that we are only interested in a sparse part of the output
(distances to the $k$-nearest nodes) to get a fast algorithm. To do so, we
distribute the edges in a certain way that indeed allows to collect the
distances to the $k$ closest nodes efficiently. For details see Section 5.

#### Skeleton graph (Section 6).

Finally, our goal is to extend the distances computed to the $k$-nearest nodes
to distances between all pairs of nodes. To do so, we show that after
computing the distances to the $k$-nearest nodes we can construct a skeleton
graph $G_{S}$ with $\tilde{O}(n/k)\ll n$ nodes, such that an approximation of
APSP on $G_{S}$ can be used to compute an approximation of APSP on $G$.

######  Lemma 2.4 (Skeleton Graph — Simplified Version).

Let $k$ be an integer between $1$ and $n$. Suppose we are given a graph $G$,
and that each node knows the distances to its $k$-nearest nodes in the graph
$G$. Then, with high probability, we can construct a graph $G_{S}$ over a
subset $V_{S}\subseteq V$ of $O(\frac{n\log k}{k})$ nodes in $O(1)$ rounds of
Congested Clique, such that given an $l$-approximation of APSP on $G_{S}$, we
can compute a $7l$-approximation of APSP on $G$ in $O(1)$ rounds.

At a high-level, Lemma 2.4 allows to convert the problem of computing APSP on
$G$ to computation of APSP on a smaller graph. Note that the smaller $G_{S}$
is, the better we are at obtaining knowledge of approximate APSP — for
instance, if $G_{S}$ has less than $\sqrt{n}$ nodes, we can simply broadcast
all edges of $G_{S}$ in order to exactly compute the shortest distance on
$G_{S}$, and thus get an $O(1)$-approximation for APSP on $G$. Skeleton graphs
were used before in the computation of shortest paths. The most standard
example we are aware of is to sample a set of nodes of size $\tilde{O}(n/k)$,
and connect pairs of sampled nodes that are at distance $\tilde{O}(k)$ from
each other, which can lead to a running time that depends on $k$ (also as
$\tilde{O}(n/k)$ can be large, it is unclear how to compute distances from
this set of nodes efficiently even if the paths are short). We take a
different approach. We just connect pairs of sampled nodes that have a path of
$O(1)$ edges between them of a certain structure in the graph $G$ after also
adding to $G$ the edges connecting each node to its $k$-nearest nodes (with
the edge weight being the known distance of the shortest path between them).
We use the structure of the paths and the fact they only have $O(1)$ edges to
show that we can construct $G_{S}$ in $O(1)$ rounds, and we prove that working
with this skeleton graph only adds a constant factor to the approximation. For
details see Section 6.

#### Putting everything together.

First, the ingredients described above already allow to get an
$O(1)$-approximation for APSP in weighted graphs in $O(\log{\log{n}})$ rounds.
To do so, we compute the distances to the $\sqrt{n}$-nearest nodes in
$O(\log{\log{n}})$ rounds (this can be done by combining our hopset and matrix
exponentiation as discussed above, see Lemma 5.2 with $h=2$). Then, we can
construct a skeleton graph with $\tilde{O}(\sqrt{n})$ nodes $G_{S}$. Since
$G_{S}$ is small, we can construct a 3-spanner of $G_{S}$ of size $O(n)$ in
$O(1)$ rounds that can be broadcast to the whole graph. Using Lemma 2.4 this
can be translated to an $O(1)$-approximation of the distances in $G$.

To obtain a faster $O(\log{\log{\log{n}}})$-round algorithm, we want to
combine this approach with our faster algorithm for computing the $k$-nearest
nodes. However this algorithm only works when $k\in O(n^{1/h})$ (such that
$h^{O(1)}$ is the number of hops in the hopset), so we cannot apply it
directly for $k=\sqrt{n}$. Instead, we work in iterations, where in each
iteration we improve the approximation for APSP, and increase the value of $k$
that we can consider. Consequently, the size of the graph $G_{S}$ and the
number of hops in the hopset decrease in each iteration.

More concretely, we combine the above ingredients to prove Lemma 2.1 that
allows improving an $a$-approximation to an $O(\sqrt{a})$-approximation in
$O(1)$ rounds. We work as follows.

  1. 1.

We start with a given $a$-approximation of APSP (initially this is an
$O(\log{n})$-approximation).

  2. 2.

We compute a $\sqrt{n}$-nearest $O(a\log{d})$-hopset using Lemma 2.2.

  3. 3.

We use the computed hopset and Lemma 2.3 to compute the distances to the
$k$-nearest nodes, for a carefully chosen value of $k$.

  4. 4.

We compute a subgraph $G_{S}$ with $\tilde{O}(n/k)\ll n$ nodes, such that an
approximation of APSP on $G_{S}$ can be used to compute an approximation of
APSP on $G$ (using Lemma 2.4).

  5. 5.

We use the smaller size of $G_{S}$ to compute an $O(\sqrt{a})$-approximation
for APSP on $G_{S}$ in $O(1)$ rounds, which gives an
$O(\sqrt{a})$-approximation for APSP on $G$.

To complete the description of the algorithm, we should specify the value of
$k$, and explain how we compute approximate APSP on $G_{S}$ in the last step.
Note that all other steps take $O(1)$ rounds. To specify the value of $k$, we
focus first on the case that $a\in O(\log{n})$. Intuitively, we would like to
choose $h\approx\sqrt{\log{n}}$, and then $k\approx
n^{1/\sqrt{\log{n}}}=2^{\sqrt{\log{n}}}$. It can be verified (as mentioned
above) that with this choice, we can use Lemma 2.3 and compute the distances
to the $k$-nearest nodes in $O(1)$ rounds. Now if the size of $G_{S}$ was
$O(n/k)=O(n/2^{\sqrt{\log{n}}})$, then we can compute an
$O(\sqrt{\log{n}})$-approximation for APSP in $G_{S}$ as follows. We construct
an $O(\sqrt{\log{n}})$-spanner of size $O(n/k)^{1+1/\sqrt{\log{n}}}\subseteq
O(n)$ for $G_{S}$, such spanners can be constructed in $O(1)$ rounds. Now
since the spanner has size $O(n)$ we can broadcast it to the whole graph and
get an $O(\sqrt{\log{n}})$-approximation to the distances in $G_{S}$ and in
$G$, as needed. Since the size of $G_{S}$ is $\tilde{O}(n/k)$ we need to
slightly adapt the choice of the parameters. Similarly in the general case we
choose $h\approx\sqrt{a}$, see Section 7 for the details. Based on these
ingredients we prove Lemma 2.1, which allows converting an
$O(a)$-approximation to an $O(\sqrt{a})$-approximation. Then at a high-level
we want to repeat it $O(\log{\log{\log{n}}})$ rounds until we get an
$O(1)$-approximation for APSP.

There are additional technical details to make the approach work. In
particular, the approach described above works well if the weighted diameter
of the graph is $\operatorname{poly}(\log{n})$ (note that the number of hops
in the hopset is $O(a\log{d})$ and we want $\log d\in a^{O(1)}$ to use Lemma
2.1. Initially this holds, but we want this to hold also after the
approximation $a$ is improved as long as $a\in\Omega(\log{\log{n}})$,
afterwards we can use a more direct approach to compute the distances in
$O(\log{\log{\log{n}}})$ rounds). To handle this, we show how to break the
problem to computing distances in $O(\log{n})$ related graphs with small
diameter, where intuitively in the $i$’th graph we deal with distances of
roughly $2^{i}$ (note that since we have an approximation for APSP, nodes can
know locally in which graph the distance between $u$ and $v$ should be
computed). For details see Section 7.

##  3 Preliminaries

###  3.1 Definitions and Notation

#### Model of distributed computing.

In the Congested Clique model, we have a _fully-connected_ communication
network of $n$ nodes, where nodes communicate by sending $O(\log{n})$-bit
messages to each other node in synchronous rounds. Given an input graph $G$ on
$n$ nodes, initially each node of the Congested Clique knows its own input,
i.e., the edges adjacent to it in $G$ and their weights, and at the end of the
algorithm it should know its output. For example, when computing shortest
paths, a node $v$ should know its distances from other nodes. As standard, we
assume that the weights are polynomially bounded nonnegative integers.

Throughout the paper, for a graph $G=(V,E)$, we write $n=|V|$, $m=|E|$, For
$u,v\in V$, we write $d_{G}(u,v)$ to be the shortest distance between $u$ and
$v$, using the edges in the graph $G$. The subscript $G$ may be omitted when
convenient. Unless otherwise stated, we assume that the graph $G$ under
consideration is _simple_.

For a node $v\in V$ and integer $k\in\mathbb{Z}^{+}$, we write $N_{k}(v)$ to
be a set of the $k$ nodes closest to $v$, breaking ties by taking the nodes
with smaller IDs.

#### Spanners.

A $k$-spanner is subgraph $G^{\prime}$ of $G$ such that for any pair of nodes
$u$ and $v$, we have $d_{G^{\prime}}(u,v)\leq k\cdot d_{G}(u,v)$. Here, $k$ is
also called the stretch of $G^{\prime}$.

#### Hopsets.

A hopset is a set of edges added to a graph that allow to shortcut paths such
to have a small number of hops. In our case, we will be interested especially
in shortcuting paths to the $k$ closest nodes, and we define a notion of
$k$-nearest hopset. $H$ is called a $k$-nearest $\beta$-hopset for a graph
$G=(V,E)$ if:

  * •

$H$ is a graph over the same set of nodes $V$.

  * •

For every pair of nodes $u$ and $v$ then $d_{G}(u,v)=d_{G\cup H}(u,v)$ i.e.
distances are preserved.

  * •

For all nodes $u\in V$, and for all $v\in N_{k}(u)$ (recall $N_{k}(u)$ is the
set of the $k$ closest nodes to $u$), there exists a path in $H$ using no more
than $\beta$ hops from $u$ to $v$, and with total weight $d_{G}(u,v)$.

#### All pairs shortest path (APSP) problem.

In the APSP Problem, initially all nodes only know their incident edges. The
goal is for every node $u$ to know the shortest distance $d_{G}(u,v)$ to every
other $v$ after the conclusion of all rounds. In the approximate version, we
relax the requirement to knowing $\delta(u,v)$ instead of $d_{G}(u,v)$. An
$\alpha$-approximation is one which $\delta(u,v)$ satisfies
$d_{G}(u,v)\leq\delta(u,v)\leq\alpha\cdot d_{G}(u,v)$ for all pairs $u$ and
$v$. We call $\tilde{N}_{k}(v)$ an $a$-approximate $k$-nearest set of $v$ if
there exist some $\delta$ that is an $a$-approximation to APSP, such that
$\tilde{N}_{k}(v)$ is a set of $k$ nodes $u$ with smallest values of
$\delta(v,u)$, breaking ties by IDs.

#### Matrix exponentiation.

The relationship between the APSP problem and the matrix multiplication
problem in a tropical semiring is well-known — specifically, exponentiation.

Let $R=(\mathbb{Z}_{\geq 0}\cup\\{\infty\\},\oplus,\odot)$ be the tropical (or
min-plus) semiring, with elements being the nonnegative integers, the addition
operation $\oplus$ in the ring $R$ is defined by $x\oplus y=\min(x,y)$, and
the multiplication $\odot$ is the usual addition of the integers by $x\odot
y=x+y$.

For two matrices $A$ and $B$ of elements of $R$, define the distance product
$A\star B$ to be the matrix multiplication over the tropical semiring, that
is,

$(A\star B)[i,j]=\min_{k}(A[i,k]+B[k,j]).$

Then, if $A$ is the weighted adjacency matrix of the graph $G$ where
$A[i,i]=0$ for all $i$, then $A^{h}$ consist of the values of the APSP
distances of the graph $G$ using paths of at most $h$ hops. If we take $h$ to
be at least the maximum number of hops in any shortest path we get APSP.

###  3.2 Handling Zero Edge Weights

Throughout the rest of the paper, we assume that all edge weights are positive
integers. However, the algorithm can be updated to handle the case where edge
weights can be zero, using the following black-box reduction.

######  Theorem 3.1.

If there exists an algorithm $A$ that computes $a$-approximation of APSP for
undirected weighted graphs with _positive_ integer edge weights in $f(n)$
rounds in the Congested Clique model, then we can extend the algorithm $A$ to
compute $a$-approximation of APSP for undirected weighted graphs with
_nonnegative_ integer edge weights in $f(n)+O(1)$ rounds in the Congested
Clique model.

Furthermore, if the algorithm $A$ is deterministic, then the resulting
extended algorithm is also deterministic.

The main idea is: given a graph $G$, we find the clusters of nodes whose
distance from each other is $0$, compress each cluster into a single node, run
the algorithm $A$ on the compressed graph, then use the result to compute the
$a$-approximation on $G$. For details see Appendix A.

###  3.3 Useful Tools

We use the following routing algorithms. First, we use Lenzen’s routing
algorithm [12].

######  Lemma 3.1 (name=[12]).

There is a deterministic algorithm that delivers all the messages to the
destinations within $O(1)$ rounds, where each node has $O(n)$ messages, each
message consists of $O(\log n)$ bits of content, and each node is the target
of $O(n)$ messages.

The following lemma from [3] generalizes Lenzen’s routing algorithm to relax
the condition that each node can only send $O(n)$ messages, as long as each
node only receives $O(n)$ messages, and some technical conditions are
satisfied.

######  Lemma 3.2 (Corollary 7 in [3]).

In the deterministic Congested Clique model, given each node starts with
$O(n\log n)$ bits of input, and at most $O(1)$ rounds have passed since the
start of the algorithm, any routing instance where each node is the target of
$O(n)$ messages can be performed in $O(1)$ rounds.

Intuitively speaking, if there is a high amount of “duplication” or
“redundancy” in the messages being sent by each node, then it can be
effectively transmitted.

For instance, if a node wants to broadcast a $O(n\log n)$-bit message to all
the remaining nodes, the total amount of data that that node need to send is
$O(n^{2}\log n)$ bits; however it can be computed from $O(n\log n)$ bits,
which allows us to apply this lemma to perform the routing instance in $O(1)$
rounds.

##  4 Approximation to Hopset

In this section, we discuss Lemma 2.2 in more detail. We recall the statement
below. *

#### Intuition for the proof.

We note that, informally, our goal is the following: use an $a$-approximation
for APSP to add “shortcut” edges such that for every $u$, the closest
$\sqrt{n}$ nodes to $u$ can be reached in a small number of hops.
Our algorithm works as follows. For a particular node $u$, we look at its
approximately closest $\sqrt{n}$ nodes and make $u$ aware of a total of $O(n)$
approximate distances involving that nearest set. Then $u$ recomputes
distances with that additional knowledge and adds shortcut edges. We show that
with this knowledge $u$ can compute exact distances to a substantial part of
its $\sqrt{n}$-closest nodes, thus creating useful shortcuts.

More concretely, we start by proving that for any node $v$ in $u$’s
$\sqrt{n}$-nearest, we can use a shortcut edge and then another edge to cover
at least $\frac{1}{a}$ fraction of the distance to $v$. Next we prove that we
can use 2 other edges to cover $\frac{1}{a}$ fraction of the remaining
distance, and so on. We use this to prove that after $O(a\log{d})$ hops we
reach $v$.

###  4.1 Algorithm Description

Let $\delta$ be the given $a$-approximation of APSP, such that for all $u,v$
we have $d(u,v)\leq\delta(u,v)\leq a\cdot d(u,v).$ Our algorithm does the
following:

  1. 1.

Each node $u$ computes a set $\tilde{N}_{\sqrt{n}}(u)$ to be the set of
$\sqrt{n}$ nodes $v$ with smallest values of $\delta(u,v)$, breaking ties by
IDs.

  2. 2.

Node $u$ asks each $v\in\tilde{N}_{\sqrt{n}}(v)$ for the $\sqrt{n}$ shortest
edges adjacent to $v$.

  3. 3.

Node $u$ runs a shortest-path algorithm using all the edges it received, as
well as all the edges adjacent to $u$ in the input graph $G$.

  4. 4.

Let $d^{\prime}(u,v)$ be the shortest distance from $u$ to $v$, computed by
node $u$ in the step above.

  5. 5.

Each node $u$ adds an edge $(u,v)$ with weight $d^{\prime}(u,v)$ to the
hopset.

######  Claim 4.1.

The above algorithm can be implemented in $O(1)$ rounds of Congested Clique.

###### Proof.

Note that the only part that requires communication is Step 2. Clearly, every
node is a target of $O(n)$ messages and only $O(1)$ rounds have passed. Thus,
we can apply Lemma 3.2 and we are done. ∎

###  4.2 Correctness

For each $v\in V$ and $d>0$ define:

  * •

$B_{d}(v)$ to be the closed ball of radius $d$ around $v$ (that is ${u\in
V:d(u,v)\leq d}$).

  * •

$l(v)$ to be the smallest integer $l$ such that $|B_{l}(v)|\geq\sqrt{n}$.
Equivalently:

$l(v)=\max_{v\in N_{\sqrt{n}}(v)}d(u,v).$

Note that by the definition of $l(v)$, for any $l^{\prime}<l(v)$, we have
$|B_{l^{\prime}}(v)|<\sqrt{n}.$ Our first goal is to show that each node $v$
computed the exact distance to each $u$ such that $d(v,u)\leq(l(v)-1)/a$. To
simplify notation we let $B(v)=B_{(l(v)-1)/a}(v)$. We use the following claim.

######  Claim 4.2.

For all $v$, it holds that $B(v)\subseteq\tilde{N}_{\sqrt{n}}(v).$

###### Proof.

For all $u\in B(v)$, we have that $d(u,v)\leq(l(v)-1)/a$, and hence
$\delta(u,v)\leq l(v)-1$. In addition, by the definition of $l(v)$, there are
less than $\sqrt{n}$ nodes at distance $l(v)-1$ from $v$, which implies that
there are less than $\sqrt{n}$ nodes $u$ with $\delta(u,v)\leq l(v)-1$, as
$d(u,v)\leq\delta(u,v).$ Hence, all nodes $u$ where $d(u,v)\leq(l(v)-1)/a$ are
necessarily in the set $\tilde{N}_{\sqrt{n}}(v).$ ∎

Now, we prove that each node $v$ learns the exact distance to all nodes in a
sufficiently small set.

######  Lemma 4.1.

Recall above that $d^{\prime}(u,v)$ is the shortest distance from $u$ to $v$
computed by node $u$ in the algorithm. Then, $\forall u\in B(v)$,
$d^{\prime}(v,u)=d(v,u)$.

###### Proof.

Indeed, assume otherwise pick the counterexample with the smallest value of
$d(v,u)$.

Then, we have that $u\in B(v)$ and $d^{\prime}(v,u)>d(v,u)$. Let $t$ be the
node adjacent to $u$ on some shortest $u-v$ path, by assumption $t\in B(v)$ so
$d^{\prime}(v,t)=d(v,t)$.

The edge $(t,u)$ that lies on that shortest $u-v$ path must not have been sent
to $v$ during the execution of the algorithm.

From Claim 4.2, $t\in\tilde{N}_{\sqrt{n}}(v)$, hence $t$ must have sent to $v$
some shortest $\sqrt{n}$ edges adjacent to $t$. Let
$u_{1},u_{2},\ldots,u_{\sqrt{n}}$ be the other endpoints of these nodes. Then
$d(t,u_{i})\leq d(t,u)$.

So $d(v,u_{i})\leq d(v,u)\Longrightarrow u_{i}\in B(v)$, but this means that
$B(v)$ contains all of $u_{i}$ and also $u$, which means that
$|B(v)|>\sqrt{n}$, contradicting the fact that $|B(v)|<\sqrt{n}$, as by
definition $B(v)=B_{l^{\prime}}(v)$ for $l^{\prime}<l(v)$. ∎

Our next goal is to prove that there is a low-hop path from each node $v$ to
$\sqrt{n}$ closest nodes. Our proof exploits the following property of $l(v)$.

######  Claim 4.3.

For two nodes $u$ and $v$, it holds that $|l(v)-l(u)|\leq d(u,v)$.

###### Proof.

Assume without loss of generality that $l(v)\geq l(u)$, and assume to the
contrary that $l(u)+d(u,v)<l(v)$ then on one hand
$|B_{l(u)+d(u,v)}(v)|<\sqrt{n}$ as $l(u)+d(u,v)<l(v)$. On the other hand,
$|B_{l(u)+d(u,v)}(v)|\geq\sqrt{n}$, as at distance $l(u)+d(u,v)$ from $v$ we
have all nodes in the set $B_{l(u)}(u)$ that has at least $\sqrt{n}$ nodes, a
contradiction. ∎

Finally, we prove that $H$ is indeed a $\sqrt{n}$-nearest
$O(a\log{d})$-hopset. We prove something stronger, that there is an $O(a\log
d)$-hop path between $u$ and $v$ for any $u\in B_{l(v)}(v)$. Since there are
at least $\sqrt{n}$ nodes at distance $l(v)$ from $v$, this in particular
implies that there is an $O(a\log d)$-hop path between $v$ and its
$\sqrt{n}$-nearest nodes.

######  Lemma 4.2.

Let $v\in V$, and $u\in B_{l(v)}(v)$. Then there is an $O(a\log d)$-hop path
between $u$ and $v$ in $G\cup H$, with length $d(u,v)$.

###### Proof.

Fix a shortest path $v=s_{1}s_{2}\cdots\rightarrow s_{k}=u$, where $u\in
B_{l(v)}(v)$.

Let $t_{0}=s_{1}$. For each $i\in\mathbb{Z}^{+}$ let $t_{i}$ to be the
smallest-index next node on the path that does not belong to $B(t_{i-1})$. We
terminate when $u\in B(t_{i})$, see Figure 1 for illustration. Then there is a
2-hop path in $G\cup H$ between $t_{i-1}$ and $t_{i}$ of weight
$d(t_{i-1},t_{i})$.

$t_{0}$$v=$$t_{1}$$t_{2}$$t_{3}$$t_{4}$$=u$

Figure 1: Illustration of the selection of $t_{i}$.

By induction on increasing $i$, the following can be proven:

  * •

$l(s_{i})\geq d(s_{i},u)$. For $s_{1}=v$ this clearly holds, as $u\in
B_{l(v)}(v)$. For a general $i$, if $l(s_{i})\geq l(s_{1})$, then it follows
from the base case, so the interesting case is that $l(s_{i})\leq l(s_{1})$.
Here, using Claim 4.3 we have $l(s_{i})\geq l(s_{1})-d(s_{i},s_{1})\geq
d(s_{1},u)-d(s_{1},s_{i})=d(s_{i},u).$

  * •

$t_{i+1}\notin B(t_{i})=B_{\frac{l(t_{i})-1}{a}}(t_{i})$, which also imply
$d(t_{i+1},u)\leq d(t_{i},u)-\frac{l(t_{i})}{a}\leq
d(t_{i},u)-\frac{d(t_{i},u)}{a}=(1-\frac{1}{a})\cdot d(t_{i},u)$.

So, as $(1-\frac{1}{a})^{a\lceil\log d\rceil}<(\frac{1}{e})^{\lceil\log
d\rceil}\leq\frac{1}{d}$, so we have $d(t_{a\lceil\log
d\rceil},u)<\frac{1}{d}d(v,u)\leq 1$ (if the sequence continues that long), so
it must be $0$, which means the sequence $t$ has $a\lceil\log d\rceil$
elements (excluding $t_{0}$). Since for each $i$, $t_{i}$ and $t_{i+1}$ can be
reached within $2$ hops using the hopset $H$, we obtain an $O(a\log{d})$-hop
path between $v$ and $u$ in $G\cup H$, as needed. ∎

##  5 Fast Computation of the $k$-Nearest Nodes

In Section 4 we showed that we can construct a hopset such that for each node
its closest $k$ nodes are at hop-distance $O(a\log{d})$. As we assume that the
weights are polynomial, and we can obtain an $a\in O(\log{n})$-approximation
in $O(1)$ rounds, this gives paths with $O(\log^{2}{n})$ edges. Our next goal
is to use this hopset to compute the distances to the $k$ closest nodes.
Naively it may require $\Omega(\log^{2}{n})$ rounds as the number of edges in
the paths is $O(\log^{2}{n})$, but one can use fast matrix exponentiation to
solve it in $O(\log{(\log^{2}{n})})\subseteq O(\log{\log{n}})$ rounds,
following the approach in [2]. Here, the high-level idea is to learn at round
$i$ the $k$-closest nodes of hop-distance at most $2^{i}$. However, this is
still too expensive for our needs. To obtain a faster algorithm, we identify
in this section situations in which the $k$ closest nodes can be computed in
just $O(1)$ rounds. In particular we show that we can compute the $k\in
O(n^{1/h})$ closest nodes of hop distance $h$ in just $O(1)$ rounds. Repeating
the algorithm $O(1)$ times gives the following.

*

We start by proving the following.

######  Lemma 5.1.

Given a graph $G$ with positive integer weights and an integer $h$, if $k\in
O(n^{1/h})$, then we can deterministically compute for each node the $k$ nodes
closest to it of hop distance at most $h$ in $O(1)$ rounds.

This problem can be phrased as a special case of _filtered matrix
multiplication_. Here, we are given a matrix $A$ that represents the graph,
and our goal is to compute for each node $u$, the $k$ smallest elements in the
row of $u$ in the matrix $A^{h}$, where $A^{h}_{u,v}$ has the distance of the
shortest path between $u$ and $v$ using paths of at most $h$ hops. To get an
efficient algorithm we start by filtering the matrix $A$ to a matrix
$\overline{A}$ that only has the $k$ smallest elements in each row, and
compute a filtered version of the matrix $({\overline{A}})^{h}$. Filtered
matrix multiplication was also used before to find the $k$-nearest nodes in
[2; 9]. The main difference in our approach is that previous algorithms showed
how to compute filtered matrix multiplication of 2 matrices in $O(1)$ rounds
(if $k\leq\sqrt{n}$),777They also showed an algorithm that works if $k\leq
n^{2/3}$, but it comes at a cost of an additional $O(\log{n})$ term in the
round complexity. and then to use this to compute the $k$-nearest nodes of hop
distance $h$ one needs to repeat the algorithm $\log{h}$ times, where here we
show that $h$ matrices can be multiplied in $O(1)$ rounds if $k\leq n^{1/h}$.
We later show that repeating Lemma 5.1 $i$ times gives the following.

######  Lemma 5.2.

Given a graph $G$ with positive integer weights and an integer $h$, if $k\in
O(n^{1/h})$, then we can deterministically compute for each node the $k$ nodes
closest to it of hop distance at most $h^{i}$ in $O(i)$ rounds.

###  5.1 Overview and Comparison with Existing Algorithms

Our approach is inspired by previous algorithms for collection of
neighborhoods [6] or path listing [3], that worked for sparse graphs. More
concretely, the algorithm in [6] is for the case of low-degree graphs, where
the algorithm in [3] is for graphs that do not have small cycles. In our case,
the input graph is not necessarily sparse, and we cannot collect entire
neighborhoods around nodes as was done in the previous algorithms, but we
exploit the fact that we are only interested in a sparse part of the output
(the $k$ closest nodes) in order to get an efficient algorithm.

Essentially, our algorithm is a de-randomization of the neighborhood
collection algorithm in [6], using the idea in [3]. Comparing to the
neighborhood collection algorithm in [6]:

  * •

Our algorithm is deterministic. The improvement is done by using the bin-
splitting idea in theorem 8 in [3].

  * •

We use a more careful selection of edges to send, and a tighter analysis in
order to handle the case where not all nodes are low-degree.

Comparing to the path listing algorithm in theorem 8 in [3] which lists all
paths of length $O(k)$ if the number of edges in the graph is $\leq
n^{1+1/k}$, the first phase of our algorithm is identical, however in our
algorithm, we also need the endpoint to learn about the length of the path;
which means we need to send back the information about the path to the node at
the start of that path — specifically, for each $h$-hop path $p$ from $u$ to
$v$ with length $d_{p}$, we need node $u$ to know $(v,\min_{p}d_{p})$.

In the situation in the mentioned paper, it is guaranteed that each node is
only the start of $O(n)$ such paths $p$, which means all the communication
only require each node to receive $O(n)$ messages $(v,d_{p})$, which allows a
direct application of Lemma 3.2; however, for our use case, this condition is
no longer guaranteed. We need an additional idea — the main insight is to sort
the edge list in a particular order; we describe the algorithm below.

###  5.2 Algorithm Description

Here we describe the algorithm to prove Lemma 5.1.

  1. 1.

First, each node $v$ computes a list $M_{(v)}$ of the outgoing edges
consisting of a list of pairs $(v,u,w_{uv})$, where $u$ is the target node and
$w_{uv}$ is the weight of the edge.

  2. 2.

For each node, only $k$ smallest outgoing edges need to be kept. In other
words, filter $M_{(v)}$ to make its size $\leq k$. We will prove that this is
sufficient for each node to reach the $k$ nodes closest to it.

  3. 3.

Then, let $M$ be the list of all the outgoing edges from all nodes $v$, in
increasing $v$ order — i.e. it is the concatenation of all the outgoing edge
lists computed above, $M=M_{(1)}+M_{(2)}+\cdots+M_{(n)}$. Therefore, this list
consists of $nk\in O(n\cdot n^{1/h})$ edges.

We choose $p=\lfloor n^{1/h}\cdot\frac{h}{4}\rfloor$. Divide $M$ into $p$
contiguous sublists (bins), each of $O(n/h)$ edges. Let the bins be
$C_{1},\ldots,C_{p}$.

We consider all $h$-combinations $C_{i_{1}},C_{i_{2}},\ldots,C_{i_{h}}$ of
distinct bins, where _the ordering of the elements
$C_{i_{2}},\ldots,C_{i_{h}}$ does not matter_. We will show there are $\leq n$
combinations in total.

  4. 4.

Assign each combination to a node, and make each node learn all the edges in
its bin.

  5. 5.

For each node $u$, it finds all the nodes $v$ where the bin $C_{i_{1}}$
assigned to $v$ contains at least one edge from $M_{(u)}$ — that is, an
outgoing edge from $u$. Then, for each such node $v$, it asks for $k$ nodes
closest to $u$ computed using the edges received by $v$ using paths of at most
$h$ edges, as well as the distances to those nodes.

###  5.3 Complexity

######  Lemma 5.3.

The algorithm above takes $O(1)$ rounds.

We give the high-level idea of the proof. First, the values of $p$ and $h$
computed in step 3 can be broadcasted to all nodes. Because of the selection
of $p$, we have the number of combinations $h\cdot\binom{p}{h}$ is $\leq n$ —
intuitively, $h$ is small compared to $k$ or $p$, so the selection of
$p\approx n^{1/h}$ makes $\binom{p}{h}<p^{h}\approx n$. Therefore, it is
indeed possible to assign a node to handle at most one combination.

Then, in step 4, some deterministic algorithm can be used to compute how the
assignment of each combination to a node. After that, since each node needs to
learn $O(n)$ words of information, we can apply Lemma 3.2 to execute the
routing instance in $O(1)$ rounds.

Similar argument can be used to apply Lemma 3.2 on the routing instance in
step 5 — each node $u$ needs to ask for information from $O(n/p)$ nodes $v$,
and it needs to receive $O(k)$ words from each such node $v$. Since $k\in
O(n^{1/h})$ and $p=\lfloor n^{1/h}\cdot\frac{h}{4}\rfloor$, again, the number
of words received by each node is $O(n)$.

###### Proof of Lemma 5.3.

We will describe how the algorithm can be effectively implemented in the
Congested Clique model.

Implementing step 1 and 2 is trivial.

In step 3,

  * •

The number $p$ and $h$ can be broadcasted to all nodes.

  * •

There are $h\cdot\binom{p}{h}$ combinations in total, this number is $\leq n$
because, $h\cdot\binom{p}{h}\leq h\cdot\big{(}\frac{pe}{h}\big{)}^{h}\leq
h\cdot(n^{1/h}\cdot\frac{e}{4})^{h}=n\cdot h\cdot(\frac{e}{4})^{h}$, and for
all $h\geq 1$ then $h\cdot\big{(}\frac{e}{4}\big{)}^{h}\leq 1$ because,
$\ln\big{(}h\cdot\big{(}\frac{e}{4}\big{)}^{h}\big{)}=\ln h+h\ln\frac{e}{4}$
has derivative $\frac{1}{h}+\ln\frac{e}{4}$, for $h\geq 3$ then the derivative
is negative, thus the function is decreasing on $h\in[3,\infty)$, and it can
be manually checked that $h\cdot\big{(}\frac{e}{4}\big{)}^{h}\leq 1$ for
$1\leq h\leq 3$.

  * •

The list $M$ is not known by any individual node, however, we can make each
node $v$ broadcast the size of $M_{(v)}$. From this value, each node can
compute for each element $M_{j}$ of the list $M$, which node owns the element
and it is at which position — specifically, it can compute from $j$, values
$v$ and $k$ such that $M_{j}$ is the $k$-th element of the list $M_{(v)}$.

  * •

The nodes can use some deterministic algorithm to compute how the combinations
should be assigned to the nodes, thus each node knows the assignment of
combinations to every nodes.

In step 4,

  * •

Consider any node $u$, it wants to learn bins
$C_{i_{1}},C_{i_{2}},\ldots,C_{i_{h}}$.

From the information of the length of all the lists $M_{(v)}$ above, it can
compute that the edges in the bins it wants to learn consist of contiguous
elements from index $l_{uv}$ to index $r_{uv}$ in the list $M_{(v)}$, for each
other node $v$.

Notice that it cannot happen that, the edges the node $u$ wants to learn from
the list $M_{(v)}$ is a non-contiguous sublist, because any gap has the length
at least one bin-width, which is $O(n/h)$, this is much larger than the length
of $M_{(v)}$, which is $\leq k$ by step 2 of the algorithm above.

At this point, node $u$ sends the value of $l_{uv}$ and $r_{uv}$ to node $v$,
then each node knows exactly which edges it needs to send to which node.

Each bin has $O(n\cdot n^{1/h}/p)\subseteq O(n/h)$ edges, each node only has
to learn at most $h$ distinct bins, thus each node need to receive $O(n)$
messages, so Lemma 3.2 can be applied.

In step 5, for each node $u$,

  * •

Let $S$ be the set of all the nodes $v$ where the bin $C_{i_{1}}$ assigned to
$v$ contains at least one edge in $M_{(u)}$.

Recall above that $u$ knows the assignment of combinations to all nodes, as
well as which contiguous sublist of $M$ has edges in $M_{(u)}$, thus it can
compute $S$ locally.

In the end of this step, node $u$ needs to ask for the information on $k$
nodes closest to $u$ from each node $v\in S$.

  * •

Recall that there are $h\cdot\binom{p}{h}\leq n$ combinations in total. By
symmetry, for each $1\leq i\leq p$, there are $\frac{1}{p}$ of all the
combinations $C_{i_{1}},C_{i_{2}},\ldots,C_{i_{h}}$ where $i_{1}=i$. Thus, the
number of such combinations is $\leq n/p$.

Moreover, because of the specific ordering, there can be at most $2$ bins
within $C_{1},C_{2},\ldots,C_{p}$ that contain an outgoing edge from $u$.

As such, $|S|\leq 2n/p\in O(n/p)$.

  * •

Since $k\in O(n^{1/h})$ and $p=\lfloor n^{1/h}\cdot\frac{h}{4}\rfloor$, then
$|S|\cdot k\leq O(n/p)\cdot k\leq O(n)$, so each node can learn all the
relevant information in $O(1)$ rounds.∎

###  5.4 Correctness

To prove Lemma 5.1, our goal is to prove that each node $u$ learns the
distances to the $k$ closest nodes using paths of at most $h$ hops.
Intuitively, the reason is that each such $h$-hop path is known by some node
$v$ that will send the information to $u$. We show that the fact that we
filter the edges to keep only $k$ minimum weight edges adjacent to each node
does not affect paths to the $k$ closest nodes. Lemma 5.2 is obtained by
repeating Lemma 5.1 $i$ times, and Lemma 2.3 is a direct corollary of Lemma
5.2.

We next give the full proof. We should show that by the end of the algorithm
each node knows the distance to $k$ closest nodes of hop distance at most $h$.
Phrasing this as a matrix problem, each node $u$ knows the distance to $k$
nodes, such that these distances correspond to $k$ smallest elements in the
row of $u$ in the matrix $A^{h}$, where $A^{h}_{u,v}$ is the distance between
$u$ and $v$ using paths of at most $h$ hops. We start by proving that $u$
knows the distance to $k$ closest nodes in $({\overline{A}})^{h}$, where
$\overline{A}$ is a matrix that corresponds to the list obtained in Step 2 of
the algorithm that keeps only $k$ smallest elements in each row of $A$,
breaking ties by IDs.

######  Lemma 5.4.

By the end of the algorithm, each node $u$ knows the distance to $k$ closest
nodes according to $({\overline{A}})^{h}$, breaking ties by IDs. That is, it
knows $k$ tuples $(v,(\overline{A})^{h}_{u,v})$ that correspond to the $k$
smallest elements in the row of $u$ in $({\overline{A}})^{h}$, breaking ties
by IDs.

###### Proof.

Consider any path $P$ of at most $h$ edges of $\overline{A}$ such that $P$ is
a path of a minimum cost out of the $h$-hop paths connecting its endpoints. By
the description of the algorithm each edge of the path is in some bin, and any
$h$-combination of bins is given to a node $v$. Hence each such path is known
by some node. Moreover, any path that starts at $u$ is known by a node $v$
such that the first bin $C_{i_{1}}$ assigned to $v$ has an outgoing edge from
$u$. After Step 5 of the algorithm, $u$ learns from each such node $v$ about
the $k$ closest nodes to $u$ known by $v$ using paths of at most $h$ edges.
After this step, if $u$ did not learn the tuple
$(w,({\overline{A}})^{h}_{u,w})$ it means that $u$ learns the $h$-hop distance
to at least $k$ nodes $w^{\prime}$ such that
$({\overline{A}})^{h}_{u,w^{\prime}}\leq({\overline{A}})^{h}_{u,w}$. We show
that $u$ indeed learns the tuple
$(w^{\prime},({\overline{A}})^{h}_{u,w^{\prime}})$ for each of its $k$ closest
nodes (and not a length of a longer path). Let $l_{h}(u)$ be the smallest
value such that there are at least $k$ nodes $w$ where
$({\overline{A}})^{h}_{u,w}\leq l_{h}(u)$. For each node $w$ where
$({\overline{A}})^{h}_{u,w}<l_{h}(u)$, $u$ necessarily learns
$(w,({\overline{A}})^{h}_{u,w})$ because the $h$-hop path of length
$({\overline{A}})^{h}_{u,w}$ is known by a node $v$, and $v$ necessarily sends
the information to $u$ as there are less than $k$ nodes of this distance. If
$({\overline{A}})^{h}_{u,w}=l_{h}(u)$, and $w$ is among the $k$ nodes closest
to $u$ via $h$-hop paths in $\overline{A}$ (breaking ties by IDs) then the
path of length $({\overline{A}})^{h}_{u,w}$ is known by a node $v$, and $v$
must send $(w,({\overline{A}})^{h}_{u,w})$ to $u$. Otherwise, it knows about
at least $k$ nodes that are closer to $u$ or with the same distance and
smaller ID, in contradiction to the definition of $w$. ∎

We next show that learning the $k$ smallest elements according to
$(\overline{A})^{h}$ is equivalent to learning the $k$ smallest elements
according to $A^{h}$.

######  Lemma 5.5.

Let $A$ be matrix representing a weighted graph with positive integer weights.
Let $\overline{A}$ be the matrix obtained from $A$ by keeping only the $k$
smallest entries in each row, breaking ties by IDs (and setting the rest of
entries to $\infty$). Then the $k$ smallest entries in each row of
$(\overline{A})^{i}$ are the $k$ smallest entries in the corresponding row of
$A^{i}$.

###### Proof.

For a node $u$, denote by $N^{i}_{k}(u)$ the set of $k$ closest nodes to $u$
using paths of at most $i$ hops, breaking ties by IDs. We show that for each
$v\in N^{i}_{k}(u)$, the shortest path $P$ using at most $i$ hops between $u$
in $v$ in the original graph (represented by $A$) exists also after we only
keep the $k$ minimum weight edges adjacent to each node, and hence the whole
path exists in the graph represented by $\overline{A}$. For all nodes on the
path $P$, we denote by $d_{P}(u,w)$ the distance between $u$ and $w$ in the
path $P$. Let $w$ be the neighbor of $v$ in $P$. We first prove that the whole
path between $u$ and $w$ is kept. Note that since the weights are positive,
for each node $x$ in this subpath we have $d_{P}(u,x)<d_{P}(u,v)$. Assume to
the contrary that some edges on this path are filtered out, and let $e=(x,y)$
be the first such edge, that is, the edge closest to $u$. Since $(x,y)$ is
filtered out, then $x$ adds $k$ edges to nodes $z$ such that $w(x,z)\leq
w(x,y)$. In particular, for all these nodes, the path from $u$ to $z$ through
$x$ is a path of less than $i$ hops with total weight at most
$d_{P}(u,x)+w(x,y)=d_{P}(u,y)<d_{P}(u,v)$, contradicting the fact that $v$ is
among the $k$ closest nodes to $u$ using paths of at most $i$ hops. Hence, the
whole path between $u$ and $w$ (the neighbor of $v$ on $P$) is preserved.
Similarly, the last edge $(w,v)$ is also preserved, as otherwise $w$ adds
edges to $k$ nodes that are closer than $v$ (breaking ties by IDs), and if
there are $k$ such nodes that do not include $v$, we get a contradiction to
the the fact that $v\in N^{i}_{k}(u)$. Since all such paths are preserved, the
$k$ smallest entries in the row of $u$ in $(\overline{A})^{i}$ (that
correspond to the closest nodes to $u$ using paths of at most $i$ edges in the
graph $\overline{A}$) are exactly the $k$ smallest entries in the row of $u$
in $A^{i}$, completing the proof. ∎

We can now prove Lemma 5.1.

See 5.1

###### Proof.

By Lemma 5.4, we know that by the end of the algorithm each node knows the
distances to the $k$ closest nodes according to the matrix
$({\overline{A}})^{h}$. Hence, by Lemma 5.5, it knows the distances to the $k$
closest nodes according to $A^{h}$, which means that it knows the distances to
the $k$ closest nodes using paths of at most $h$ hops, as needed. The number
of rounds is $O(1)$ by Lemma 5.3. ∎

###  5.5 Repeating the Algorithm

By repeating the algorithm $i$ times, we get the following.

See 5.2

###### Proof.

Let $A$ be the weighted adjacency matrix of $G$. From Lemma 5.1 if we apply
the algorithm once, each node learns the $k$ closest nodes to it according to
$A^{h}$, we denote the resulting matrix by $A_{1}=\overline{A^{h}}.$ We can
now run the algorithm again with the input matrix $A_{1}$, and so on. We prove
that after $i$ iterations each node knows the $k$ closest nodes to it
according to $A^{h^{i}}$, which are exactly the $k$ closest nodes of hop
distance at most $h^{i}$. The proof is by induction. For $i=1$ it holds by
Lemma 5.1. Assume that it holds for $i$ and we prove that it holds for $i+1$.
This means that after $i$ iterations each node knows the closest $k$ nodes
according to $A^{h^{i}}$, denote the resulting (filtered) matrix by
$A_{i}=\overline{A^{h^{i}}}$. We now run the algorithm with respect to
$A_{i}$. By Lemma 5.1 we know that after running the algorithm, each node
knows distances to $k$ closest nodes according to
$(A_{i})^{h}=(\overline{A^{h^{i}}})^{h}$. By Lemma 5.5, this is equivalent to
knowing $k$ closest nodes according to $(A^{h^{i}})^{h}=A^{h^{i+1}}$, as
needed. The number of rounds is $O(i)$, as each iteration takes $O(1)$ rounds.
∎

As a direct corollary of Lemma 5.2, if we have a $k$-nearest hopset that
guarantees low-hop paths from each node to its $k$ closest nodes, we can
compute the exact distances to these nodes using Lemma 5.2.

*

##  6 Skeleton Graph Reduction

After computing distances to the $k$ closest nodes, our goal is to extend it
to approximate distances between all pairs of nodes. Informally, the following
lemma states that once each node knows its approximate $k$-nearest nodes, we
can construct a smaller graph $G_{S}$ of size $\tilde{O}(\frac{n}{k})$, such
that approximating APSP on $G$ reduces to approximating APSP on $G_{S}$. For
technical reasons, during our algorithms sometimes nodes only know the
distances to an approximate set of the $k$-nearest. To handle this, we require
certain conditions on the sets known, which makes the full description of the
lemma a bit more technical.

######  Lemma 6.1 (name=Skeleton Graph, restate=skeleton).

Suppose we are given a graph $G$ and additionally the following guarantees:

  * •

$a\geq 1$ is a real number.

  * •

$k$ is some integer between $1$ and $n$.

  * •

$\delta$ is a symmetric function that takes two nodes $u$ and $v$ as input,
and returns a non-negative integer such that $d(u,v)\leq\delta(u,v)$.

  * •

For each node $u$, a set $\tilde{N}_{k}(u)$ of $k$ nodes is given, such that:

    * –

$u\in\tilde{N}_{k}(u)$;

    * –

for every $v\in\tilde{N}_{k}(u)$ and $t\notin\tilde{N}_{k}(u)$, then
$\delta(u,v)\leq a\cdot d(u,t)$.

This set is to be understood as the $a$-approximate $k$-nearest set.

  * •

For each node $u$, then $u$ knows the value of $\tilde{N}_{k}(u)$.888 Note
that unlike $N_{k}(u)$ which is unambiguously defined (up to tie break),
$\tilde{N}_{k}(u)$ is defined to be the current value of $\tilde{N}_{k}(u)$
held by the nodes. It can be any set that satisfies the conditions listed
above, and such a set is not necessarily unique. Furthermore, for each
$v\in\tilde{N}_{k}(u)$, then node $u$ knows the value of $\delta(u,v)$, and
importantly, $\delta(u,v)\leq a\cdot d(u,v)$.

Intuitively, $\delta$ is a _local_ $a$-approximation of APSP on $G$ — that is,
an $a$-approximation only on the approximate $k$-nearest sets
$\tilde{N}_{k}(u)$.

Then, with high probability, we can construct a graph $G_{S}$ over a subset
$V_{S}\subseteq V$ of $O(\frac{n\log k}{k})$ nodes in $O(1)$ rounds of
Congested Clique, where $G_{S}$ has the following property:

  * •

Given any $l$-approximation of APSP on $G_{S}$, we can then compute a
$7la^{2}$-approximation of APSP on $G$ in $O(1)$ rounds.

Essentially, this lemma allows us to extend a local $a$-approximation $\delta$
on the approximate $k$-nearest sets to a $7la^{2}$-approximation of APSP on
the whole of $G$, losing a multiplicative factor of $7la$ in the
approximation. In the special case that $a=1$, then $\delta(u,v)=d(u,v)$ is
the exact distance between the $2$ nodes. In all applications where this
holds, each node $u$ already knows its exact $k$-nearest set $N_{k}(u)$, so we
will just use $\tilde{N}_{k}(u)=N_{k}(u)$. Most of the time (everywhere in
this paper, except Theorem 7.3), we do have $a=1$ — that is, $\delta=d$ is the
exact shortest distance.

###  6.1 Algorithm Description

We describe the algorithm here.

  1. 1.

First, we construct a hitting set $S$ of $O(\frac{n\log k}{k})$ nodes, such
that for each node $v$, $S\cap\tilde{N}_{k}(v)$ is nonempty. This can be done
in $O(1)$ rounds with high probability.

We call the nodes in $S$ the _skeleton_ nodes.

  2. 2.

For each node $u$, let $c(u)$ be a skeleton node such that
$c(u)\in\tilde{N}_{k}(u)$, and $\delta(u,c(u))$ is the smallest, with ties
broken by IDs.

  3. 3.

Then, we construct the graph $G_{S}$, whose nodes are exactly those in the set
$S$, and edges are constructed in a specific way as described in the following
line.

  4. 4.

For any nodes $u,v,t$, such that $t\in\tilde{N}_{k}(u)$ and there is a direct
edge between $t$ and $v$ with weight $w_{tv}$, then add an edge to the graph
$G_{S}$ connecting $c(u)$ and $c(v)$ with length
$\delta(u,c(u))+\delta(u,t)+w_{tv}+\delta(v,c(v))$.

  5. 5.

The above describes the construction of $G_{S}$.

Now, assume $\delta_{G_{S}}$ which is a $l$-approximation of APSP on $G_{S}$
has been computed, compute $\eta$ being a $7la^{2}$-approximation of APSP on
$G$ as follows. For each pair $(u,v)$, then:

     * •

If $u\in\tilde{N}_{k}(v)$, set $\eta(u,v)=\delta(u,v)$.

     * •

Symmetrically, if $v\in\tilde{N}_{k}(u)$, set $\eta(u,v)=\delta(v,u)$.

     * •

Otherwise, set
$\eta(u,v)=\delta(u,c(u))+\delta_{G_{S}}(c(u),c(v))+\delta(v,c(v))$.

###  6.2 Complexity

The algorithm above can be performed in $O(1)$ rounds. The main idea is
discussed below.

The selection of $S$ is computed using a randomized algorithm. The main idea
is that each node selects itself into $S$ with probability
$\Theta\big{(}\frac{|S|}{n}\big{)}$, but in order to make sure every node is
near a selected node, we need another step.

The computation of the edges in $G_{S}$ is done using sparse matrix
multiplication — this is very similar to using matrix multiplication to
compute $4$-hop shortest paths $c(u)\rightarrow u\rightarrow t\rightarrow
v\rightarrow c(v)$, but we need to pick the order the matrices are multiplied
carefully to make sure the matrices are sparse enough. Similarly, the
computation of $\eta(u,v)$ in step 5 also uses sparse matrix multiplication,
similar to how $3$-hop shortest paths $c(u)\rightarrow u\rightarrow
v\rightarrow c(v)$ are computed.

The rigorous proof is described below. We use the following sparse matrix
multiplication algorithm.

#### Sparse matrix multiplication algorithm.

For a matrix $M$, define the _density_ of $M$, $\rho_{M}$, to be the average
number of entries on a row different from $\infty$ (the identity of the
$\oplus$ operation).

The following sparse matrix multiplication algorithm is taken from [2], which
proves to be useful because of the relationship between the matrix
multiplication problem over semiring and the shortest path problem.

In the sparse matrix multiplication problem, we are given two matrices $S$ and
$T$ over the min-plus semiring with size $n\times n$, and wish to compute the
product $ST$.

######  Theorem 6.1 (Theorem 8 in [2]).

Sparse matrix multiplication $ST$ over min-plus semiring can be computed
deterministically in

$O\biggl{(}\frac{(\rho_{S}\rho_{T}\rho_{ST})^{1/3}}{n^{2/3}}+1\biggr{)}$

rounds in Congested Clique, assume we know $\rho_{ST}$ beforehand.

Using that, we will prove that the algorithm can be implemented in $O(1)$
rounds.

#### Line 1.

We describe the algorithm to compute the hitting set.

We use the same idea as in the proof of lemma 4.1 in [8]:

  * •

first, each node selects itself into the set $S$ with probability $\frac{\ln
k}{k}$,

  * •

then, each node that does not find any node in $\tilde{N}_{k}(v)$ already in
$S$ so far, selects itself into $S$.

Observe that the probability of a node being selected in step 2 is bounded
above by $(1-\frac{\ln k}{k})^{k}\leq\frac{1}{k}$. Thus, by linearity of
expectation, the expected number of nodes being selected is
$\Theta(\frac{n\log k}{k})$, which means we can make $\mathbb{P}[|S|\in
O(\frac{n\log k}{k})]>\frac{2}{3}$ repeating the algorithm $O(1)$ times, or
$>1-\frac{1}{\operatorname{poly}(n)}$ repeating the algorithm $\Theta(\log n)$
times — the algorithm also only requires $O(1)$ bits of communication along
the edges, which means we can run up to $\Theta(\log n)$ parallel instances.
Finally, note that the second step ensures that $S$ is a hitting set for
$\\{\tilde{N}_{k}(v):v\in V\\}$.

#### Line 4.

Consider two skeleton nodes $s_{a},s_{b}\in S$. While we can have multiple
edges between $s_{a}$ and $s_{b}$, we only care about the minimum weight edge.

Thus, the required edge is the one which minimizes
$\delta(s_{a},u)+\delta(u,t)+w_{tv}+\delta(v,s_{b})$ such that $c(u)=s_{a}$,
$c(v)=s_{b}$, $t$ is in $\tilde{N}_{k}(u)$ and $\\{t,v\\}\in E_{G}$.

For every pair $s_{a}$ and $t$, define
$x(s_{a},t)=\min_{u:c(u)=s_{a}}\delta(s_{a},u)+\delta(u,t)$. Similarly, for
every $s_{b}$ and $t$, define
$y(t,s_{b})=\min_{v:c(v)=s_{b}}w_{tv}+\delta(s_{b},v)$.

We can make the value $x(s_{a},t)$ known to $s_{a}$ and $t$ in $O(1)$ rounds
as follows:

  * •

Every $u$ sends $[c(u),\delta(c(u),u)+\delta(u,t)]$ to all
$t\in\tilde{N}_{k}(u)$.

  * •

For every $s_{a}$, each $t$ finds minimum the second value over all messages
of the form $[s_{a},\ldots]$, thus computing $x(s_{a},t)$.

  * •

Every $t$ sends $x(s_{a},t)$ to $s_{a}$.

We can do the same for $y(t,s_{b})$ as follows:

  * •

Every $v$ sends $[c(v),w_{tv}+\delta(v,c(v))]$ to all its neighbors $t$ in the
original graph.

  * •

For every $s_{b}$, each $t$ finds minimum the second value over all messages
of the form $[s_{b},\ldots]$, thus computing $y(t,s_{b})$.

  * •

Every $t$ sends $y(t,s_{b})$ to $s_{b}$.

Finally, we compute the edge weights in $G_{S}$ as follows:

  * •

Let, $X$ and $Y$ be matrices such that $X_{i,j}=x(i,j)$ and $Y_{i,j}=y(i,j)$
wherever those values are defined and $\infty$ otherwise.

  * •

Notice that for any $s_{a},s_{b}$, the weight of the edge $\\{s_{a},s_{b}\\}$
in $G_{S}$ is defined as $\min_{t\in V}X_{s_{a},t}+Y_{t,s_{b}}$.

  * •

This is simply the matrix multiplication $XY$ over the min-plus semi-ring, so
we can use Theorem 6.1.

  * •

Note that we have $\rho_{X}\leq nk/n=k$. To see this, observe that an entry in
$X$ is non-$\infty$ iff it holds some $x(s_{a},t)$ value. However, every valid
$x(s_{a},t)$ value can be mapped to some $u$ such that $c(u)=s_{a}$ and $t$ is
in $\tilde{N}_{k}(u)$, and this is only possible for $nk$ pairs.

  * •

Similarly, $\rho_{Y}\leq n\cdot|S|/n=|S|\in O(\frac{n\log k}{k})$ because
$y(t,s_{b})$ requires one node to be a skeleton node.

  * •

Finally, using the same argument as above, every row of $XY$ has at most $|S|$
entries that is different from $\infty$, so $\rho_{XY}\in O(\frac{n\log
k}{k})$.

  * •

It can be verified that plugging these values in Theorem 6.1 results in the
entire algorithm taking $O(1)$ rounds. Note that since we are just interested
in distances between nodes in $S$, the structure of the output matrix is
known.

#### Line 5.

We need to show that we can compute all the values $\eta(u,v)$ efficiently,
where

$\eta(u,v)=\delta(u,c(u))+\delta_{G_{S}}(c(u),c(v))+\delta(c(v),v).$

  * •

Define matrix $A$ such that $A_{c(u),u}=\delta(c(u),u)$ and $\infty$
otherwise. Note that $\rho_{A}=1$ as there are only $n$ non-$\infty$ values.

  * •

Also, represent the approximation on $G_{S}$ using a matrix $D$ such that
$D_{s_{a},s_{b}}=\delta_{G_{S}}(s_{a},s_{b})$ and $\infty$ otherwise.

  * •

Observe that computing the required approximation $\eta$ is equivalent to the
matrix multiplication $A^{T}DA$.

  * •

Since the density of $A$ and $A^{T}$ is $1$, from Theorem 6.1, any
multiplication involving them takes $O(1)$ rounds.

  * •

Thus, we can first compute $B=DA$ and then compute $A^{T}B$ to obtain $\eta$
in $O(1)$ rounds.

###  6.3 Correctness

Consider any pair of nodes $u$ and $v$ in $G$. We need to show $\eta(u,v)\leq
7la^{2}d(u,v)$. If $v\in\tilde{N}_{k}(u)$, then $\eta(u,v)=\delta(u,v)\leq
a\cdot d(u,v)$, we are done. Similarly, if $u\in\tilde{N}_{k}(v)$, we are
done. Thus, we will assume that $v\notin\tilde{N}_{k}(u)$ and
$u\notin\tilde{N}_{k}(v)$.

#### Decomposition into segments.

Let $u=v_{0}v_{1}\cdots\rightarrow v_{m}=v$ be some shortest path between $u$
and $v$.

Define nodes $u_{0},t_{0},u_{1},t_{1},\ldots,u_{p},t_{p}$ on the shortest path
from $u$ to $v$ such that:

  * •

$u_{0}=u$.

  * •

$t_{0}$ is the rightmost node on the path (by “rightmost”, we mean assume the
nodes on the path are written $v_{0},\ldots,v_{m}$ from left to right; that
is, the nodes $v_{i}$ with maximum $i$) such that $t_{0}N_{k}(u_{0})$.

  * •

$u_{1}$ is the node immediately to the right of $t_{0}$.

  * •

$t_{1}$ is the rightmost node on the path such that $t_{1}N_{k}(u_{1})$.

  * •

Repeat until some node $t_{p}$ on the sequence is equal to $v$.

An illustration of this construction can be found in Figure 2.

Since $v\notin\tilde{N}_{k}(u)$, we have $p\geq 1$. For brevity, for any
integer $0\leq i\leq p$, we write $s_{i}=c(u_{i})$; and we write $s_{*}=c(v)$.
By construction, it may be the case that $t_{p}=u_{p}=v$, but otherwise all
nodes in the sequence are distinct.

$u_{0}$$u=$$s_{0}$$t_{0}$$u_{1}$$s_{1}$$t_{1}$$u_{2}$$s_{2}$$t_{2}$$s_{*}$$=v$
Figure 2: Illustration of the construction. Red nodes are skeleton nodes.

#### Proving a special case.

Before we present the full proof, let us consider the case when $a=1$ (that
is, if $\delta(u,v)$ is the exact distance between $u$ and $v$). We show that
in this case the distance of the path $u_{0}s_{0}s_{1}\cdots\rightarrow
s_{p}\rightarrow s_{*}\rightarrow v$ is a constant multiple of the shortest
distance $d(u,v)$ (where, between two consecutive skeleton nodes
$s_{i}\rightarrow s_{i+1}$, we use the path $(s_{i}\dashrightarrow
u_{i}\rightarrow t_{i}\rightarrow u_{i+1}\dashrightarrow s_{i+1})$ — the
dashed arrows ($\dashrightarrow$) represent the edges that are outside the
shortest path from $u$ to $v$; and the solid arrows ($\rightarrow$) represent
the edges that are already on the shortest path from $u$ to $v$. ).

We just need to bound the total length of the segments that lie outside the
shortest path from $u$ to $v$. We can bound them as follows:

  * •

The extra distance $u_{i}\dashrightarrow s_{i}$ is no more than
$u_{i}\rightarrow u_{i+1}$ for $i<p$ because $s_{i}\in\tilde{N}_{k}(u_{i})$
and $u_{i+1}\notin\tilde{N}_{k}(u_{i})$, and in the longer path we traverse
this path twice, once in each direction; (this corresponds to Claim 6.3)

  * •

The last segment $u_{p}\dashrightarrow s_{p}$ is no more than the distance
$u_{p}\rightarrow t_{p}\dashrightarrow s_{*}$, by definition of $s_{p}$;

  * •

The segment $t_{p}\dashrightarrow s_{*}$ is no more than the distance
$d(u,v)$.

  * •

The segment $s_{*}\dashrightarrow v$ is exactly the same as
$t_{p}\dashrightarrow s_{*}$, just in the opposite direction, thus have the
same length.

By carefully bounding the inequalities, we can thus prove that the distance of
the path $u_{0}\dashrightarrow s_{0}\dashrightarrow
s_{1}\dashrightarrow\cdots\dashrightarrow s_{p}\dashrightarrow
s_{*}\dashrightarrow v$ is no more than $O(1)\cdot a^{2}$ times $d(u,v)$, thus
$\eta(u,v)\leq O(1)\cdot l\cdot a^{2}d(u,v)$.

#### Proving the general case.

We start by proving inequalities that we will use to bound $\eta(u,v)$.

######  Claim 6.1.

For every valid $i$, there is an edge in $G_{S}$ between $s_{i}$ and $s_{i+1}$
with weight
$\delta(s_{i},u_{i})+\delta(u_{i},t_{i})+d(t_{i},u_{i+1})+\delta(u_{i+1},s_{i+1})$.

###### Proof.

Note that $t_{i}$ and $u_{i+1}$ are adjacent on the shortest path, implying
that $d(t_{i},u_{i+1})$ must be equal to the weight of the edge between them,
$w_{t_{i}u_{i+1}}$. The claim then follows immediately from the construction
of $G_{S}$. ∎

######  Claim 6.2.

We have that
$d_{G_{S}}(s_{p},s_{*})\leq\delta(s_{p},u_{p})+\delta(u_{p},v)+\delta(v,s_{*})$.

###### Proof.

Note that there is an edge from $s_{p}$ to $s_{*}$ in $G_{S}$ with weight
$\delta(s_{p},u_{p})+\delta(u_{p},t_{p})+w_{t_{p}v}+\delta(v,s_{*})$. Since
$t_{p}=v$, we are done. ∎

######  Claim 6.3.

For every valid $i$, we have $\delta(u_{i},s_{i})\leq a\cdot
d(u_{i},u_{i+1})$.

###### Proof.

This holds because, by definition, $s_{i}\in\tilde{N}_{k}(u_{i})$ and
$u_{i+1}\notin\tilde{N}_{k}(u_{i})$. ∎

######  Claim 6.4.

We have $\delta(u_{p},s_{p})\leq a\cdot d(u_{p},s_{*})$.

###### Proof.

Either $s_{*}$ is outside the approximate nearest set $\tilde{N}_{k}(u_{p})$
then as above, or it’s inside the approximate nearest set then
$\delta(u_{p},s_{p})\leq\delta(u_{p},s_{*})$ (because $u_{p}$ chooses $s_{p}$
to be its center), that term is $\leq a\cdot d(u_{p},s_{*})$. ∎

#### Completing the proof.

We are now ready to bound $\eta(u,v)$:

$\displaystyle\eta(u,v)$
$\displaystyle=\delta(u,s_{0})+\delta(v,s_{*})+\delta_{G_{S}}(s_{0},s_{*})$
$\displaystyle\leq
l\cdot(\delta(u,s_{0})+\delta(v,s_{*})+d_{G_{S}}(s_{0},s_{*}))$
$\displaystyle\leq l\cdot\bigg{(}\delta(u,s_{0})+\delta(v,s_{*})$
$\displaystyle\qquad+\sum_{i=0}^{p-1}\mathcolor{red}{d_{G_{S}}(s_{i},s_{i+1})}+\mathcolor{blue}{d_{G_{S}}(s_{p},s_{*})}\bigg{)}\quad$
$\displaystyle\leq l\cdot\bigg{(}\delta(u,s_{0})+\delta(v,s_{*})$
$\displaystyle\qquad+\sum_{i=0}^{p-1}\mathcolor{red}{\delta(u_{i},s_{i})+\delta(u_{i},t_{i})+d(t_{i},u_{i+1})+\delta(u_{i+1},s_{i+1})}$
$\displaystyle\qquad+\mathcolor{blue}{\delta(u_{p},s_{p})+\delta(u_{p},v)+\delta(v,s_{*})}\bigg{)}\quad\text{(from
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\lx@cref{creftype~refnum}{ineq:a1}}
and
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\lx@cref{creftype~refnum}{ineq:a2}})}$
$\displaystyle=l\cdot\bigg{(}\sum_{i=0}^{p-1}2\mathcolor{magenta}{\delta(u_{i},s_{i})}+\delta(u_{i},t_{i})+d(t_{i},u_{i+1})$
$\displaystyle\qquad+2\mathcolor{orange}{\delta(u_{p},s_{p})}+\delta(u_{p},v)+2\delta(v,s_{*})\bigg{)}$
$\displaystyle\leq l\cdot\bigg{(}\sum_{i=0}^{p-1}2\mathcolor{magenta}{a\cdot
d(u_{i},u_{i+1})}+\delta(u_{i},t_{i})+d(t_{i},u_{i+1})$
$\displaystyle\qquad+2\mathcolor{orange}{a\cdot
d(u_{p},s_{*})}+\delta(u_{p},v)+2\delta(v,s_{*})\bigg{)}\quad\text{(from
{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}\lx@cref{creftype~refnum}{ineq:a3}}
and
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\lx@cref{creftype~refnum}{ineq:a4}})}$
$\displaystyle\leq l\cdot\bigg{(}\sum_{i=0}^{p-1}2a\cdot
d(u_{i},u_{i+1})+\mathcolor{darkgreen}{a\cdot
d(u_{i},t_{i})}+d(t_{i},u_{i+1})$ $\displaystyle\qquad+2a\cdot
d(u_{p},s_{*})+\mathcolor{darkgreen}{a\cdot
d(u_{p},v)}+2\mathcolor{darkgreen}{a\cdot
d(v,s_{*})}\bigg{)}\quad\text{({\color[rgb]{0,0.7,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.7,0}assumption
on $\delta$})}$ $\displaystyle\leq
la\cdot\bigg{(}\sum_{i=0}^{p-1}2d(u_{i},u_{i+1})+d(u_{i},t_{i})+d(t_{i},u_{i+1})$
$\displaystyle\qquad+2d(u_{p},s_{*})+d(u_{p},v)+2d(v,s_{*})\bigg{)}\quad\text{($a\geq
1$)}$
$\displaystyle=la\cdot\big{(}3d(u_{0},u_{p})+2d(u_{p},s_{*})+d(u_{p},v)+2d(v,s_{*})\big{)}$
$\displaystyle\leq
la\cdot\big{(}3d(u_{0},u_{p})+2\big{(}d(u_{p},v)+d(v,s_{*})\big{)}+d(u_{p},v)+2d(v,s_{*})\big{)}$
(triangle inequality for $d$)
$\displaystyle=la\cdot\big{(}3d(u,v)+4d(v,s_{*})\big{)}$ $\displaystyle\leq
la\cdot\big{(}3d(u,v)+4\delta(v,s_{*})\big{)}$ $\displaystyle\leq
la\cdot\big{(}3d(u,v)+4a\cdot d(v,u)\big{)}$ $\displaystyle=la(3+4a)\cdot
d(u,v)$ $\displaystyle\leq 7la^{2}d(u,v).$

##  7 The Main Algorithm

Our main theorem is the following.

######  Theorem 7.1 (name=Approximation of APSP,restate=main).

For every constant $\varepsilon>0$, there is a randomized
$(7^{4}+\varepsilon)$-approximation algorithm for weighted undirected APSP
that takes $O(\log\log\log n)$ rounds in the Congested Clique model.

If we restrict the algorithm to $O(t)$ rounds, we get the following.

######  Theorem 7.2 (restate=[name=]truncatedalgorithm).

There is a randomized $O(\log^{2^{-t}}n)$-approximation algorithm for weighted
undirected APSP in the Congested Clique model that takes $O(t)$ rounds, where
$t\geq 1$ is provided as a parameter.

We will prove this in Section 7.7, the argument is very similar to the proof
of Theorem 7.1, with only minor modifications.

###  7.1 Preliminaries

#### Strengthening the Congested Clique model.

In the Congested Clique model there are $n$ nodes and within each round each
node can send to each other node a message of $\Theta(\log n)$ bits. For our
proofs, it is convenient to consider a variant of the model where the
bandwidth between each pair of nodes is larger — specifically, within each
round, each node can send to each other node a message of $\Theta(\log^{c}n)$
bits.

For brevity, we call the variant defined above the _strengthened Congested
Clique model with bandwidth $\log^{c}n$ bits_. In our applications, $c$ is a
small integer constant, such as $3$ or $4$.

The input and output characteristic of this extended model is the same as the
Congested Clique model — if an undirected graph $G$ of $n$ nodes is given as
input, each node $v$ knows all the edges adjacent to $v$ and their weights;
and if a symmetric distance approximation $\delta(u,v)$ is computed as output,
each node $v$ knows the values of $\delta(v,u)$ for every node $u$.

Note that in this setting we can broadcast $O(n\log^{c-1}n)$ messages to all
nodes in $O(1)$ rounds (instead of $O(n)$). We use this variant only to
simplify the proofs, where our end-results are for the Congested Clique model.

#### Constant-round distance approximation computation.

Recall that A $k$-spanner is subgraph $G^{\prime}$ of $G$ such that for any
pair of nodes $u$ and $v$, we have $d_{G^{\prime}}(u,v)\leq k\cdot
d_{G}(u,v)$. Here, $k$ is also called the stretch of $G^{\prime}$. We use the
following algorithm from [6] to compute spanners. Among other uses, it is used
to compute an $O(\log n)$-spanner that uses $O(n)$ edges, which is helpful to
bootstrap our algorithm.

######  Lemma 7.1 (Theorem 1.2 in [6]).

For any constant $\varepsilon>0$, there is a randomized constant-round
Congested Clique algorithm that computes $(1+\varepsilon)(2k-1)$-spanner with
$O(\frac{\log 1/\varepsilon}{\varepsilon}\cdot n^{1+1/k})$ edges with high
probability in weighted undirected graphs.

From the spanner-computation algorithm in Lemma 7.1, we have the following
corollaries, which are used to compute approximations to the shortest
distance. In our algorithms we sometimes compute APSP on a smaller skeleton
graph $G_{S}$ over $O(n^{1-1/b})$ nodes, such that the nodes of $G_{S}$ know
their adjacent edges.

######  Corollary 7.1.

Let $G$ be our input graph with $n$ nodes, and $G_{S}$ be a weighted graph
over a subset of $N\in O(n^{1-1/b})$ nodes such that each node in $G_{S}$
knows its adjacent edges in $G_{S}$. For any constant $\varepsilon>0$ and
$b\geq 1$, there is a randomized constant-round Congested Clique algorithm
that computes a $(1+\varepsilon)(2b-1)$-approximation to APSP on $G_{S}$ with
high probability. The approximation is known to all nodes of $G$.

###### Proof.

We can use Lemma 7.1 to compute a $(1+\varepsilon)(2b-1)$-spanner of size
$O(N^{1+1/b})\subseteq O(n)$ for the graph $G_{S}$. Since the spanner has
$O(n)$ edges, we can broadcast it to all nodes of $G$ in $O(1)$ rounds, which
results in $(1+\varepsilon)(2b-1)$-approximation to all distances in $G_{S}$.
∎

In particular, in the special case that $G_{S}=G$, we can get an
$O(\log{n})$-approximation. More precisely, we can set the paremters as
follows. For any constant $\alpha>0$, setting $b=\frac{\alpha\log n}{3}$ and
$\varepsilon=0.1$, so that the approximation factor is
$(1+\varepsilon)(2b-1)\leq\alpha\log n$ for large enough $n$, and
$n^{1-1/b}\in\Theta(n)$. We get:

######  Corollary 7.2.

For any constant $\alpha>0$, there is a randomized constant-round Congested
Clique algorithm that computes an $(\alpha\log n)$-approximation to APSP with
high probability on weighted graphs with $O(n)$ nodes. The approximation is
known to all nodes.

###  7.2 Approximation Factor Reduction

We are now ready to restate and prove Lemma 2.1.

*

We give here the high-level idea. We work as follows.

  1. 1.

First, we use Lemma 2.2 to get a $\sqrt{n}$-nearest $O(a\log d)$-hopset $H$.

  2. 2.

Next, we want to use Lemma 5.2 to let each node learn the distances to the $k$
closest nodes, for an appropriate choice of $k$. We select $h=\frac{1}{2}\cdot
a^{1/4}$ and $k=n^{1/h}=n^{2a^{-1/4}}$. With these parameters, we can apply
Lemma 5.2, and get for each node the distances to the $k=n^{2a^{-1/4}}$ nodes
closest to it.

  3. 3.

Now we apply Lemma 6.1 and construct a skeleton graph $G_{S}$ over a set
$V_{S}\subseteq V$ of $O(\frac{n\log k}{k})$ nodes, such that approximation of
the distances in $G_{S}$ leads to approximate APSP in $G$.

  4. 4.

We exploit the smaller size of $G_{S}$ to prove that we can get an
$O(\sqrt{a})$-approximation for $G_{S}$ (by computing an $O(\sqrt{a})$-spanner
of size $O(n)$ for $G_{S}$ and broadcasting it to the graph), which leads to
an $O(\sqrt{a})$-approximation for APSP in $G$.

We next provide the full proof.

###### Proof of Lemma 2.1.

We assume $n$ is large enough such that $\log(2\log n)\leq\sqrt{\log n}$ and
$a\leq\log^{2}n$ — this is only useful for the technical analysis below.

We want to apply the four lemmas sequentially, as briefly described in Section
2.

Recall that we start from a $(16a)$-approximation of APSP. Then, we do the
following.

  * •

Use Lemma 2.2, with the parameter $a=16a$, to get a $\sqrt{n}$-nearest
$O(a\log d)$-hopset $H$.

At this step, we have no choice but to set the parameter $a$ to be the given
approximation factor. As the result, the final hopset $H$ is a $O(a\log
d)$-hopset.

Let $\hat{h}\in O(a\log d)$ be the number of hops. Because $d\in a^{O(1)}$,
then $\hat{h}\in a^{O(1)}$.

  * •

Now, note that if $H$ is a $\sqrt{n}$-nearest $\hat{h}$-hopset, then it is
also a $k$-nearest $\hat{h}$-hopset for any $k\leq\sqrt{n}$. We wish to set
$k$ such that we can apply Lemma 5.2.

In order to do that, we need to find $h$ such that $\hat{h}\leq h^{i}$, and
$k\in O(n^{1/h})$. Because we want to take only $O(1)$ rounds, we must have
$i\in O(1)$.

As shown above, $\hat{h}\in a^{O(1)}$, thus any selection of $h$ such that
$h\in a^{\Omega(1)}$ would allow us to choose $i\in O(1)$. Let us select
$h=\frac{1}{2}\cdot a^{1/4}$ (the selection of the constant $1/4$ may appear
to be arbitrary at the moment, but in the later steps we will see that it
suffices for our purposes), and $k=n^{1/h}=n^{2a^{-1/4}}$.

With these parameters, we can indeed apply Lemma 5.2 (letting the graph with
the hopset $H$ be the input graph for the lemma). As a result, we get, for
each node, the distances to the $k=n^{2a^{-1/4}}$ nodes closest to it.

  * •

Next, we use Lemma 6.1. Once again, the selection of parameters is forced on
us: from the previous step, each node knows the _exact_ distance to the
$k=n^{2a^{-1/4}}$ nodes closest to it. Thus the parameters are $a=1$ and
$k=k$, so $\delta=d$ is the exact shortest distance.

As a result, we can construct a skeleton graph $G_{S}$ over a set
$V_{S}\subseteq V$ of $O(\frac{n\log k}{k})$ nodes, such that approximation of
the distances in $G_{S}$ leads to approximate APSP in $G$.

  * •

Finally, Corollary 7.1 is used. The selection of the constant $b$ is once
again fixed, because the number of nodes of the graph $G_{S}$ is
$O(\frac{n\log k}{k})$ and we have to select $b$ such that $O(\frac{n\log
k}{k})\leq O(n^{1-1/b})$. We will later prove that selecting $b=\sqrt{a}$
works.

As a result, we get a $(1+\varepsilon)(2b-1)$-approximation to APSP on the
graph $G_{S}$.

  * •

In the end, using the conclusion of Lemma 6.1, from the computed approximation
to APSP above, we can get a $7(1+\varepsilon)(2b-1)$-approximation to APSP on
the original graph $G$.

Selecting $\varepsilon=1/7$, we have $7(1+\varepsilon)(2b-1)<16b=16\sqrt{a}$.

The only remaining thing we need to prove is that selecting $b=\sqrt{a}$ works
to ensure that $O(\frac{n\log k}{k})\leq O(n^{1-1/b})$, for $k=n^{2a^{-1/4}}$.

Intuitively, observe that if the $\log k$ part is removed, we have
$\frac{n}{k}=n^{1-1/h}$, so selecting $b$ as small as $h=\frac{1}{2}\cdot
a^{1/4}$ works. The extra safety margin is merely to deal with the $\log k$
part, which intuitively should be much less significant than $n$ or $k$ —
nevertheless, we still need $a\in O(\log n)$.

Formally, we claim the following:

> If $n$ is a large enough integer, then for any real number $a\geq 1$, let
> $k=n^{2a^{-1/4}}$ and $b=\sqrt{a}$. Then $\frac{n\log k}{k}\leq n^{1-1/b}$.

By the assumption that $n$ is large enough, we have:

$\displaystyle a^{1/4}\log(2\log n)$ $\displaystyle\leq\log n$
$\displaystyle\Longrightarrow a^{1/4}\log\left(2a^{-1/4}\log n\right)$
$\displaystyle\leq\log n$ $\displaystyle\Longrightarrow a^{-1/4}$
$\displaystyle\geq\frac{\log\left(2a^{-1/4}\log n\right)}{\log n}.$ Because
$a\geq 1$, then $a^{-1/4}\geq a^{-1/2}=\frac{1}{b}$. Combining estimates, we
get: $\displaystyle 2a^{-1/4}-\frac{1}{b}$
$\displaystyle\geq\frac{\log\left(2a^{-1/4}\log n\right)}{\log n}$
$\displaystyle\Longrightarrow 1+\frac{\log\left(2a^{-1/4}\log n\right)}{\log
n}-2a^{-1/4}$ $\displaystyle\leq 1-\frac{1}{b}$
$\displaystyle\Longrightarrow\log n+\log\left(2a^{-1/4}\log
n\right)-2a^{-1/4}\log n$ $\displaystyle\leq\log
n\cdot\left(1-\frac{1}{b}\right)$ $\displaystyle\Longrightarrow\log n+\log\log
k-\log k$ $\displaystyle\leq\log n\cdot\left(1-\frac{1}{b}\right)$
$\displaystyle\Longrightarrow n\cdot\frac{\log k}{k}$ $\displaystyle\leq
n^{1-1/b}.$ ∎

###  7.3 Special Case: When the Diameter $d\in(\log n)^{O(1)}$

Using Lemma 2.1, we can prove the following weaker version of Theorem 7.1:

######  Lemma 7.2 (restate=approximateAPSPweak, name=Approximation of APSP —
weaker version).

Given the weighted diameter is $d\in(\log n)^{O(1)}$, there is a randomized
$21(1+\varepsilon)$-approximation algorithm for weighted undirected APSP in
the Congested Clique model that takes $O(\log\log\log n)$ rounds.

Here $\varepsilon$ is an arbitrarily-small positive constant.

###### Proof.

Using Corollary 7.1, we can compute an $a$-approximation of APSP, where $a\in
O(\log n)$.

Now, we repeatedly apply Lemma 2.1. After $1$, $2$, $3$, … iterations, we get
an $O(\sqrt{\log n})$, $O(\log^{1/4}n)$, $O(\log^{1/8}n)$, … approximation of
APSP. Thus, after $O(\log\log\log n)$ iterations, we can get an
$a$-approximation of APSP, where $a\in O(\log\log n)$.

At this point, due to the requirement $\log d\in a^{O(1)}$, we cannot continue
using Lemma 2.1 to reduce the approximation factor.

Instead, we uses a more direct approach, which strongly resembles the method
used in Section 2 to get the $O(\log\log n)$-round algorithm. First, we pass
our $a$-approximation of APSP to Lemma 2.2 to get a $\sqrt{n}$-nearest
$O(a\log d)$-hopset $H$. Since $a\in O(\log{\log{n}})$ and $\log{d}\in
O(\log{\log{n}})$ the number of hops is $O((\log{\log{n}})^{2})$.

Then, we can use the filtered matrix exponentiation lemma in Lemma 5.2 with
parameters $k=\sqrt{n}$ and $h=2$, so that each node knows the exact shortest
distance to the nearest $\sqrt{n}$ nodes of distance $h^{i}\in O(a\log{d})$ in
$O(i)$ rounds. The number of rounds in the Congested Clique model taken by
this step is $O(\log(a\log d))\subseteq O(\log\log\log n)$.

Finally, we apply Lemma 6.1 with $a=1$ (thus $\delta=d$ is the exact shortest
distance) and $k=\sqrt{n}$. The resulting skeleton graph $H$ would have
$O(\sqrt{n}\log n)$ nodes. Using [6], we can compute a
$3(1+\varepsilon)$-spanner with $O((\sqrt{n}\log n)^{1+1/2})\subseteq O(n)$
edges, thus the spanner can be broadcasted in $O(1)$ rounds. Thus, by the
conclusion of Lemma 6.1 we get a $21(1+\varepsilon)$-approximation of APSP of
the original graph. ∎

Alternatively, in our strengthened model (see Section 7.1), if the bandwidth
is $\log^{3}n$ bits, then all of the $O(n\log^{2}n)$ edges in the graph $H$
can be broadcasted and exact distances computed within $O(1)$ rounds, which
would give us a $7$-approximation of APSP of the original graph. Thus,

######  Lemma 7.3.

With assumptions as in Lemma 7.2, in the strengthened Congested Clique model
with bandwidth $\log^{3}n$ bits, then we can compute a $7$-approximation of
APSP in $O(\log\log\log n)$ rounds.

###  7.4 Reduction From the General Problem to the Small Weighted Diameter
Problem

Note that Lemma 7.2 requires the weighted diameter to be small. At this point,
we need the following weight scaling lemma that reduces the problem of
computing approximation of APSP on the original graph to the problem of
computing APSP on some other graphs, with smaller diameter.

######  Lemma 7.4.

Given $\delta$, a $h$-approximation of APSP for the input graph $G$, and a
constant $\varepsilon$ such that $0<\varepsilon\leq 1$, then we can
deterministically compute in $O(1)$ rounds a collection of $O(\log n)$ graphs

$\\{G_{0},G_{1},\ldots,G_{O(\log n)}\\},$

each of $n$ nodes and weighted diameter
$\leq\lceil\frac{2}{\varepsilon}\rceil\cdot h^{2}$, such that if a
$l$-approximation of APSP on each of these graphs,
$\\{\delta_{G_{0}},\delta_{G_{1}},\ldots,\delta_{G_{O(\log n)}}\\}$ are
computed, then we can deterministically compute in $O(1)$ rounds a function
$\eta$, which satisfies:

  * •

$\eta(u,v)\geq d_{G}(u,v)$ for all pairs of nodes $u$ and $v$;

  * •

if furthermore, $u$ and $v$ have some shortest path between them of no more
than $h$ hops in $G$, then $\eta(u,v)<(1+\varepsilon)l\cdot d_{G}(u,v)$.

In particular, if every pair of nodes are reachable with some shortest path of
no more than $h$ hops, then $\eta$ is a $(1+\varepsilon)l$-approximation of
APSP.

As usual, $\varepsilon$ is a positive constant that can be made arbitrarily
small, and the graphs $G_{i}$ and distance approximations $\delta_{G_{i}}$ are
known in the sense explained at the beginning of this section: each node $v$
knows all the values adjacent to $v$.

In the applications of this lemma, we will have $l\ll h$, thus we start with
an inaccurate $h$-approximation $\delta$, and end up with a more accurate
$(1+\varepsilon)l$-approximation $\eta$.

#### Proof strategy.

Intuitively, the main observation is the following: we _round_ the weights,
then _truncate_ them. Given a path between two nodes such as:

$3$$1$$203$$7$

This is a $4$-hop path.

Let $x=10$, and round up every edge weight to the nearest multiple of $x$.

$10$$10$$210$$10$

Even though each _individual_ edge weight may increase by a large factor (for
instance, the weight of the edge originally has weight $1$ is increased by
$900\%$), in this case, the overall length of the path only increases from
$214$ to $240$ — that is, only a $12\%$ increase.

We see that the overall increment is controlled by the value of $x$ and the
number of hops $h=4$ — as such, as long as $x\cdot h$ is small compared to
$d(u,v)$, there is no problem.

At a high-level, we divide the collection of all pairs $(u,v)$ into $O(\log
n)$ groups based on the approximate scale of $d(u,v)$ — that is,
$d(u,v)\approx\frac{2^{i}}{\varepsilon}$ for each $0\leq i\leq O(\log n)$.
Then, for each $i$, the graph $G_{i}$ is defined by rounding each edge weight
up according to the scale, we then _truncate_ the edge weights in order to
force the diameter to be small enough.

The initial approximation $\delta$ is used in order to approximately determine
the scale for each pair of vertices $(u,v)$. In all applications of this
lemma, the bandwidth is large enough such that the running an algorithm on the
$O(\log(n))$ graphs $G_{i}$ is not an issue.

###### Proof.

First, we describe the algorithm. Set $B=\lceil\frac{2}{\varepsilon}\rceil$.

  * •

From the graph $G$, we construct the collection of graphs $\\{G_{i}\\}$ as
follows:

Let $0\leq i\leq O(\log n)$ be an integer. Define $x=2^{i}$.

For each $i$, construct the new graph $G_{i}$ as follows:

    * –

Create a graph $H_{i}$ consisting of nodes in $G$, and the edges are taken
from $G$ but rounding the weight up to the closest multiple of $x$ (formally,
for every edge connecting $u$ and $v$ in $G$ with weight $w$, there is an edge
connecting $u$ and $v$ in $G_{i}$ with weight $\lceil\frac{w}{x}\rceil\cdot x$
— note that the new weight is $\leq w+x-1$).

    * –

Create a graph $K_{i}$ from $H_{i}$, but for every pair of $u$ and $v$ in
$H_{i}$, add an additional edge connecting $u$ and $v$ with weight $x\cdot
B\cdot h^{2}$. As such, $K_{i}$ is a multigraph where between each pair of
nodes there may be up to $2$ undirected edges. For the purpose of shortest
path computation, we only need to keep the edge with the smaller weight among
the two. Thus, this step can be equivalently understood as: for every pair of
nodes $u$ and $v$, set the weight of the edge between the two nodes to be
$w_{uv}\leftarrow\min(w_{uv},x\cdot B\cdot h^{2})$, adding an edge if there
weren’t one.

    * –

Finally, note that all edge weights in $K_{i}$ are integers $\leq x\cdot
B\cdot h^{2}$ and divisible by $x$. Construct $G_{i}$ to be the same graph as
$K_{i}$, but with all of the edge weights divided by $x$. Clearly the weighted
diameter of $G_{i}$ is $\leq B\cdot h^{2}$.

  * •

Given the computed distance-approximation $\delta_{G_{i}}$ of each graph
$G_{i}$, for each pair of nodes $u\neq v$, as well as $\delta$ which is a
$h$-approximation of APSP on $G$, the nodes $u$ and $v$ compute the value of
$\eta(u,v)$ as follows:

    * –

Pick an integer $i\geq 0$ such that $2^{i-1}\cdot B\cdot h^{2}(u,v)<2^{i}\cdot
B\cdot h^{2}$, then set $\eta(u,v)=2^{i}\cdot\delta_{G_{i}}(u,v)$.

    * –

If there exists such $i$, because $d(u,v)$ is bounded by a polynomial in $n$,
then $i\leq O(\log n)$, so the graph $G_{i}$ exists, and $\delta_{G_{i}}$ has
been computed in the previous step.

    * –

If there’s no such $i$, then $\delta(u,v)<\frac{B}{2}\cdot h^{2}$, pick $i=0$
and set $\eta(u,v)=\delta_{G_{0}}(u,v)$.

All the computations are done locally by the endpoints of each edge, thus can
be done in $O(1)$ rounds.

Then, to prove the correctness of the algorithm. Consider any pair of nodes
$u\neq v$.

  * •

Assume there exists integer $i\geq 0$ such that $2^{i-1}\cdot B\cdot
h^{2}(u,v)<2^{i}\cdot B\cdot h^{2}$ as above. Define $x=2^{i}$ as before, then
we get $\frac{x}{2}\cdot B\cdot h\leq d_{G}(u,v)<x\cdot B\cdot h^{2}$.

By construction of $H_{i}$, then $d_{G}(u,v)\leq d_{H_{i}}(u,v)$.

Combining with $d_{G}(u,v)\leq x\cdot B\cdot h^{2}$, then we get
$d_{G}(u,v)\leq\min(d_{H_{i}}(u,v),x\cdot B\cdot h^{2})=d_{K_{i}}(u,v)$.

  * •

If furthermore there exist a $\leq h$-hop shortest path between $u$ and $v$,
then $d_{H_{i}}(u,v)\leq d_{G}(u,v)+(x-1)\cdot h$ — recall that in the
construction of the graph $H_{i}$, each edge weight is increased by an amount
at most $(x-1)$ — thus $d_{H_{i}}(u,v)<d_{G}(u,v)+x\cdot
h\leq(1+\varepsilon)\cdot d_{G}(u,v)$, where the last inequality follows from
the fact that $\frac{x}{2}\cdot B\cdot h\leq d_{G}(u,v)$ and
$B=\lceil\frac{2}{\varepsilon}\rceil$.

By construction of $K_{i}$, then $d_{K_{i}}(u,v)=\min(d_{H_{i}}(u,v),x\cdot
B\cdot h^{2})\leq d_{H_{i}}(u,v)<(1+\varepsilon)\cdot d_{G}(u,v)$.

Therefore, $d_{K_{i}}(u,v)<(1+\varepsilon)\cdot d_{G}(u,v)$.

  * •

If there does not exist such integer $i$ and we pick $i=0$, then
$\delta(u,v)<\frac{B}{2}\cdot h^{2}$ as mentioned above, which means
$d(u,v)<\frac{B}{2}\cdot h^{2}$.

Using the analysis similar to the above, except that we observe that
$x-1=2^{i}-1=0$ (i.e. the weight-rounding is not performed), which imply
$d_{K_{i}}(u,v)=d_{H_{i}}(u,v)=d_{G}(u,v)$.

Either way, by combining the assumptions:

  * •

$d_{G}(u,v)\leq d_{K_{i}}(u,v)$,

  * •

if $u$ and $v$ have a shortest path between them using no more than $h$ hops,
then $d_{K_{i}}(u,v)<(1+\varepsilon)d_{G}(u,v)$,

  * •

$\delta_{G_{i}}(u,v)$ is a $l$-approximation of $d_{G_{i}}(u,v)$,

  * •

$\eta(u,v)=2^{i}\cdot\delta_{G_{i}}(u,v)$,

the final approximation is $\eta(u,v)$ satisfies the requirements.

We have proven the algorithm is correct. From the description, all the
computations are done locally, so they can clearly be performed in $O(1)$
rounds. ∎

######  Remark 7.1.

We see that the $h^{2}$ factor (instead of $h$) in the diameter of the graph
$G_{i}$ is caused by: the initial $h$-approximation $\delta$ is used to
_select_ which $\delta_{G_{i}}$ should be used. Because for the pairs of nodes
we care about, there exist a shortest path between them with no more than $h$
hops, each of the edges contributes $2^{i}$ to the rounding error, so in
total, $2^{i}\cdot h$ error is induced. And we want this error to be $\leq$
the actual distance, but because $\delta$ itself has an error factor of $h$,
so we can only upper bound the actual distance at $2^{i}\cdot h^{2}$.

In summary: one $h$ factor is from the number of hops, the other $h$ factor is
from the approximation factor of $\delta$.

###  7.5 Special Case 2: When the Bandwidth is $\log^{4}n$ Bits

We can combine Lemma 7.2 and Lemma 7.4 to show the following.

######  Theorem 7.3 (name=, restate=specialcaseii).

Let $G$ be a graph with $n$ nodes. In the strengthened Congested Clique model
with bandwidth $\log^{4}n$ bits, it is possible to obtain a
$7^{3}(1+\varepsilon)^{2}$-approximation of APSP with high probability in
$O(\log\log\log n)$ rounds.

As before, $\varepsilon$ is an arbitrarily-small positive constant.

At a high-level, we work as follows. Initially we have an
$a=O(\log{n})$-approximation to APSP.

  1. 1.

We start by computing a $\sqrt{n}$-nearest $O(a\log{n})=O(\log^{2}{n})$-hopset
by Lemma 2.2.

  2. 2.

Our first goal is to compute distances to the $\sqrt{n}$-nearest nodes. Note
that each node has paths of $\beta=O(\log^{2}{n})$ hops connecting it to these
nodes.

  3. 3.

We construct the $O(\log{n})$ graphs $G_{i}$ from Lemma 7.4 with the parameter
$h=\beta$. These graphs are guaranteed to have weighted diameter
$O(\log^{4}{n})$.

  4. 4.

Now we can apply Lemma 7.2 on the graphs $G_{i}$, to compute
$O(1)$-approximation for the distances in $G_{i}$ in $O(\log{\log{\log{n}}})$
rounds. By Lemma 7.4 this gives $O(1)$-approximation to the distances in $G$
between pairs of nodes that have paths of $h$ hops between them. In
particular, it allows each node $u$ to compute a set $\tilde{N}_{k}(u)$ of the
approximately closest $k=\sqrt{n}$ nodes that satisfies the requirements of
Lemma 6.1.

  5. 5.

Finally, we use Lemma 6.1 to construct a skeleton graph $G_{S}$ on
$\tilde{O}(\sqrt{n})$ nodes, such that an $O(1)$-approximation of the
distances on $G_{S}$ gives an $O(1)$-approximation to the distances in $G$.
Since $G_{S}$ has size $\tilde{O}(\sqrt{n})$ we can get an
$O(1)$-approximation to the distances in $G_{S}$ in $O(1)$ rounds. Optimizing
the parameters leads to a final approximation of $7^{3}+\epsilon$ for the
distances in $G$.

Implementing this approach directly may require each node to send
$\operatorname{poly}(\log{n})$ bits to each other node in each round, for
example to simulate the algorithms on $O(\log{n})$ different graphs $G_{i}$.
To simplify the presentation, in this part, the algorithm assumes the
strengthened Congested Clique model where each node can send $O(\log^{4}{n})$
bits to each other node in each round.

###### Proof.

First, use Corollary 7.2 to compute a $a$-approximation of APSP where $a\in
O(\log n)$.

Then we use Lemma 2.2 with $a=a$, and the diameter of the graph is of course
$d\in n^{O(1)}$. Thus, we get a $\sqrt{n}$-nearest $\beta$-hopset $H$, where
$\beta\in O(a\log d)\subseteq O(\log^{2}n)$.

We assume that the set of edges in $G$ is a subset of the set of edges in $H$
— taking the union if necessary. Thus, any node can reach the nearest set of
$\sqrt{n}$ nodes using at most $\beta$ hops, using only the edges in $H$.

Now, we want to approximate $d_{H}(u,v)$ for pairs of nodes $u$ and $v$ that
are reachable within $\beta$ hops, using the edges in $H$. Thus, we use Lemma
7.4 with input:

  * •

the parameter $h=\beta\in O(\log^{2}n)$,

  * •

the parameter $l=7$,

  * •

the input graph $G$ is $H$,

  * •

the distance approximation $\delta$ on $H$ is computed using Corollary 7.2,

  * •

$0<\varepsilon\leq 1$ is an arbitrarily small constant.

As a result, we obtain a collection $\\{H_{i}\\}$ of $O(\log n)$ graphs. By
the hypothesis of Lemma 7.4, the diameter of each of the graphs $H_{i}$ is in
$O(\log^{2}n)$.

Thus, we can use the special case above, Lemma 7.3, on each of the graphs
$H_{i}$, to compute a $7$-approximation $\delta_{H_{i}}$ on $H_{i}$. This is
possible because the extra bandwidth allows us to run $O(\log n)$ independent
copies of the algorithm in Lemma 7.3. This step takes $O(\log\log\log n)$
rounds.

By the conclusion of Lemma 7.4, from a $7$-approximation of each of the graphs
$H_{i}$ in the collection above, we get back $\eta$ being a distance
approximation on $H$. This distance approximation $\eta$ is such that, for
every pair of nodes $(u,v)$ such that there is some $\beta$-hop shortest path
between $u$ and $v$ on the graph formed by $H$, then
$d_{H}(u,v)\leq\eta(u,v)\leq 7(1+\varepsilon)\cdot d_{H}(u,v)$.

In particular, by the construction of $H$, for every node $u$ and every node
$v\in N_{\sqrt{n}}(u)$, then there is a path of at most $\beta$ hops, using
only edges in $H$, with length $d(u,v)$. In other words, for every such nodes
$u$ and $v$ then $d(u,v)\leq\eta(u,v)\leq 7(1+\varepsilon)\cdot d(u,v)$.

Finally, using Lemma 6.1 with parameters:

  * •

$G$ is the graph,

  * •

$\delta$ is the $7(1+\varepsilon)$-approximation $\eta$ computed in the
previous step,

  * •

for each node $u$, then $\tilde{N}_{k}(u)$ is computed to be the set of $k$
nodes $v$ with smallest value of $\eta(u,v)$, breaking ties by IDs,

  * •

$a=7(1+\varepsilon)$,

  * •

$l=1$,

  * •

and $k=\sqrt{n}$,

note that the constructed skeleton graph $G_{S}$ will have $O((\sqrt{n}\log
n)^{2})$ edges, all of the edges can be broadcasted and APSP computed exactly
(thus that’s why $l=1$), we obtain a $7^{3}(1+\varepsilon)^{2}$-approximation
of APSP of $G$ as desired.

The only thing remains to prove is that the approximation $\delta=\eta$,
together with the choice of $\tilde{N}_{k}(u)$ sets, satisfies the hypotheses
of Lemma 6.1. Note that we computed the sets $\tilde{N}_{k}(u)$ according to
the approximation $\delta=\eta$, and hence they are not necessarily equal to
the set $N_{k}(u)$ of the $k$-nearest nodes, but we show that they still
satisfy the properties that we need.

By the hypothesis, for all $v\in N_{k}(u)$, then $d(u,v)\leq\delta(u,v)\leq
a\cdot d(u,v)$.

We will just check the two conditions needed for Lemma 6.1.

######  Claim 7.1.

For every $v\in\tilde{N}_{k}(u)$, then $\delta(u,v)\leq a\cdot d(u,v)$.

######  Claim 7.2.

For every $v\in\tilde{N}_{k}(u)$ and $t\notin\tilde{N}_{k}(u)$, then
$\delta(u,v)\leq a\cdot d(u,t)$.

To show the claims above, first, define $x$ to be a node that is in
$N_{k}(u)\setminus\tilde{N}_{k}(u)$ with smallest $d(u,x)$, or if
$N_{k}(u)\setminus\tilde{N}_{k}(u)$ is empty, then we must have
$N_{k}(u)=\tilde{N}_{k}(u)$ (because both sets have exactly $k$ elements),
define $x$ to be the element in $N_{k}(u)$ with maximum value of
$\delta(u,x)$.

In either case, we have the property that for every $v\in\tilde{N}_{k}(u)$,
then $\delta(u,v)\leq\delta(u,x)$. Furthermore, $x\in N_{k}(u)$, so
$\delta(u,x)\leq a\cdot d(u,x)$.

So, the first claim can be seen because: for every $v\in\tilde{N}_{k}(u)$,
then:

  * •

if $v\in N_{k}(u)$, then $\delta(u,v)\leq a\cdot d(u,v)$ trivially by the
hypothesis of $\delta$;

  * •

otherwise, $\delta(u,v)\leq\delta(u,x)\leq a\cdot d(u,x)\leq a\cdot d(u,v)$.

The second claim can be seen because: let $v\in\tilde{N}_{k}(u)$ and
$t\notin\tilde{N}_{k}(u)$, then $\delta(u,v)\leq\delta(u,x)\leq a\cdot
d(u,x)\leq a\cdot d(u,t)$.

So we are done. ∎

######  Remark 7.2.

In the proof above, the only step that takes $O(\log\log\log n)$ rounds is
Lemma 7.3, the remaining steps take $O(1)$ rounds each.

There are two places that we need the extra bandwidth — first in the parallel
application of Lemma 7.3 on $O(\log n)$ disjoint graphs, and second in the
last step where we broadcast all the edges in the skeleton graph.

###  7.6 General Case

Here, we make the algorithm described in Section 7.5 work in the standard
Congested Clique model while only adding a constant factor to the
approximation.

*

At a high level, we start by computing distances to $\log^{4}{n}$-nearest
nodes (we can do so in $O(1)$ rounds using Lemma 5.2), and then construct a
skeleton graph $G_{S}$ on $O(\frac{n}{\log^{3}n})$ nodes, and we simulate the
whole algorithm on $G_{S}$. Since $G_{S}$ has size $O(\frac{n}{\log^{3}n})$ we
can simulate routing $O(\log^{4}{n})$ bits between each of its nodes in $O(1)$
rounds using Lemma 3.1.

###### Proof of Theorem 7.1.

First, we can compute for each node the $\log^{4}n$-nearest set as follows:

  * •

Select $k=\log^{4}n$.

  * •

Thus, we can select $h\in\Theta(\frac{\log n}{\log\log n})$ such that $k\in
O(n^{1/h})$.

  * •

Thus, $h\in\Omega(\sqrt{\log n})$, so $k=\log^{4}n\in h^{O(1)}$.

  * •

Each node can certainly reach its $k$-nearest set in no more than $k$ hops
(using the set of edges of the original graph). Thus, Lemma 5.2 can be used to
compute in $O(1)$ rounds, for each node, its $k$-nearest set, so we are done.

Next, we use Lemma 6.1 with parameters:

  * •

$k=\log^{4}n$ and $a=1$, so $\delta=d$ is the exact distance between any two
nodes, (observe that the above step makes every node $v$ know their exact
$k$-nearest nodes, and the distance to these nodes, so the value of $k$ and
$a$ is already fixed)

  * •

$l=7^{3}(1+\varepsilon)^{2}$,

compute a skeleton graph $G_{S}$ of $O(\frac{n}{\log^{3}n})$ nodes.

Because $G_{S}$ only has $O(\frac{n}{\log^{3}n})$ nodes, we can simulate an
algorithm in the strengthened Congested Clique model with bandwidth of
$\log^{4}n$ bits on the graph $G_{S}$, using Lemma 3.1. More concretely, we
simulate an algorithm on the graph $G_{S}$ as follows. Note that each node of
$G_{S}$ should send and receive $O(\log^{4}{n})$ bits from each of the
$O(\frac{n}{\log^{3}n})$ other nodes in $G_{S}$. In total, it should send and
receive $O(n)$ messages of $O(\log{n})$ bits which can be done using Lemma
3.1.

Based on that we can apply the special case above, Theorem 7.3, so we can
compute $7^{3}(1+\varepsilon)^{2}$-approximate APSP on $G_{S}$. Then, by the
conclusion of Lemma 6.1, each node can compute
$7^{4}(1+\varepsilon)^{2}$-approximate APSP on $G$. Since $\varepsilon>0$ can
in fact be made arbitrarily small, the conclusion follows.

Apart from Theorem 7.3 which takes $O(\log\log\log n)$ rounds, all of the
other steps take $O(1)$ rounds each. Therefore, the final time complexity is
$O(\log\log\log n)$, as needed. ∎

###  7.7 Limiting the Number of Rounds

Now, we will prove the version where the algorithm is limited to $O(t)$
rounds, which we restate below.

*

Essentially, we simply reuse the proof, but truncate the number of rounds
taken.

For the first step, when $d\in(\log n)^{O(1)}$, instead of Lemma 7.2, we have:

######  Lemma 7.5.

Given that the weighted diameter is $d\in(\log n)^{O(1)}$, there is a
randomized $O(\log^{2^{-t}}n)$-approximation algorithm for weighted undirected
APSP that takes $O(t)$ rounds, where $t\geq 1$ is provided as a parameter.

###### Proof.

We repeat the proof in Section 7.3, with the following modifications:

  * •

If $t$ is large enough such that the desired approximation factor
$O(\log^{2^{-t}}n)$ is $\leq O(\log\log n)$, this means
$t\in\Omega(\log\log\log n)$, so we can apply Lemma 7.2 which takes
$O(\log\log\log n)\subseteq O(t)$ rounds.

  * •

Otherwise, we use the first part of Section 7.3, applying Lemma 2.1 for $t$
times such that we get an $O(\log^{2^{-t}}n)$-approximation of APSP.∎

The corresponding version of Theorem 7.3 would be the following.

######  Theorem 7.4.

Let $G$ be a graph with $n$ nodes. In the strengthened Congested Clique model
with bandwidth $\log^{4}n$, it is possible to obtain an
$O(\log^{2^{-t}}n)$-approximation of APSP in $O(t)$ rounds with high
probability, where $t\geq 1$ is given as a parameter.

###### Proof.

Proceed exactly as the proof of Theorem 7.3. However, instead of applying
Lemma 7.2 on each of the graphs $H_{i}$, we apply Lemma 7.5 with the parameter
$t$ being set to $t+1$, so that the approximation $\delta_{H_{i}}$ is a
$b$-approximation, where $b\in O(\log^{2^{-t}/2}n)$.

Thus, the obtained approximation $\eta$ satisfies that for every pair of nodes
$(u,v)$ such that there is some $\beta$-hop shortest path between $u$ and $v$
on the graph formed by $H$, then $d(u,v)\leq\eta(u,v)\leq
b(1+\varepsilon)\cdot d(u,v)$.

Finally, as before, we set parameter $a=b(1+\varepsilon)$ (the other
parameters are the same as before) and apply Lemma 6.1. The final result is a
$O(a^{2})$-approximation of APSP, because $a\in O(\log^{2^{-t}/2}n)$, then
$a^{2}\in O(\log^{2^{-t}}n)$ as desired. ∎

Finally, for the main theorem:

*

The proof once again is similar, except that we apply Theorem 7.4 with
parameter $t=t$ instead of Theorem 7.3.

##  8 Discussion

In this work we showed that $O(1)$-approximation for APSP can be computed in
$O(\log{\log{\log{n}}})$ rounds in the Congested Clique model. Many intriguing
questions remain open. First, a natural goal would be to obtain
$O(1)$-approximation in $O(1)$ rounds. One direction to obtain it is to
develop a faster algorithm for computing the distances to the $k$-nearest
nodes. Our current approach allows to compute these distances in $O(1)$ rounds
for sub-polynomial values of $k$. If one can compute these values (or
$O(1)$-approximation for them) in $O(1)$ rounds for a small polynomial value
of $k$ it would directly lead to $O(1)$-approximation for APSP in $O(1)$
rounds.

Another interesting question is whether similar results can be obtained in the
closely related linear-memory Massively Parallel Computation (MPC) model. A
direct simulation of the Congested Clique model in the near linear-memory MPC
model requires $\tilde{\Omega}(n^{2})$ total memory which is too expensive for
the MPC model, so obtaining similar results in the MPC model would require
developing low-memory variants of the algorithms.

## References

  * [1]
  * Censor-Hillel et al. [2021] Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf. 2021.  Fast approximate shortest paths in the congested clique.  _Distributed Computing_ 34, 6 (01 Dec 2021), 463–487.  https://doi.org/10.1007/s00446-020-00380-5
  * Censor-Hillel et al. [2020] Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman. 2020.  Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. In _34th International Symposium on Distributed Computing (DISC 2020)_ _(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 179)_ , Hagit Attiya (Ed.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 33:1–33:17.  https://doi.org/10.4230/LIPIcs.DISC.2020.33
  * Censor-Hillel et al. [2019a] Keren Censor-Hillel, Petteri Kaski, Janne H Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. 2019a.  Algebraic methods in the congested clique.  _Distributed Computing_ 32, 6 (2019), 461–478.
  * Censor-Hillel et al. [2019b] Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner. 2019b.  Sparse matrix multiplication and triangle listing in the congested clique model.  _Theoretical Computer Science_ (2019).
  * Chechik and Zhang [2022] Shiri Chechik and Tianyi Zhang. 2022.  Constant-Round Near-Optimal Spanners in Congested Clique. In _Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing_ (Salerno, Italy) _(PODC’22)_. Association for Computing Machinery, New York, NY, USA, 325–334.  https://doi.org/10.1145/3519270.3538439
  * Dor et al. [2000] Dorit Dor, Shay Halperin, and Uri Zwick. 2000.  All-pairs almost shortest paths.  _SIAM J. Comput._ 29, 5 (2000), 1740–1759.
  * Dory et al. [2021] Michal Dory, Orr Fischer, Seri Khoury, and Dean Leitersdorf. 2021\.  Constant-Round Spanners and Shortest Paths in Congested Clique and MPC. In _Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC)_ (Virtual Event, Italy) _(PODC’21)_. Association for Computing Machinery, New York, NY, USA, 223–233.  https://doi.org/10.1145/3465084.3467928
  * Dory and Parter [2022] Michal Dory and Merav Parter. 2022.  Exponentially faster shortest paths in the congested clique.  _ACM Journal of the ACM (JACM)_ 69, 4 (2022), 1–42.
  * Korhonen and Suomela [2018] Janne H. Korhonen and Jukka Suomela. 2018.  Towards a Complexity Theory for the Congested Clique. In _Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures_ (Vienna, Austria) _(SPAA ’18)_. Association for Computing Machinery, New York, NY, USA, 163–172.  https://doi.org/10.1145/3210377.3210391
  * Le Gall [2016] François Le Gall. 2016\.  Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems. In _Distributed Computing_ , Cyril Gavoille and David Ilcinkas (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 57–70.
  * Lenzen [2013] Christoph Lenzen. 2013\.  Optimal Deterministic Routing and Sorting on the Congested Clique. In _Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing_ (Montréal, Québec, Canada) _(PODC ’13)_. Association for Computing Machinery, New York, NY, USA, 42–50.  https://doi.org/10.1145/2484239.2501983
  * Nazari [2020] Yasamin Nazari. 2020\.  Sparse Hopsets in Congested Clique. In _23rd International Conference on Principles of Distributed Systems (OPODIS 2019)_ _(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 153)_ , Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 34:1–34:16.  https://doi.org/10.4230/LIPIcs.OPODIS.2019.34
  * Nowicki [2021] Krzysztof Nowicki. 2021\.  A deterministic algorithm for the MST problem in constant rounds of congested clique. In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ (Virtual, Italy) _(STOC 2021)_. Association for Computing Machinery, New York, NY, USA, 1154–1165.  https://doi.org/10.1145/3406325.3451136

##  Appendix A Missing Proofs from Section 3

We next prove Theorem 3.1.

See 3.1

###### Proof.

We do the following:

  1. 1.

Compute the connected components of the subgraph consisting of the edges with
weight $0$ (in other words, two nodes $u$ and $v$ belong to the same component
if and only if $d_{G}(u,v)=0$);

  2. 2.

For each connected component, compute a representative node that serves as the
“leader” of that component;

  3. 3.

For every two leaders $s$ and $t$, both $s$ and $t$ know the minimum weight of
an edge that connects the component of $s$ and the component of $t$.

All of the above can be done in $O(1)$ rounds because:

  1. 1.

Step 1 can use existing algorithm for minimum spanning tree. Using the
algorithm in [14], this takes $O(1)$ rounds.

In particular, as explained in the cited paper, after the algorithm is
finished, every node knows the whole minimum spanning tree.

From that information, each node can locally filter the spanning tree to keep
only the edges with weight $0$, which allows them to compute all the connected
components induced by the $0$-weight edges.

  2. 2.

Step 2, for each connected component, we can just take the node with minimum
number.

As mentioned above, each node knows the connected components of the whole
graph, as such everything can be computed locally.

  3. 3.

Step 3 is the nontrivial part, it is proven below.

Let $S$ be the set of leaders. For a leader $s\in S$, write $C(s)$ to be the
set of nodes that are in the same component as $s$ (including $s$ itself) — in
other words, $C(s)=\\{v\in V\mid d(s,v)=0\\}$. By the discussion above, every
node knows every value of $C(\cdot)$.

We execute the following algorithm:

  1. 1.

For each node $v$ and each leader $t$, node $v$ sends a message $(s,w)$ to
node $t$, where $s$ is the leader of $v$, and $w$ is the minimum weight of an
edge connecting $v$ and any node in $C(t)$.

  2. 2.

Each leader $t$ receives a collection of messages $(s,w)$, for each value of
$s$ it takes the minimum value of $w$ among all these messages.

The algorithm is correct, as it guarantees that each leader $t$ learns the
minimum weight edge connecting any node in $C(t)$ to $C(s)$ for any other
leader $s$. In addition, each node $v$ just sends one message to each leader,
and each leader only receive one message from each other node, so the running
time is $O(1)$ rounds.

Afterwards, the compressed graph has its set of nodes being $S$, the set of
leaders. We run the algorithm $A$ on it, and get back a distance approximation
$\delta\colon S\times S\rightarrow\mathbb{Z}$. This takes $f(n)$ rounds, by
assumption.

We wish to compute the resulting distance approximation $\eta\colon V\times
V\rightarrow\mathbb{Z}$ by: for every leaders $s,t\in S$, and $v\in C(s)$,
$u\in C(t)$, then $\eta(v,u)=\delta(s,t)$. Clearly $\eta$ is an
$a$-approximation of APSP on $G$. Note that all nodes know all sets $C(s)$, so
to complete the algorithm, each node $v\in C(s)$ just needs to learn the
distance $\delta(s,t)$ for each leader $t$. To do so, each leader $t$ sends to
$v\in C(s)$ the message $\delta(s,t)$. Since each leader just sends one
message to each node $v$ this takes $O(1)$ rounds. ∎