Near-Linear Lower Bounds for Distributed Distance Computations,
Even in Sparse Networks
Amir Abboud∗

Keren Censor-Hillel†

Seri Khoury†

arXiv:1605.05109v1 [cs.DC] 17 May 2016

May 18, 2016

Abstract
We develop a new technique for constructing sparse graphs that allow us to prove nearlinear lower bounds on the round complexity of computing distances in the CONGEST model.
e
Specifically, we show an Ω(n)
lower bound for computing the diameter in sparse networks, which
was previously known only for dense networks [Frishknecht et al., SODA 2012]. In fact, we can
even modify our construction to obtain graphs with constant degree, using a simple but powerful
degree-reduction technique which we define.
e
Moreover, our technique allows us to show Ω(n)
lower bounds for computing ( 32 − ε)approximations of the diameter or the radius, and for computing a ( 53 − ε)-approximation of all
eccentricities. For radius, we are unaware of any previous lower bounds. For diameter, these
greatly improve upon previous lower bounds and are tight up to polylogarithmic factors [Frishknecht et al., SODA 2012], and for eccentricities the improvement is both in the lower bound
and in the approximation factor [Holzer and Wattenhofer, PODC 2012].
Interestingly, our technique also allows showing an almost-linear lower bound for the verification of (α, β)-spanners, for α < β + 1.

∗

Stanford University, Department of Computer Science, abboud@cs.stanford.edu. Supported by Virginia Vassilevska Williams’s NSF Grants CCF-1417238 and CCF-1514339, and BSF Grant BSF:2012338.
†
Technion, Department of Computer Science, {ckeren,serikhoury}@cs.technion.ac.il. Supported by ISF Individual Research Grant 1696/14.

1

Introduction

The diameter and radius are two basic graph parameters whose values play a vital role in many
applications. In distributed computing, these parameters are even more fundamental, since they
capture the minimal number of rounds needed in order to send a piece of information to all the
nodes in a network. Hence, understanding the complexity of computing these parameters is central
to distributed computing, and has been the focus of many studies in the CONGEST model of
computation, where in every round each of n nodes may send messages of up to O(log n) bits to
each of its neighbors. Frischknecht et al. [21] showed that the diameter is surprisingly hard to
e
compute: Ω(n)
rounds are needed even in networks with constant diameter.1 This lower bound is
nearly tight, due to an O(n) upper bound presented by [36] to compute all pairs shortest paths in
a network. Naturally, approximate solutions are a desired relaxation, and were indeed addressed in
several cornerstone studies [21,24,26,30,36], bringing us even closer to a satisfactory understanding
of the time complexity of computing distances in distributed networks. However, several central
questions remained elusive.
Sparse Graphs. The graphs constructed in [21] have Θ(n2 ) edges and constant diameter, and
e
require any distributed protocol for computing their diameter to spend Ω(n)
rounds. Such a high
lower bound makes one wonder if the diameter can be computed faster in networks that we expect
to encounter in realistic applications. Almost all large networks of practical interest are very
sparse [31], e.g. the Internet in 2012 had ≈ 4 billions nodes and ≈ 128 billion edges [32].
The only known lower bound for computing the diameter of a sparse network is obtained by a
e √n). This
simple modification to the construction of [21] which yields a much weaker bound of Ω(
e
leaves hope that the Ω(n)
bound can be beaten significantly in sparse networks. Our first result is
to rule out this possibility.
Theorem 1.1. The number of rounds needed for any protocol to compute the diameter of a network
on n nodes and O(n log n) edges of constant diameter in the CON GEST model is Ω( logn2 n ).
We remark that, as in [21], our lower bound holds even for networks with constant diameter
and even against randomized algorithms. Throughout the paper we say that a graph on n nodes
is sparse if it has O(n log n) edges. Due to simple transformations, e.g. by adding dummy nodes,
all of our lower bounds will also hold for the more strict definition of sparse graphs as having O(n)
edges, up to a loss of a log factor.
As explained next, the sparsity in our new lower bound construction allows us to extend the
result in some interesting ways.
Approximation Algorithms. Another important question is whether we can bypass this nearlinear barrier if we settle for knowing only an approximation to the diameter. An α-approximation
algorithm to the diameter returns a value D̂ such that D ≤ D̂ ≤ α · D, where D is the diameter
e √n + D) rounds are needed, even for computing a
of the network. From [21] we know that Ω(
( 32 − ε)-approximation to the diameter, for any constant ε > 0.
Following this lower bound, almost-complementary upper bounds were under extensive research.
It is known that a 32 -approximation can be computed in a sublinear number of rounds: Holzer and
Wattenhofer [26] showed a O(n3/4 + D)-round algorithm and (independently) Peleg et al. [36]
√
√
obtained a O(D n log n) bound, later these bounds were improved to √
O( n log n + D) by Lenzen
and Peleg [30], and finally Holzer et al. [24] reduce the bound to O( n log n + D). When D is
1

e and O
e hide factors that are polylogarithmic in n.
The notations Ω

1

small, these upper bounds are near-optimal in terms of the round complexity – but do they have
the best possible approximation ratio that can be achieved within a sublinear number of rounds?
e √n + D) rounds, to match the lower
That is, can we also obtain a ( 32 − ε)-approximation in O(
bound of [21]?
Progress towards answering this question was made by Holzer and Wattenhofer [26] who showed
e
that any algorithm that needs to decide whether the diameter is 2 or 3 has to spend Ω(n)
rounds.
However, as the authors point out, their lower bound is not robust and does not rule out the
possibility of a ( 23 − ε)-approximation when the diameter is larger than 2, or an algorithm that is
allowed an additive +1 error besides a multiplicative ( 32 − ε) error.
Perhaps the main difficulty in extending the lower bound constructions of [21] and [26] to resolve
these gaps was that their original graphs are dense. A natural way to go from a lower bound
construction against exact algorithms to a lower bound against approximations is to subdivide
each edge into a path. When applied to dense graphs, this transformation blows up the number of
e √n) lower bound [21]. Our new sparse construction technique
nodes quadratically, resulting in a Ω(
allows us to tighten the bounds and negatively resolve the above question. In particular, we show
e
a Ω(n)
lower bound for computing a ( 32 − ε)-approximation to the diameter.
Theorem 1.2. For all constant 0 < ε < 1/2, the number of rounds needed for any protocol to
compute a (3/2 − ε)-approximation to the diameter of a sparse network is Ω( logn3 n ).
Radius. In many scenarios we want one special node to be able to efficiently send information
to all other nodes. In this case, we would like this node to be the one that is closest to every other
node, i.e. the center of the graph. The radius of the graph is the largest distance from the center,
and it captures the number of rounds needed for the center node to transfer a message to another
node in the network. While radius and diameter are closely related, the previous lower bounds for
diameter do not transfer to radius and it was conceivable that the radius of the graph could be
computed much faster. Obtaining a non-trivial lower bound for radius has been stated as an open
problem in [26]. A third advantage of our technique is that it extends to computing the radius, for
which we show that the same strong near-linear barriers above hold.
Theorem 1.3. For all constant 0 < ε < 1/2, the number of rounds needed for any protocol to
compute a (3/2 − ε)-approximation to the radius of a sparse network is Ω( logn3 n ).
Eccentricity The eccentricity of a node is the largest distance from it. Observe that the diameter
is the largest eccentricity in the graph while the radius is the smallest. As pointed in [26], given
a ( 23 − ε)-approximation algorithm to all the eccentricities, we can achieve ( 23 − ε)-approximation
e √n + D) lower bound for any
algorithm to the diameter by a simple flooding. This implies an Ω(
( 32 − ε)-approximation algorithm for computing all the eccentricities. Our construction allows us to
improve this result by showing that any algorithm for computing even a ( 53 − ε)-approximation to
all the eccentricities must spend Ω( logn3 (n) ) rounds. This improves both in terms of the number of
rounds, and in terms of the approximation factor, which we allow to be even larger. Interestingly,
it implies that approximating all eccentricities is even harder than approximating just the largest
or the smallest one.
Theorem 1.4. For all constant 0 < ε < 2/3, the number of rounds needed for any protocol to
compute a (5/3 − ε)-approximation of all eccentricities of a sparse network is Ω( logn3 n ).

2

Constant-Degree Graphs For computing exact diameter and radius, we can modify the graph
constructions according to a degree-reduction technique we define, such that the resulting graphs
have a constant degree, and still allow us to obtain near-linear lower bounds. Roughly speaking,
given a node v, we replace a subset of y edges of v by a binary tree to the respective neighbors
(with additional internal nodes). This reduces the degree of v by y − 2. Repeatedly applying this
procedure in a careful manner results in a graph of constant degree, for which we can still show
our near-linear lower bounds (notice that distances change, as well as the number of nodes). We
exemplify this technique by obtaining the following lower bound on computing the radius.
Theorem 1.5. The number of rounds needed for any protocol to compute the radius of a sparse
network of constant degree in the CON GEST model is Ω(n/ log3 n).
Verification of Spanners Finally, our technique allows us to obtain a lower bound for the
verification of (α, β)-spanners. An (α, β)-spanner of a graph G, is a subgraph H in which for any
two nodes u, v it holds that dH (u, v) ≤ αdG (u, v) + β. When spanners are sparse, i.e., when H does
not have too many edges, they play a vital role in many application, such as routing, approximating
distances, synchronization, and more. Hence, the construction of sparse spanners has been a central
topic of many studies, both in centralized and sequential computing.
Here we address the problem of verifying that a given subgraph H is indeed an (α, β)-spanner
of G. At the end of the computation, each node outputs a bit indicating whether H is a spanner,
with the requirement that if H is indeed a spanner with the required parameters then all nodes
indicate this, and if it is not then at least one node indicates that it is not. We obtain the following.
Theorem 1.6. Given an unweighted graph G = V, E and a subgraph H ⊂ E of G, the number of
rounds needed for any protocol to decide whether H is an (α, β)-spanner of G in the CON GEST
model is Ω( (α+β)nlog3 n ), for any α < β + 1.
Notice that for any reasonable value of α, β = O(poly log n), the lower bound is near-linear. This
is another evidence for a task for which verification is harder than computation in the CONGEST
model, as initially brought into light in [17]. This is, for example, because (+2)-purely additive
√
spanners with O(n3/2 log n) edges can be constructed in O( n log n+D) rounds (this appears in [30],
and can also be deduced from [26]), and additional various additive spanners can be constructed
fast in CONGEST [13].

1.1

Techniques

Communication Complexity and Distributed Computing. A well-known technique to
prove lower bounds in the CON GEST model is to use a reduction from communication complexity to distributed computing. Peleg and Rubinovich [37] apply a lower bound from communication
complexity to show that the number of rounds needed for any distributed algorithm to construct a
e √n + D). Many recent papers were inspired by this technique.
minimum spanning tree (MST) is Ω(
In [19] Elkin extended the result of [37] to show
p nthat any distributed algorithm for constructing an
e
α-approximation to the MST must spend Ω( α ) rounds. Das Sarma et al. [17] show that any distributed verification algorithm for many problems, such as connectivity,√s−t cut and approximating
e √n + D) rounds. Nanongkai et al. [34] showed an Ω( ` · D + D) lower bound for
MST requires Ω(
computing a random walk of length `. Similar reductions from communication complexity were
adapted also in the CON GEST Clique Broadcast model [18, 25], where in each round each node
can broadcast the same O(log n)-bit message to all the nodes in the network.

3

Similar to the technique used in [17, 18, 21, 25, 26], our lower bounds are obtained by reductions
from the Set-Disjointness problem in the two-party number-in-hand model of communication complexity [42]. Here, each of the players Alice and Bob receives a k-bit string, Sa and Sb respectively,
and needs to decide whether the two strings are disjoint or not, i.e., whether there is some bit
0 ≤ i ≤ k − 1 such that Sa [i] = 1 and Sb [i] = 1. A classical result [28, 38] is that in order to solve
the Set-Disjointness problem, Alice and Bob must exchange Ω(k) bits.
The high level idea for applying this lower bound in the CON GEST model, is as follows. We
construct a graph in which the existence of some of the edges depends on the inputs of Alice and
Bob, and we partition the graph between the two players, inducing a cut in it, which we will refer
to as the “communication-cut”. The graph will have some property (e.g. diameter at least 4) if and
only if the two strings of Alice and Bob are disjoint. The players can then simulate a distributed
algorithm (e.g. for diameter), while exchanging only the bits that are sent by the algorithm on edges
that belong to the communication-cut. If our cut has t edges, then Alice on Bob only exchange
O(r · t · log n) bits where r is an upper bound on the round complexity of the algorithm. Therefore,
the lower bound on the communication complexity of Set-Disjointness implies a lower bound on the
number of rounds required for any distributed algorithm (for diameter). Observe that the larger
the communication-cut in the reduction, the smaller the lower bound for the distributed problem.
Having a sparse graph with a small cut, is what allows us to make this leap in the lower bounds.
To achieve this, the key idea is to connect the nodes to a set of nodes that represent their binary
value, and the only nodes on the cut are the nodes of the binary representation. We call this
graph structure a bit-gadget, and it plays a central role in all of our graph constructions. This is
inspired by graph constructions for different settings (e.g. [2], see additional discussion for sequential
algorithms below).

1.2

Additional Related Work

There are many known upper [23, 29, 33] and lower [17, 20, 27, 37] bounds for approximate distance
computation in weighted networks. For example, the weighted diameter of a network with underlying diameter D can be approximated to within (2 + o(1)) in O(n1/2+o(1) + D1+o(1) ) rounds [23].
Moreover, such problems have also been considered in the congested clique model [12,23,33], where
(1 + o(1))-approximate all pairs shortest paths can be computed in O(n0.158 ) rounds [12].
Diameter and Radius in Sequential Algorithms. Intuitively, the technical difficulty in extending the proof for diameter to work for radius as well is the difference in types between the two
problems: the diameter asks for a pair of nodes that are far (∃x∃y) while radius asks for a node that
is close to everyone (∃x∀y). Recent developments in the theory of (sequential) algorithms suggest
that this type-mismatch could lead to fundamental differences between the two problems. Recall
that classical sequential algorithms solve APSP in O(nm) time [16] and therefore both diameter
and radius can be solved in quadratic O(n2 ) time in sparse graphs.
Due to the lack of techniques for proving unconditional super-linear ω(n) lower bounds on the
runtime of sequential algorithms for any natural problem, a recent line of work seeks hardness results
conditioned on certain plausible conjectures (a.k.a. “Hardness in P”). An interesting example of
such result concerns the diameter: Roditty and Vassilevska W. [39] proved that if the diameter of
sparse graphs can be computed in truly-subquadratic O(n2−ε ) time, for any ε > 0, then the Strong
Exponential Time Hypothesis (SETH) is false2 , by reducing SAT to diameter. Since then, many
2

SETH is a pessimistic version of the P 6= NP conjecture, which essentially says that CNF-SAT cannot be solved
in (2 − ε)n time. More formally, SETH is the assumption that there is no ε > 0 such that for all k ≥ 1 we can solve
k-SAT on n variables and m clauses in (2 − ε)n · poly(m) time.

4

other problems were shown to be “SETH-hard” (e.g. [1, 3, 5, 6, 8] to name a few) but whether a
similar lower bound holds for radius is an open question [2, 4, 9, 10, 15, 39]. In fact, Carmosino et
al. [11] show that there is a formal barrier for reducing SAT to radius3 , and Abboud, Vassilevska
W. and Wang [4] introduce a new conjecture to prove an n2−o(1) lower bound for radius4 (which has
a similar ∃∀ type). Diameter and radius seem to behave differently also in the
regime of dense and
√
weighted graphs where the best known algorithms take roughly cubic O(n3 /2 log n ) time [14,40] and
it is known that radius can be solved in truly-subcubic O(n3−ε ) time if and only if APSP can [2], but
showing such a subcubic-equivalence between APSP and diameter is a big open question [2, 7, 41].
The framework and set-up in our unconditional lower bound proofs for distributed algorithms
are very different from the ones in the works on conditional lower bounds for sequential algorithms
discussed above. Still, some of our graph gadgets are inspired by the constructions in those proofs,
e.g. [2, 4, 10, 15, 39]. Thus, it is quite surprising that our hardness proof for diameter transfers
without much difficulty to a hardness proof for radius.

1.3

Model and basic definitions

We consider a synchronized network of n nodes represented by an undirected graph G = (V, E). In
each round, each node can send a different message of b bits to each of its neighbors. This model
is known as the CON GEST (b) model, and as the CON GEST model when b = O(log(n)) [35].
The graph parameters that need to be computed are formally defined as follows.
Definition 1.7. (Eccentricity, Diameter and Radius) Let d(u, v) denote the length of the shortest
path between the nodes u and v. The eccentricity e(u) of some node u is maxv∈V d(u, v). The
Diameter (denoted by D) is the maximum distance between any two nodes in the graph: D =
maxu∈V e(u). The Radius (denoted by r) is the maximum distance from some node to the “center”
of the graph: r = minu∈V e(u).
Finally, we define what we mean when we say that a graph is sparse.
Definition 1.8. (sparse network) A sparse network G = (V, E) is a network with n nodes and at
most O(n log(n)) edges.
Recall, however, that all our results can be obtained for graphs that have a strictly linear number
of Θ(n) edges, at the cost of at most an additional O(log n) factor in the lower bound.
Roadmap. Section 2 contains our lower bound for computing the exact or approximate diameter.
In Sections 3, 4 and 6, we give our lower bounds for computing the exact or approximate radius,
for computing eccentricities, and for verifying spanners, respectively. Section 5 uses our degreereduction technique to show a graph construction with constant degree.

2

Computing the Diameter

In this section we present lower bounds on the number of rounds needed to compute the diameter
exactly and approximately in sparse networks. First, in Section 2.1 we present a higher lower
bound on the number of rounds needed for any algorithm to compute the exact diameter of a
3
It would imply a new co-nondeterministic algorithm for SAT and refute the Nondeterministic-SETH, which is a
strong version of NP 6= CONP.
4
A truly-subquadratic algorithm for computing the radius of a sparse graph refutes the Hitting Set Conjecture:
there is no ε > 0 such that given two lists A, B of n subsets of a universe U of size poly log n we can decide whether
there is a set a ∈ A that intersects all sets b ∈ B in O(n2−ε ) time.

5

sparse network, and next, in Section 2.2 we show how to modify our sparse construction to achieve
a higher lower bound on the number of rounds needed for any algorithm to compute a ( 32 − ε)approximation to the diameter.

2.1

Exact Diameter
𝑏

𝑎

0

F

T

F’

T’

.
.
.

.
.
.

.
.
.

.
.
.

0

log 𝑘 -1

log 𝑘 -1

ℓ0

𝑟0

ℓ1
.
.
.

𝑟1
.
.
.

ℓ𝑘−1

ℓ𝑘+1
ℓ𝑘

𝑟𝑘+1
𝑟𝑘

𝑟𝑘−1

Figure 1: Graph Construction (diameter). Some edges are omitted, for clarity.

Theorem 1.1 The number of rounds needed for any protocol to compute the diameter of a network
on n nodes and O(n log n) edges of constant diameter in the CON GEST model is Ω( logn2 n ).
To prove Theorem 1.1 we describe a graph construction G = (V, E) and a partition of G into
(Ga , Gb ), such that one part is simulated by Alice (denoted by Ga ), and the second is simulated
by Bob (denoted by Gb ). Each player receives an input string defining some additional edges that
will affect the diameter of G. The proof is organized as follows: in Section 2.1.1 we describe the
graph construction, and next, in Section 2.1.2, we describe the reduction from the Set-Disjointness
problem and deduce Theorem 1.1.
2.1.1

Graph construction

Let ij denote the value of the bit j in the binary representation of i. The set of nodes V is defined
as follows (see also Figure 1):5 First, it contains two sets of nodes L = {`i | 0 ≤ i ≤ k − 1} and
R = {ri | 0 ≤ i ≤ k − 1}, each of size k. All the nodes in L are connected to an additional node `k ,
which is connected to an additional node `k+1 . Similarly, all the nodes in R are connected to an
additional node rk , which is connected to an additional node rk+1 . The nodes `k+1 and rk+1 are
also connected by an edge.
5

Note that for the sake of simplicity, some of the edges are omitted from Figure 1.

6

Furthermore, we add four sets of nodes, which are our bit-gadget: F = {fj | 0 ≤ j ≤ log(k) −
1}, T = {tj | 0 ≤ j ≤ log(k) − 1}, F 0 = {fj0 | 0 ≤ j ≤ log(k) − 1}, T 0 = {t0j | 0 ≤ j ≤ log(k) − 1},
each of size log(k). We connect the sets F, T with F 0 , T 0 by adding edges between fi and t0i , and
between ti and fi0 , for each 0 ≤ i ≤ log(k) − 1. To define the connections between the sets L, R
and the sets F, T, F 0 , T 0 , we add the following edges: For each `i ∈ L, if ij = 0, we connect `i to fj ,
otherwise, we connect `i to tj . Similarly, for each ri ∈ R, if ij = 0 we connect ri to fj0 , otherwise,
we connect ri to t0j .
To complete the construction we add two additional nodes {a, b}. We connect a to all the nodes
in F ∪ T ∪ {`k , `k+1 }, and similarly, we connect b to all the nodes in F 0 ∪ T 0 ∪ {rk , rk+1 }. We also
add an edge between the nodes a and b.
Claim 2.1. For every i, j ∈ [k − 1] it holds that d(`i , rj ) = 3 if i 6= j, and d(`i , rj ) = 5 otherwise.
Proof. If i 6= j, there must be some bit h, such that ih 6= j h . Assume without loss of generality
that ih = 1 and j h = 0. Then, `i is connected to th and rj is connected to fh0 . Since th and fh0 are
connected by an edge, d(`i , rj ) = 3. For the second part of the claim, note that there are 4 options
for any shortest path from `i to ri :
1. Through the nodes `k , `k+1 , rk+1 , rk .
2. Through some other node `j ∈ L such that j 6= i in 2 steps, and then using the shortest path
of length 3 between `j and ri .
3. Through some other node rj ∈ R such that j 6= i in 3 steps, and then using the shortest path
of length 2 between rj and ri .
4. Through at least one of the nodes a, b. Note that d(`i , a) = 2 and d(`i , b) = 3. Similarly
d(b, ri ) = 2 and d(a, ri ) = 3.
Thus, any possible shortest path between `i and ri must have length 5.
Claim 2.2. For every u, v ∈ V \ (L ∪ R) it holds that d(u, v) ≤ 3.
Proof. Let u, v ∈ V \ (L ∪ R). By definition, u is connected to one of the nodes in {a, b}. The same
holds for v and since a and b are connected by an edge, d(u, v) ≤ 3.
Corollary 2.3. For every u, v such that u ∈ (Va \ L) or v ∈ (Vb \ R), it holds that d(u, v) ≤ 4.
2.1.2

Reduction from Set-Disjointness

To prove Theorem 1.1, we show a reduction from the Set-Disjointness problem. Following the
construction defined in the previous section, we define a partition (Ga = (Va , Ea ), Gb = (Vb , Eb )):
Va = L ∪ F ∪ T ∪ {`k , `k+1 , a}, Ea = {(u, v)|u, v ∈ Va ∧ (u, v) ∈ E}
Vb = R ∪ F 0 ∪ T 0 ∪ {rk , rk+1 , b}, Eb = {(u, v)|u, v ∈ Vb ∧ (u, v) ∈ E}
The graph Ga is simulated by Alice and the graph Gb is simulated by Bob, i.e., in each round, all
the messages that nodes in Ga send to nodes in Gb are sent by Alice to Bob. Bob forwards these
messages to the corresponding nodes in Gb . All the messages from nodes in Gb to nodes in Ga are
sent in the same manner. Each player receives an input string (Sa and Sb ) of k bits. If the bit
Sa [i] = 0, Alice adds an edge between the nodes `i and `k+1 . Similarly, if Sb [i] = 0, Bob adds an
edge between the nodes ri and rk+1 .
7

Observation 2.4. For every u, v ∈ Va , it holds that d(u, v) ≤ 4. Similarly, d(u, v) ≤ 4 for every
u, v ∈ Vb .
This is because d(ua , `k+1 ) ≤ 2 for any ua ∈ Va , and d(ub , rk+1 ) ≤ 2 for any node ub ∈ Vb .
Lemma 2.5. The diameter of G is at least 5 iff the sets of Alice and Bob are not disjoint.
Proof. Consider the case in which the sets are disjoint i.e., for every 0 ≤ i ≤ k − 1 either Sa [i] = 0
or Sb [i] = 0. We show that for any u, v ∈ V , it holds that d(u, v) ≤ 4. There are 3 cases:
1. u ∈ Va and v ∈ Va : By Observation 2.4, d(u, v) ≤ 4.
2. u ∈ Vb and v ∈ Vb : By Observation 2.4, d(u, v) ≤ 4.
3. u ∈ Va and v ∈ Vb : Consider the case in which u ∈ (Va \ L) or v ∈ (Vb \ R). By Corollary 2.3
d(u, v) ≤ 4. Otherwise, u ∈ L and v ∈ R, and by Claim 2.1 d(`i , rj ) = 3 for every i 6= j.
Note that in case i = j it holds that d(`i , ri ) ≤ 4, since either `i is connected to `k+1 or ri
is connected to rk+1 , and the shortest path between `i and ri is the one through the nodes
`k+1 , rk+1 .
In case the two sets are not disjoint, there is some 0 ≤ i ≤ k − 1 such that Sa [i] = 1 and Sb [i] = 1.
Note that in this case `i is not connected directly by an edge to `k+1 and ri is not connected directly
by an edge to rk+1 . Therefore, there are only 4 options for any shortest path from `i to ri , which
are stated in Claim 2.1, from which we get that in this case the diameter of G is at least 5.
Proof of Theorem 1.1 From Lemma 2.5, we get that any algorithm for computing the exact
diameter of the graph G can be used to solve the Set-Disjointness problem. Note that since there
are O(log(k)) edges in the cut (Ga , Gb ), in each round Alice and Bob exchange O(log(k) · log(n))
bits. Since k = Ω(n) we deduce that any algorithm for computing the diameter of a network must
spend Ω( logn2 (n) ) rounds, and since |E| = O(n log(n)) this bound holds even for sparse networks.

2.2

( 23 − ε)-approximation to the Diameter

In this Section we show how to modify our sparse construction to achieve a stronger lower bound
on the number of rounds needed for any ( 32 − ε)-approximation algorithm.
Theorem 1.2 For all constant 0 < ε < 1/2, the number of rounds needed for any protocol to
compute a (3/2 − ε)-approximation to the diameter of a sparse network is Ω( logn3 n ).
2.2.1

Graph Construction

The main idea to achieve this lower bound is to stretch our sparse construction by replacing some
edges by paths of length P , an integer which will be chosen later. Actually, we only apply the
following changes to the construction described in Section 2.1.1 (see also Figure 2 where P = 3):
1. Remove the nodes a, b and their incident edges.
2. Replace all the edges incident to the nodes `k , rk by paths of length P .
3. Replace all the edges (u, v) such that u ∈ L and v ∈ (F ∪ T ) by paths of length P . Similarly,
Replace all the edges (u, v) such that u ∈ R and v ∈ (F 0 ∪ T 0 ) by paths of length P .

8

0

F

T

F’

T’

.
.
.

.
.
.

.
.
.

.
.
.

0

log n -1

log n -1

ℓ′0

ℓ0

𝑟0

𝑟′0

ℓ′1

ℓ1

𝑟1

𝑟′1

.
.
.

.
.
.

.
.
.

.
.
.

ℓ′𝑘−1

ℓ𝑘−1

𝑟𝑘−1

𝑟′𝑘−1

ℓ𝑘+1
ℓ𝑘

𝑟𝑘+1
𝑟𝑘

Figure 2: Graph construction, P = 3 (diameter approximation). Some edges are omitted.
4. Add two additional sets L0 = {`0i | 0 ≤ i ≤ k − 1}, R0 = {ri0 | 0 ≤ i ≤ k − 1} each of size k.
Connect each `0i to `i , and each ri0 to ri , by a path of length P .
Furthermore, to simplify our proof, we connect each u ∈ (F ∪ T ) to `k+1 by a path of length P .
Similarly, connect each u ∈ (F 0 ∪ T 0 ) to rk+1 by a path of length P .
Definition 2.6. (Y(u,v)) For each u, v ∈ V such that u and v are connected by a path of length
P , denote by Y (u, v) the set of all nodes on the P path between u and v (without u and v).
S
S
Claim 2.7. For every u, v ∈ V \ (L0 ∪ R0 i∈[k−1] Y (`0i , `i ) i∈[k−1] Y (ri0 , ri )) it holds that d(u, v) is
at most 4P + 1.
Proof. By the construction, the distance from u to one of the nodes in {`k+1 , rk+1 } is at most 2P .
The same holds for v. Thus, d(u, v) ≤ 4P + 1.
Claim 2.8. For every i, j ∈ [k − 1] it holds that d(`0i , rj0 ) = 4P + 1 if i 6= j, and d(`0i , rj0 ) = 6P + 1
otherwise.
Proof. If i 6= j, there must be some bit h, such that ih 6= j h . Assume without loss of generality that
ih = 1 and j h = 0. This implies that `i is connected to th by a path of length P and rj is connected
to fh0 by a path of length P as well. Since th and fh0 are connected by an edge, d(`i , rj ) = 2P + 1
and d(`0i , rj0 ) = 4P + 1. For the second part of the claim note that there are 3 options for any
shortest path from `0i to ri0 :
1. Through the node `k+1 in 3P steps, and then using the shortest path of length 3P +1 between
`k+1 and ri0 .
2. Through some other node `j ∈ L, such that j 6= i in 3P steps, and then using the shortest
path of length 3P + 1 between `j and ri0 .
9

3. Through some other node rj ∈ R, such that j 6= i in 3P + 1 steps, and then using the shortest
path of length 3P between rj and ri0 .
Thus, for the second part of the claim, any possible shortest path between (`0i , ri0 ) must have
length 6P + 1.
2.2.2

Reduction from Set-Disjointness

Following the above construction, we define a partition (Ga = (Va , Ea ), Gb = (Vb , Eb )):
[
[
[
Y (`0i , `i )
Va =
Y (`i , fj )
Y (`i , tj )
i∈[k−1]
j∈[log(k)−1]
ij =0

[

i∈[k−1]
j∈[log(k)−1]
ij =1

i∈[k−1]

Y (`i , `k ) ∪ Y (`k , `k+1 ) ∪ L0 ∪ L ∪ F ∪ T ∪ {`k , `k+1 }

i∈[k−1]

Ea ={(u, v)|u, v ∈ Va ∧ (u, v) ∈ E}
[
[
[
Vb =
Y (ri , fj0 )
Y (ri , t0j )
Y (ri0 , ri )
i∈[k−1]
j∈[log(k)−1]
ij =0

[

i∈[k]
j∈[log(k)−1]
ij =1

i∈[k−1]

Y (ri , rk ) ∪ Y (rk , rk+1 ) ∪ R0 ∪ R ∪ F 0 ∪ T 0 ∪ {rk , rk+1 }

i∈[k−1]

Eb ={(u, v)|u, v ∈ Vb ∧ (u, v) ∈ E}
Each player receives an input string (Sa and Sb ) of k bits. If Sa [i] = 0, Alice adds an edge between
the nodes `i and `k+1 . Similarly, if Sb [i] = 0, Bob adds an edge between the nodes ri and rk+1 .
Claim 2.9. Let 0 ≤ i ≤ k − 1 be such that Sa [i] = 0 or Sb [i] = 0. Then the distance from the node
`i ∈ L to any node u ∈ (R ∪ {rk+1 }) is at most 2P + 2.
Proof. There are 3 cases:
1. u = rk+1 : Note that d(`i , `k+1 ) ≤ 2P and d(`i , rk+1 ) ≤ 2P + 1.
2. u = rj ∈ R and j 6= i: By Claim 2.8 d(`i , rj ) = 2P + 1.
3. u = rj ∈ R and j = i: Note that either `i is connected to `k+1 directly by an edge or ri is
connected to rk+1 directly by an edge. Thus, one of the distances d(`i , rk+1 ), d(`k+1 , ri ) must
be equal to 2, and both d(`i , `k+1 ), d(rk+1 , ri ) are at most equal to 2P , thus, d(`i , ri ) ≤ 2P +2.

Note that any node in Vb is connected by a path of length at most P to some node in R∪{rk+1 },
and any node in L0 is connected by a path of length P to some node in L. Combining this with
Claim 2.9 gives the following.
Corollary 2.10. Let 0 ≤ i ≤ k − 1 be such that Sa [i] = 0 or Sb [i] = 0. Then d(u, vb ) ≤ 4P + 2 for
any u ∈ {`0i }∪Y (`0i , `i ) and any vb ∈ Vb . Symmetrically, d(u, va ) ≤ 4P +2 for any u ∈ {ri0 }∪Y (ri0 , ri )
and any va ∈ Va .
Lemma 2.11. The Diameter of G is 6P+1 if the two sets of Alice and Bob are not disjoint, and
4P+2 otherwise.
10

Proof. Consider the case in which the two sets are not disjoint i.e., there is some 0 ≤ i ≤ k − 1 such
that Sa [i] = 1 and Sb [i] = 1. Note that in this case `i is not connected directly by an edge to `k+1
and ri is not connected directly by an edge to rk+1 . Thus, there are only 3 options for any shortest
path from `0i to ri0 , both are stated in Claim 2.8, which implies that in this case d(`0i , ri0 ) = 6P + 1.
Therefore, the diameter of G is at least 6P + 1. Consider the case in which the sets are disjoint
i.e., for each 0 ≤ i ≤ k − 1, either Sa [i] = 0 or Sb [i] = 0, we need to prove that for every u, v ∈ V ,
it holds that d(u, v) ≤ 4P + 2. There are 3 cases:
1. u ∈ Va and v ∈ Va : Note that d(u, `k ) ≤ 2P , the same holds for v. Thus d(u, v) ≤ 4P .
2. u ∈ Vb and v ∈ Vb : Note that d(u, rk ) ≤ 2P , the same holds for v. Thus d(u, v) ≤ 4P .
S
3. u ∈ Va and v ∈ Vb : Consider the case in which u ∈ (Va \ (L0 i∈[k−1] Y (`0i , `i )) and v ∈
S
(Vb \ (R0 i∈[k−1] Y (ri0 , ri ))). By Claim 2.7 d(u, v) ≤ 4P + 1. Otherwise, by Corollary 2.10
d(u, v) ≤ 4P + 2.

Proof of Theorem 1.2 To complete the proof we need to choose P such that ( 23 − ε) · (4P + 2) <
n
1
− 21 . Note that k = Ω( log(n)
(6P + 1), this holds for any P > 2ε
) for a constant ε. Thus, we
3
deduce that any algorithm for computing ( 2 − ε)-approximation to the diameter requires at least
Ω( logn3 (n) ) rounds. Furthermore, the number of nodes and the number of edges are both equal to
Θ(k log(k) · P ). Thus, this lower bound holds even for graphs with linear number of edges.

3

Computing the Radius

In this section we present lower bounds on the number of rounds needed to compute the radius
exactly and approximately in sparse networks.

3.1

Exact Radius

Theorem 3.1. The number of rounds needed for any protocol to compute the radius of a sparse
network of constant diameter in the CON GEST model is Ω(n/ log2 n).
As in the previous sections, first we describe a graph construction, and then apply a reduction
from the Set-Disjointness problem.
3.1.1

Graph construction

The graph construction for the radius is very similar to the one described in Section 2.1.1. We only
apply the following changes to the construction described in Section 2.1.1 (see also Figure 3):6
1. Remove the nodes a, b and their incident edges.
2. For each 0 ≤ i ≤ log(k) − 1 we add an edge between the nodes fi ∈ F and ti ∈ T . Similarly,
we add an edge between fi0 ∈ F 0 and t0i ∈ T 0 .
3. Add a small gadget which connects each `i ∈ L to a new node x3 by a path of length 3
(x1 , x2 , x3 ).
6

Note that for the sake of simplicity, some of the edges are omitted from Figure 3.

11

0

F

T

F’

T’

.
.
.

.
.
.

.
.
.

.
.
.

0

log 𝑘 -1

𝑥3
𝑥2

𝑥1

log 𝑘 -1

ℓ0

𝑟0

ℓ1
.
.
.

𝑟1

ℓ𝑘−1

ℓ𝑘+1

.
.
.

𝑟𝑘+1

ℓ𝑘

𝑟𝑘

𝑟𝑘−1

Figure 3: Graph Construction (radius).
Claim 3.2. For every i, j ∈ [k − 1] it holds that d(`i , rj ) = 3 if i 6= j, and d(`i , rj ) = 4 otherwise.
Proof. If i 6= j, there must be some bit h, such that ih 6= j h . Assume without loss of generality
that ih = 1 and j h = 0. Then, `i is connected to th and rj is connected to fh0 . Since th and fh0
are connected by an edge, d(`i , rj ) = 3. For the second part of the claim, note that all the bits in
the binary representation of i are the same as the bits in the binary representation of j. Thus, for
any edge connecting `i to some node fh ∈ F , the corresponding edge from rj is connected to the
node fh0 ∈ F 0 and not to t0h ∈ T 0 . Similarly, for any edge connecting `i to some node th ∈ T , the
corresponding edge from rj is connected to the node t0h ∈ T 0 and not to fh0 ∈ F 0 . Note that for every
0 ≤ h ≤ log(k) − 1 the nodes fh and fh0 are not connected directly by an edge and d(fh , fh0 ) = 2
(the same holds for th and t0h ). Therefore, d(`i , rj ) = 4 if i = j.
3.1.2

Reduction from Set-Disjointness

The reduction is similar to the one used to prove Theorem 1.1. First we define a partition (Ga =
(Va , Ea ), Gb = (Vb , Eb )):
Va = L ∪ F ∪ T ∪ {`k , `k+1 , x1 , x2 , x3 }
Ea = {(u, v)|u, v ∈ Va ∧ (u, v) ∈ E}
Vb = R ∪ F 0 ∪ T 0 ∪ {rk , rk+1 }
Eb = {(u, v)|u, v ∈ Vb ∧ (u, v) ∈ E}

Each player receives an input string (Sa and Sb ) of k bits. If Sa [i] = 1, Alice adds an edge
between the nodes `i and `k+1 . Similarly, if Sb [i] = 1, Bob adds an edge between the nodes ri and
12

rk+1 . Note that unlike the reduction from Section 2.1.2, here, each player adds some edge if the
corresponding bit in its input string is 1, rather than 0.
Observation 3.3. For every node u ∈ V \ L it holds that e(u) ≥ 4.
Proof. There are two cases:
1. u ∈ V \ (L ∪ {x1 , x2 , x3 }): Note that d(u, x3 ) ≥ 4, since the only nodes that are connected to
x1 are the nodes in L.
2. u ∈ {x1 , x2 , x3 }): Note that d(u, rk ) ≥ 4

Lemma 3.4. The radius of G is 3 if and only if the two sets of Alice and Bob are not disjoint.
Proof. Consider the case in which the two sets are disjoint. Note that for every 0 ≤ i ≤ k − 1,
it holds that d(`i , ri ) = 4, since either `i is not connected directly by an edge to `k+1 or ri is not
connected directly by an edge to rk+1 . Combining this with Observation 3.3 and Claim 3.2 we get
that for every u ∈ V , e(u) ≥ 4. Thus, the radius of G is at least 4 as well. In case the two sets
are not disjoint, i.e., there is some 0 ≤ i ≤ k − 1 such that Sa [i] = 1 and Sb [i] = 1, we show that
e(`i ) = 3: From Claim 3.2, for every 0 ≤ j ≤ k − 1 such that i 6= j, it holds that d(`i , rj ) = 3,
and since Sa [i] = 1 and Sb [i] = 1, it holds that d(`i , ri ) = 3 as well (the path through the nodes
`k+1 and rk+1 ). It is straightforward to see that for every u ∈ V \ R, it holds that d(`i , u) ≤ 3.
Therefore, the radius of G is minu∈V e(u) which is e(`i ) = 3.
Proof of Theorem 3.1 From Lemma 3.4, we get that any algorithm for computing the exact
radius of the graph G solves the Set-Disjointness problem. Note that as the construction described
in Section 2.1.1, there are O(log(k)) edges in the cut (Ga , Gb ). Thus, in each round Alice and Bob
exchange O(log(k) · log(n)) bits. Since k = Ω(n) we deduce that any algorithm for computing the
exact radius of a network must spend Ω( logn2 (n) ) rounds, and since |E| = O(n log(n)) this lower
bound holds even for sparse networks.

3.2

( 23 − ε) approximation to the Radius

We now show how to extend the construction described in Section 2.2.1 to achieve the same asymptotic lower bound for any ( 23 − ε)-approximation algorithm to the radius as well.
Theorem 1.3 For all constant 0 < ε < 1/2, the number of rounds needed for any protocol to
compute a (3/2 − ε)-approximation to the radius of a sparse network is Ω( logn3 n ).
3.2.1

Graph construction

Let G = (V, E) be the graph construction described in section 2.2.1. We describe the construction
for this section in two steps. In the first step, we apply the following changes to G:
1. Replace the path of length P connecting `k to `k+1 by a path of length 2P . Similarly, replace
the path of length P connecting rk to rk+1 by a path of length 2P .
2. Remove all the paths of length P connecting `k+1 with some node u ∈ (F ∪ T ). Similarly,
remove all the paths of length P connecting rk+1 with some node u0 ∈ (F 0 ∪ T 0 ).

13

P

P

𝐿1

ℓ(𝑘+1,1)
P

P

𝐿2

2P

2P

𝑅1

P

𝑅′1

P

𝑟(𝑘,1)

𝐹2 ∪ 𝑇2 ∪ 𝐹2′ ∪ 𝑇2′

P

𝑅2

𝑟(𝑘+1,2)

ℓ(𝑘+1,2)
P

P

𝑟(𝑘+1,1)

ℓ(𝑘,1)

𝐿′

P

𝐹1 ∪ 𝑇1 ∪ 𝐹1′ ∪ 𝑇1′

2P

2P

ℓ(𝑘,2)

P

𝑅′2

P

𝑟(𝑘,2)

Figure 4: Graph Construction (radius approximation). Each edge between two sets of nodes
represents all the edges between the corresponding sets.
S
Let V 0 denote the set of vertices V \ (L0 i∈[k−1] Y (`0i , `i )), and let G0 be the graph induced by
the vertices in V 0 . Now we can describe the second step, in which we extend the construction in the
following manner: we have two instances of G0 , denoted by G01 = (V10 , E10 ) and G02 = (V20 , E20 ). Each
node in G01 ∪ G02 has an additional label, indicating whether it belongs to G01 or G02 . For example,
the node `i in G01 is denoted by `(i,1) , and the node ri in G02 is denoted by r(i,2) . To complete the
construction, for each 0 ≤ i ≤ k − 1 we add two paths, each of length P , connecting `0i to the nodes
`(i,1) , `(i,2) .
3.2.2

Reduction from Set-disjointness

The reduction is similar to the one used to prove Theorem 1.2. First we define a partition (Ga =
(Va , Ea ), Gb = (Vb , Eb )), let Va0 be the set of vertices defined by:
Va0 = L0 ∪ L1 ∪ L2 ∪ F1 ∪ F2 ∪ T1 ∪ T2 ∪ {`(k,1) , `(k+1,1) , `(k,2) , `(k+1,2) }

Similarly, let Vb0 be the set of vertices defined by:
Vb0 = R1 ∪ R2 ∪ R10 ∪ R20 ∪ F10 ∪ F20 ∪ T10 ∪ T20 ∪ {r(k,1) , r(k+1,1) , r(k,2) , r(k+1,2) }

Now we define the sets Va , Ea , Vb , Eb :

14

Va = Va0

[

Y (u, v)

u,v∈Va0

Ea = {(u, v)|u, v ∈ Va ∧ (u, v) ∈ E}
[
Vb = Vb0
Y (u, v)
u,v∈Vb0

Eb = {(u, v)|u, v ∈ Vb ∧ (u, v) ∈ E}

Each player receives an input string (Sa and Sb ) of k bits. If Sa [i] = 1, Alice adds two paths,
each of length P , the first connects the nodes `(i,1) and `(k+1,1) , and the second connects the nodes
`(i,2) and `(k+1,2) . Similarly, if Sb [i] = 1, Bob adds two paths of length P , the first connects the
nodes r(i,1) , and r(k+1,1) and the second connects the nodes r(i,2) and r(k+1,2) .
Observation 3.5. The node with the minimum eccentricity is in L’.
S
This is because for any node u ∈ V10 i∈[k−1] Y (`0i , `(i,1) ) it holds that the node with maxv∈V d(u, v)
S
must be in V20 . Similarly, for any node u ∈ V20 i∈[k−1] Y (`0i , `(i,2) ) it holds that the node with
maxv∈V d(u, v) must be in V10 . Thus, any node u ∈ V \ L0 must visit some node in L0 in order to
reach the node with maxv∈V d(u, v).
Observation 3.6. For any 0 ≤ i ≤ k − 1 and any u ∈ Va , it holds that d(`0i , u) ≤ 4P .
This is because the distance from any u ∈ Va to one of the nodes {`(k,1) , `(k,2) } is at most 2P ,
and d(`0i , `(k,1) ) = d(`0i , `(k,2) ) = 2P for any 0 ≤ i ≤ k − 1.
0
Claim 3.7. Let 0 ≤ i ≤ k − 1 be such that Sa [i] = 0 or Sb [i] = 0. It holds that d(`0i , r(i,1)
) ≥ 6P + 1.
0
0
Similarly, d(`i , r(i,2) ) ≥ 6P + 1 as well.

Proof. Note that either `(i,1) is not connected to `(k+1,1) by a path of length P or r(i,1) is not
connected to r(k+1,1) by a path of length P . Thus, there are three options for any shortest path
0
between `0i and r(i,1)
:
1. Through the nodes `(k+1,1) , r(k+1,1) : In this case, the shortest path must visit at least one of
the nodes `(k,1) , r(k,1) . Assume without loss of generality that the shortest path visits only
0
`(k,1) . Thus, the distance between `0i and r(i,1)
can be written as the sum of two distances:
0
0
0
0
0
d(`i , r(i,1) ) = d(`i , `(k,1) ) + d(`(k,1) , r(i,1) ). Note that d(`(k,1) , r(i,1)
) ≥ 4P + 1(and equals 4P + 1
0
0
0
if Sb [i] = 1), and d(`i , `(k,1) ) = 2P . Thus, we have d(`i , r(i,1) ) ≥ 2P + 4P + 1 = 6P + 1.
2. Through some other node `(j,1) ∈ L1 such that j 6= i in 3P steps, and then using the shortest
0
path of length 3P + 1 between `(j,1) and r(i,1)
.
3. Through some other node r(j,1) ∈ L1 such that j 6= i in 3P + 1 steps, and then using the
0
shortest path of length 3P between r(j,1) and r(i,1)
.
0
Thus, d(`0i , r(i,1)
) = 6P + 1, and similarly, d(`0i , r0 (i, 2)) = 6P + 1 as well.

Combining Claim 3.7 with Observation 3.5, we conclude the following.
Corollary 3.8. The radius of G ≥ 6P + 1 if the two sets of Alice and Bob are disjoint.
15

Claim 3.9. Let 0 ≤ i ≤ k − 1 be such that Sa [i] = 1 and Sb [i] = 1. Then the distance from `0i to
any node in Vb is at most 4P + 1.
Proof. Note that `(i,1) is connected to `(k+1,1) by a path of length P and r(i,1) is connected to
r(k+1,1) by a path of length P . Similarly, `(i,2) is connected to `(k+1,2) by a path of length P and
r(i,2) is connected to r(k+1,2) by a path of length P . Thus, the distance from `0i to each of the nodes
r(k+1,1) , r(k+1,2) is 2P + 1, and d(`0i , v) ≤ 4P + 1 for any v ∈ (Y (r(k,1) , r(k+1,1) ) ∪ Y (r(k,2) , r(k+1,2) )).
It remains to show that d(`0i , v) ≤ 4P + 1 for any v ∈ Vb \ (Y (r(k,1) , r(k+1,1) ) ∪ Y (r(k,2) , r(k+1,2) )).
Note that `0i can reach any node in R1 ∪ R2 in 3P + 1 steps. Furthermore, by the definition of the
construction, for any v ∈ Vb \(Y (r(k,1) , r(k+1,1) )∪Y (r(k,2) , r(k+1,2) )) there is some node u ∈ (R1 ∪R2 ),
such that d(v, u) = P . Thus, for any v ∈ Vb \ (Y (r(k,1) , r(k+1,1) ) ∪ Y (r(k,2) , r(k+1,2) )) it holds that
d(`0i , v) ≤ 4P + 1.
Combining Observation 3.5, Observation 3.6, Corollary 3.8 and Claim 3.9, we conclude the
following.
Lemma 3.10. The Radius of G is 4P+1 if the two sets of Alice and Bob are not disjoint, and at
least 6P+1 otherwise.
Proof of Theorem 1.3 To deduce Theorem 1.3 we need to choose P such that ( 32 −ε)·(4P +1) <
1
n
(6P + 1), this holds for any P > 8ε
) for a constant ε. Thus, we deduce
− 14 . Note that k = Ω( log(n)
3
that any algorithm for computing a ( 2 − ε)-approximation to the radius requires at least Ω( logn3 (n) )
rounds. Furthermore, the number of nodes and the number of edges are both equal to Θ(k log(k)·P ).
Thus, this lower bound holds even for graphs with linear number of edges.

3.3

Shaving an Extra Logarithmic Factor from the Denominator

In this section we show how to modify the construction described in Section 3.1.1 to achieve higher
lower bounds for computing the radius exactly and approximately. The general idea is to expand
the input strings of Alice and Bob while preserving the (asymptotic) size of the cut. We apply the
following changes to the construction described in Section 3.1.1 (see also Figure 5):
1. Replace the node `k+1 by a set of nodes {`jk+1 | 0 ≤ j ≤ log(k) − 1} of size log(k). Similarly,
j
replace the node rk+1 by a set of nodes {rk+1
| 0 ≤ j ≤ log(k) − 1} of size log(k).
j
2. Connect each `jk+1 with rk+1
by an edge.

For the graph partition, we add to Va the nodes {`jk+1 | 0 ≤ j ≤ log(k) − 1} and we add to Vb
j
the nodes {rk+1
| 0 ≤ j ≤ log(k) − 1}. The input to the set-disjointness problem now differs from
the previous construction, as follows. Each of the players Alice and Bob receives an input string
(Sa , Sb ) of size k log(k), each bit is represented by two indices i, j such that i ∈ {0, .., k − 1} and
j ∈ {0, ..., log(k) − 1}. If the bit Sa (i, j) = 1 Alice adds an edge between the nodes `i and `jk+1 .
j
Similarly, If the bit Sb (i, j) = 1 Bob adds an edge between the nodes ri and rk+1
. Note that if
the two sets of Alice and Bob are disjoint, then for each 0 ≤ i ≤ k − 1 it holds that d(`i , ri ) = 4.
Otherwise, there is some 0 ≤ i ≤ k − 1 such that d(`i , ri ) = 3. Thus, one can prove by case
analysis, that the radius of G is 3 if and only if the two sets of Alice and Bob are not disjoint. Note
that the size of the cut (Ga , Gb ) remains Θ(log(k)), k remains Θ(n), and the size of the strings is
Θ(n log(n)). Thus, we achieve the following:

16

𝐹 ∪ 𝑇 ∪ 𝐹 ′ ∪ 𝑇′
𝑥3
𝑥2

𝑥1

ℓ0

𝑟0

ℓ1
.
.
.

𝑟1

ℓ𝑘−1

ℓ𝑘

ℓ0𝑘+1

0
𝑟𝑘+1

ℓ1𝑘+1
.
.
.

1
𝑟𝑘+1
.
.
.

𝑧
ℓ𝑘+1

𝑧
𝑟𝑘+1

.
.
.
𝑟𝑘

𝑟𝑘−1

Figure 5: Graph Construction (radius), z = log(k) − 1. Some edges are omitted, for clarity.
Theorem 3.11. The number of rounds needed for any protocol to compute the radius of a sparse
network of constant diameter in the CON GEST model is Ω(n/ log n).
Similarly, we can apply the same idea to the construction described in Section 3.2.1 and achieve
the following theorem:
Theorem 3.12. The number of rounds needed for any protocol to compute a (3/2−ε)-approximation
to the radius of a sparse network is Ω(n/ log2 n).

Computing a ( 53 − ε)-approximation to the Eccentricity

4

In this section we show that any algorithm for computing a ( 53 − ε)-approximation to all the
eccentricities must spend Ω( logn3 (n) ) rounds. Similar to the previous sections, we define a graph
construction, and then apply a reduction from the set-disjointness problem.

4.1

Graph Construction

We simply apply the following changes on the construction described in Section 2.2.1 (see also
Figure 6):
S
1. Remove all the nodes in L0 i∈[k−1] Y (`0i , `i ) and their incident edges.
2. Remove all the paths of length P connecting `k+1 with some node u ∈ (F ∪ T ). Similarly,
remove all the paths of length P connecting rk+1 with some node u0 ∈ (F 0 ∪ T 0 ).
17

0
P

F

T

F’

T’

.
.
.

.
.
.

.
.
.

.
.
.

0

log 𝑘 -1

ℓ0

P

ℓ1

P

.
.
.
ℓ𝑘−1

log 𝑘 -1

P

ℓ𝑘+1

P

𝑟0

P

𝑟′0

P

𝑟1

P

𝑟′1

P

.
.
.

P

𝑟𝑘−1

𝑟𝑘+1

2P
P

P

2P

ℓ𝑘

𝑟𝑘

.
.
.
P

𝑟′𝑘−1

Figure 6: Graph construction (( 53 − ε)-approximation to Eccentricity).
3. Replace the path of length P connecting `k to `k+1 by a path of length 2P . Similarly, replace
the path of length P connecting rk to rk+1 by a path of length 2P .

4.2

Reduction from Set-disjointness

Each player receives an input string (Sa and Sb ) of k bits. If Sa [i] = 1, Alice adds a path of length
P connecting the nodes `i and `k+1 . Similarly, if Sb [i] = 1, Bob adds a path of length P connecting
the nodes ri and rk+1 .
Lemma 4.1. There is some node `i ∈ L with eccentricity 3P + 1 if and only if the two sets of Alice
and Bob are not disjoint, otherwise, the eccentricity of each node in L is 5P + 1.
Proof. Consider the case that the sets are disjoint i,e., for every 0 ≤ i ≤ k − 1 either `i is not
connected to `k+1 by a path of length P or ri is not connected to rk+1 by a path of length P . Thus,
there are only 3 options for any shortest path from `i to ri0 :
1. (Sa [i] = 0 and Sb [i] = 0) Through some other node `j such that i 6= j in 2P steps, and then
using the shortest path of length 3P + 1 from `j to ri0 . Or Through some other node rj such
that i 6= j in 2P + 1 steps, and then using the shortest path of length 3P from rj to ri0 .
2. (Sa [i] = 1 and Sb [i] = 0) Through the node `k+1 in P steps, and then using the shortest path
of length 4P + 1 from `k+1 to ri0 .
3. (Sa [i] = 0 and Sb [i] = 1) Through the node rk+1 in 3P + 1 steps, and then using the shortest
path of length 2P from rk+1 to ri0 .
In case the two sets are not disjoint, there is some 0 ≤ i ≤ k − 1 such that `i is connected to `k+1
by a path of length P and ri is connected to rk+1 by a path of length P . Thus, the distance from
18

`i to any of the nodes in R is 2P + 1, and to any of the nodes in R0 is 3P + 1. It is straightforward
to see, by the definition of the construction, that the distance from `i to any node in V \ R0 is at
most 3P + 1 as well.

Theorem 1.4 For all constant 0 < ε < 2/3, the number of rounds needed for any protocol to
compute a (5/3 − ε)-approximation of all eccentricities of a sparse network is Ω( logn3 n ).
Proof of Theorem 1.4 To complete the proof we need to choose P such that ( 35 − ε) · (3P + 1) <
2
n
(5P + 1), this holds for any P > 9ε
) for a constant ε. Thus, we deduce
− 13 . Note that k = Ω( log(n)
5
that any algorithm for computing a ( 3 − ε)-approximation to all the eccentricities requires at least
Ω( logn3 (n) ) rounds.

5

Networks with ∆ = 5

In this section we show how to modify our construction for radius computation to achieve almost
the same lower bound for networks with ∆ = 5, where ∆ is the maximum degree of the network.
Similar modification can be applied to the construction of the diameter as well. Consider the
construction described in section 3.1. For each node v ∈ V such that v has a large degree, we
replace a subset of the edges incident to v by a binary tree (see also Figure 7). For example,
consider the node `0 . Instead of connecting `0 to each of its neighbors in F ∪ T directly by edges,
we add a binary tree of size O(log(k)), whose root is `0 and whose leaves are the corresponding
nodes in F ∪ T . Note that there are O(k) nodes with degree O(log(k)) and O(log(k)) nodes with
degree O(k) in the original graph.

𝑢1

𝑤1

𝑤2

𝑢2

𝑤2

.
.
.

.
.
.

.
.
.

𝑢𝑦

𝑤𝑧

𝑤𝑧

𝑣

𝑢1
𝑢2
𝑣

.
.
.

𝑤1

.
.
.
𝑢𝑦

Figure 7: Replacing y edges connected to some node v of degree y + z by a binary tree of size O(y).
Thus, the degree of v becomes z + 2.

19

Theorem 1.5 The number of rounds needed for any protocol to compute the radius of a sparse
network of constant degree in the CON GEST model is Ω(n/ log3 n).
Now we describe the changes we apply to the construction described in Section 3.1.1 formally
by 10 steps:
1. Remove the node x3 and its incident edge.
2. Replace the edges between x1 and L by a binary tree of size O(k) such that x1 is the root
and the leaves are the nodes in L. Note that the height of this tree is exactly log(k).
3. Replace the edge (x1 , x2 ) by a path of length log(k) + 2 log log(k) − 1. Denote the set of all
the nodes on this path, including x1 and x2 , by P (x1 , x2 ).
4. Remove all the edges connecting some node in L ∪ R with some node in the bit-gadget.
5. Connect each `i in L to all the nodes that represent its binary value by a binary tree of
size O(log(k)), such that `i is the root and the leaves are the corresponding nodes in F ∪ T .
Similarly, connect each ri in R to all the nodes that represent its binary value by a binary
tree of size O(log(k)), such that ri is the root and the leaves are the corresponding nodes in
F 0 ∪ T 0 . Note that the height of each such tree is exactly log log(k).
6. After the previous step, each of the nodes in the bit-gadget is a leaf in k trees, thus, we replace
each u in the bit-gadget by a binary tree of size O(k) such that the root is u and the leaves are
its k parents in the k binary trees. Note that the height of each such tree is exactly log(k).
Thus, after this step, the distance between `0 and f0 , for example, is log log(k) + log(k) − 1
and not log log(k) + log(k). This is because the parents of the leaves in the tree rooted at `0
are leaves in the trees rooted at the corresponding nodes in F ∪ T .
7. Replace the edges in {(`i , `k ) | 0 ≤ i ≤ k − 1} ∪ {(ri , rk ) | 0 ≤ i ≤ k − 1} by paths of length
log log(k) − 1. Denote by P (`k ) the set of all the nodes on the paths connecting `k to the
nodes in L, including the nodes in L and the node `k . Similarly, denote by P (rk ) the set of
all the nodes on the paths connecting rk to the nodes in R, including the nodes in R and the
node rk .
8. Replace the set of the first edges on every path that connects `k to the nodes in L (i.e.,
the k edges that are incident to `k ) by a binary tree of size O(k) and height exactly log(k).
Similarly, replace set of the first edges on every path that connects rk to the nodes in R
(i.e., the k edges that are incident to rk ) by a binary tree of size O(k) and height exactly
log(k). Note that the edges (`k , `k+1 ) and (rk , rk+1 ) remain the same. Thus, after this step,
the distance between `0 and `k , for example, is log log(k) + log(k) − 1, and thus, the distance
between `0 and `k+1 is log log(k) + log(k).
9. Connect the node `k+1 to each of the nodes in L by a new path of length log log(k) − 1, for
each `i . Denote by q(`i ) the neighbor of `i in the corresponding path of size log log(k) − 1
connecting `i to `k+1 . Similarly, connect the node rk+1 to each of the nodes in R by a
new path of length log log(k) − 1, and for each ri , denote by q(ri ) the neighbor of ri in the
corresponding path of size log log(k) − 1 connecting ri to rk+1 . Denote by P (`k+1 ) the set of
all the nodes on the paths connecting `k+1 to the nodes in L, including the nodes in L and
the node `k+1 . Similarly, Denote by P (rk+1 ) the set of all the nodes on the paths connecting
rk+1 to the nodes in R, including the nodes in R and the node rk+1 .
20

10. Replace the set of the first edges on every path that connects `k+1 to the nodes in L(i.e., the
k edges that are incident to `k+1 ) by a binary tree of size O(k) and height exactly log(k).
Similarly, replace the first edges on every path that connects rk+1 to the nodes in R(i.e., the
k edges that are incident to rk+1 ) by a binary tree of size O(k) and height exactly log(k).
We note that we keep the edges between the nodes fi ∈ F and ti ∈ T and the edges between
the nodes fi0 ∈ F 0 and t0i ∈ T 0 for each 0 ≤ i ≤ log(k) − 1 as in Section 3.1. For each v ∈ V such
that v is a root of some binary tree in G, denote by T (v) the set of all nodes in the binary tree
rooted at v not including v itself.
Claim 5.1. The maximum degree in the graph is 5.
Proof. We show that for each v ∈ V the degree of v is at most 5. There are 7 cases:
1. v ∈ {`k+1 , rk+1 }: Note that `k+1 is a root of a binary tree, and other than nodes in T (`k+1 ),
it is connected only to the nodes `k and rk+1 , thus the degree of `k+1 is 4. A similar argument
holds for rk+1 .
2. v ∈ {`k , rk }: Note that `k is a root of a binary tree, and other than nodes in T (`k ), it is
connected only to the node `k+1 , thus, the degree of `k is 3. A similar argument holds for rk
as well.
3. v ∈ L ∪ R: Note that for each `i ∈ L, it holds that `i is a root of a binary tree, and it is a
leaf in the binary tree rooted at x1 . In addition, it is connected to q(`i ) and to another node
connecting it to a path of length log log(k) − 1, which is connected to the binary tree rooted
at `k . Thus, its degree is 5. The same holds for each ri ∈ R.
4. v ∈ P (x1 , x2 ): If v ∈ P (x1 , x2 ) \ {x1 } then v is of degree 2. Otherwise, the degree of x1 is 3,
since it is a root of a binary tree and it is connected to another node on the path P (x1 , x2 ).
5. v ∈ bit-gadget: Note that v is a root of a binary tree and it is connected to two additional
nodes in the bit-gadget. Thus, its degree is 4.
6. v is an inner node in some binary tree: The degree of an inner node in a binary tree is at
most 3.
7. v ∈ P (`k ) ∪ P (rk ) ∪ P (`k+1 ) ∪ P (rk+1 ) \ (L ∪ R): All the nodes on these paths are of degree 2.

5.1

Reduction from Set Disjointness

Each player receives an input string (Sa and Sb ) of k bits. If Sa [i] = 0, Alice removes the edge
connecting `i to q(`i ). Similarly, if Sb [i] = 0, Bob removes the edge connecting ri to q(ri ).
Claim 5.2. For every 0 ≤ i, j ≤ k − 1 such that i 6= j, it holds that d(`i , rj ) ≤ 2 log log(k) +
2 log(k) − 1.
Proof. If i 6= j, there must be some bit h, such that ih 6= j h . Assume without loss of generality
that ih = 1 and j h = 0. Then, the distance between `i and th is log log(k) + log(k) − 1. Similarly,
the distance between ri and t0h is log log(k) + log(k) − 1. Note that fh and t0h are connected by an
edge. Thus, d(`i , rj ) ≤ 2 log log(k) + 2 log(k) + 2(−1) + 1 = 2 log log(k) + 2 log(k) − 1.

21

Claim 5.3. If 0 ≤ i ≤ k−1 is such that Sa [i] = 0 or Sb [i] = 0, then d(`i , ri ) ≥ 2 log log(k)+2 log(k).
Otherwise, d(`i , ri ) = 2 log log(k) + 2 log(k) − 1.
Proof. If 0 ≤ i ≤ k − 1 is such that Sa [i] = 0 or Sb [i] = 0, then either `i is not connect to
q(`i ) directly by an edge, or ri is not connect to q(`i ) directly by an edge. Thus, similar to the
previous constructions there are two options for any shortest path between `i and ri . The first
is through the bit-gadget and the second is through the nodes `k+1 , rk+1 , and both of them must
have length at least 2 log log(k) + 2 log(k). Otherwise, in case Sa [i] = 1 and Sb [i] = 1 it holds
that d(`i , `k+1 ) = log log(k) + log(k) − 1. Similarly, d(ri , rk+1 ) = log log(k) + log(k) − 1. Thus,
d(`i , ri ) = 2 log log(k) + 2 log(k) − 1.
Claim 5.4. If 0 ≤ i ≤ k − 1 is such that Sa [i] = 1 and Sb [i] = 1, then e(`i ) = 2 log log(k) +
2 log(k) − 1.
Proof. We show that for any v ∈ V , it holds that d(`i , v) ≤ 2 log log(k) + 2 log(k) − 1. There are 2
cases:
1. v ∈ Va : Here, there are 7 sub-cases:
(a) v ∈ {`k , `k+1 }: By the construction, d(`i , `k ) = log log(k)+log(k)−1, and since Sa [i] = 1,
it holds that d(`i , `k+1 ) = log log(k) + log(k) − 1 as well.
(b) v ∈ L: In this case, `i can use the node `k in order to reach any node in L by a
path of length 2 log log(k) + 2 log(k) − 2, since the distance between any `i and `k is
log log(k) + log(k) − 1.
(c) v ∈ P (x1 , x2 ) ∪ T (x1 ) \ L: Note that d(`i , x1 ) = log(k), and x1 can reach any node in
T (x1 ) in log(k) steps, and any node in P (x1 , x2 ) in log(k) + 2 log log(k) − 1 steps. Thus,
d(`i , v) ≤ 2 log log(k) + 2 log(k) − 1.
(d) v ∈ F ∪ T : Note that for each 0 ≤ j ≤ log(k) − 1, it holds that the distance from `i
to one of the nodes in {fj , tj } is log log(k) + log(k) − 1, and since we keep the edges
between the nodes fj ∈ F and tj ∈ T for each 0 ≤ j ≤ log(k) − 1, it holds that
d(`i , v) ≤ log(k) + log log(k).
S
S
S
(e) v ∈ i∈[k−1] T (`i ) j∈[log(k)−1] T (fj ) j∈[log(k)−1] T (tj ): Note that v is at distance at
most log(k) + log log(k) − 2 from some node in F ∪ T . In this case d(`i , v) ≤ 2 log(k) +
2 log log(k) − 2 by case 1(d).
(f) v ∈ T (`k ) ∪ P (`k ) \ L: Note that v is at distance at most log(k) + log log(k) − 1 from `k .
In this case, d(`i , v) ≤ 2 log(k) + 2 log log(k) − 2 by case 1(a).
(g) v ∈ T (`k+1 ) ∪ P (`k+1 ) \ L: Note that v is at distance at most log(k) + log log(k) − 1 from
`k+1 . In this case, d(`i , v) ≤ 2 log(k) + 2 log log(k) − 2 by case 1(a).
2. v ∈ Vb : Here, there are 6 cases:
(a) v ∈ {rk , rk+1 }: Since Sa [i] = 1, d(`i , rk+1 ) = d(`i , `k+1 ) + d(`k+1 , rk+1 ) = log log(k) +
log(k), and d(`i , rk ) = log log(k) + log(k) + 1.
(b) v ∈ R: By Claims 5.2 and 5.3, it holds that d(`i , v) = 2 log log(k) + 2 log(k) − 1.
(c) v ∈ F 0 ∪ T 0 : By case 1(d), it holds that d(`i , v) ≤ log(k) + log log(k) + 1.
S
S
S
(d) v ∈ i∈[k−1] T (ri ) j∈[log(k)−1] T (fj0 ) j∈[log(k)−1] T (t0j ): Note that v is at distance at
most log(k) + log log(k) − 2 from some node in F 0 ∪ T 0 . In this case d(`i , v) ≤ 2 log(k) +
2 log log(k) − 1 by case 2(c).
22

(e) v ∈ T (`k ) ∪ P (rk ) \ L: Note that v is at distance at most log(k) + log log(k) − 1 from rk .
In this case d(`i , v) ≤ 2 log(k) + 2 log log(k) − 1 by case 2(a).
(f) v ∈ T (`k+1 ) ∪ P (rk+1 ) \ L: Note that v is at distance at most log(k) + log log(k) − 1 from
rk+1 . In this case d(`i , v) ≤ 2 log(k) + 2 log log(k) − 1 by case 2(a).

Lemma 5.5. If the two sets of Alice and Bob are disjoint, then the radius of G is at least
2 log log(k) + 2 log(k). Otherwise, there is some 0 ≤ i ≤ k − 1 such that Sa [i] = 1 and Sb [i] = 1 and
the radius of G is at most e(`i ) ≤ 2 log log(k) + 2 log(k) − 1.
Proof. Consider the case in which the two sets are not disjoint. By Claim 5.3, for all the nodes in
L, it holds that d(`i , ri ) ≥ 2 log log(k) + 2 log(k). Note that for all the nodes u ∈ V \ (L ∪ T (x1 ) ∪
P (x1 , x2 )), it holds that d(u, x2 ) ≥ 2 log log(k)+2 log(k), and for all the nodes u ∈ T (x1 )∪P (x1 , x2 )
it holds that d(u, ri ) ≥ 2 log log(k) + 2 log(k) for each 0 ≤ i ≤ k − 1. Thus, the radius of G is at least
2 log log(k) + 2 log(k) as well. The second part of the claim follows directly from Claim 5.4.
Proof of Theorem 1.5 As described before, we add O(k) binary trees of size O(log(k)), and
O(log(k)) binary trees of size O(k), and O(k) paths of size O(log log(k)). Thus the total number
n
of nodes added to the construction described in Section 3.1 in O(k log(k)). Thus, k = Ω( log(n)
)
n
and by Lemma 5.5 that any algorithm for computing the radius of G requires at least Ω( log3 (n) )
rounds, even in graphs with ∆ = 5.
Remark 5.6. We remark that we believe that by a simple modification we can obtain the same
result for graphs with maximum degree 3. This is done by replacing each node of degree 4 by 2
nodes, each of degree 3, and by replacing each node of degree 5 by 3 nodes, each with degree 3.

6

Verification of Spanners

In this section we show that verifying an (α, β)-spanner is also a hard task in the CON GEST
model.
Theorem 1.6 Given an unweighted graph G = V, E and a subgraph H ⊂ E of G, the number of
rounds needed for any protocol to decide whether H is an (α, β)-spanner of G in the CON GEST
model is Ω( (α+β)nlog3 n ), for any α < β + 1.
In particular, this gives a near-linear lower bound when α, β are at most polylogarithmic in n.

6.1

Graph Construction

Let P = αx + β. For our proof for unweighted graphs we need x to be equal to 1. However, we keep
the notation x to prove the same lower bound for weighted graphs as well. We apply the following
changes to the construction described in Section 3 (see also Figure 8):7
1. Remove the nodes {x1 , x2 , x3 } and their incident edges.
2. Remove the nodes {`k , rk } and their incident edges.
7

Some of the edges are omitted, for clarity.

23

ℓ𝑘+2

F

T

F’

T’

.
.
.

.
.
.

.
.
.

.
.
.

ℓ0

𝑟0

ℓ1
.
.
.

𝑟1
.
.
.

𝑟𝑘+1

ℓ𝑘+1

ℓ𝑘−1

𝑟𝑘+2

𝑟𝑘−1

Figure 8: Graph Construction (spanner verification).
3. Remove all the edges (u, v) such that u ∈ F and v ∈ T . Similarly, Remove all the edges (u, v)
such that u ∈ F 0 and v ∈ T 0 .
4. Replace all the edges (u, v) such that u ∈ L and v ∈ (F ∪ T ) by paths of length P2 . Similarly,
Replace all the edges (u, v) such that u ∈ R and v ∈ (F 0 ∪ T 0 ) by paths of length P2 .
5. Connect each `i ∈ L to `k+1 by a path of length P . Similarly, Connect each ri ∈ R to rk+1
by a path of length P .
6. Add two additional nodes {`k+2 , rk+2 }. Connect `k+2 to each of the nodes in L by a path of
length P2 . Similarly, connect rk+2 to each of the nodes in R by a path of length P2 .
The following Observation follows directly from the construction and the discussions in previous
sections.
Observation 6.1. For every 0 ≤ i, j ≤ k − 1 such that i 6= j, it holds that d(`i , rj ) = αx + β + 1.
Otherwise, d(`i , ri ) = 2(αx + β) + 1.

6.2

Reduction from Set-Disjointness

Each player receives an input string (Sa and Sb ) of k bits. If Sa [i] = 1, Alice adds a path of length
x between the nodes `i and `k+1 . Similarly, if Sb [i] = 1, Bob adds a path of length x between the
nodes ri and rk+1 . Denote by Dist the set of all the edges that are added according to the strings
of Alice and Bob. Now we define the subgraph H to be E \ Dist. Let dG (u, v) denote the distance
between the nodes u and v in G. Similarly, let dH (u, v) denote the distance between the nodes u
and v in H.
Lemma 6.2. If there is some 0 ≤ i ≤ k − 1 such that Sa [i] = 1 and Sb [i] = 1, then H is not an
(α, β) spanner of G for any α < β + 1.
24

Proof. According to Observation 6.1, it holds that dH (`i , ri ) = 2(αx + β) + 1, while dG (`i , ri ) =
2x + 1. And since α(2x + 1) + β < 2(αx + β) + 1 for any α < β + 1, it holds that H is not an (α, β)
spanner of G.
Lemma 6.3. If the two sets of Alice and Bob are disjoint, then H is an (α, β) spanner of G for
any α ≥ 1.
Proof. We show that dH (u, v) ≤ αdG (u, v) + β for any u, v ∈ V .
1. u = `i ∈ L and v = rj ∈ R such that i 6= j: Note that dG (`i , rj ) = min(2x+1, αx+β+1), while
dH (`i , rj ) = αx + β + 1 by Observation 6.1. Thus, the problematic case is when dG (`i , rj ) =
2x + 1, for which α(dG (`i , rj )) + β ≥ α(2x + 1) + β = 2αx + α + β ≥ αx + β + 1 = dH (`i , rj )
for any α ≥ 1.
2. u = `i ∈ L and v = rj ∈ R such that i = j: Note that dG (`i , ri ) ≥ x + αx + β + 1, since either
`i is not connected to `k+1 by a path of length x, or ri is not connected to rk+1 by a path of
length x. While dH (`i , ri ) = 2(αx + β) + 1 by Observation 6.1. Note that α(dG (`i , ri )) + β ≥
α(x+αx+β +1)+β ≥ αx+α2 x+αβ +α+β ≥ αx+αx+β +1+β ≥ 2(αx+β)+1 = dH (`i , ri ),
for any α ≥ 1.
3. u ∈ Va and v ∈ Va : Here, there are two cases:
(a) The shortest path in G does not visit the node `k+1 . In this case dG (u, v) = dH (u, v).
(b) The shortest path in G visits the node `k+1 , thus, it visits some node `i . In this case
dG (u, v) can be written as the sum of three distances, dG (u, v) = dG (u, `i )+dG (`i , `k+1 )+
dG (`k+1 , v), if none of the distances dG (u, `i ), dG (`k+1 , v) is using the disjointness edges,
then the claim holds by the fact that α(dG (`i , `k+1 )) + β ≥ dH (`i , `k+1 ). Otherwise,
dG (u, v) can be written as the sum of three distances, dG (u, v) = dG (u, `i ) + dG (`i , `j ) +
dG (`j , v), note that dG (`i , `j ) ≥ 2x, while dH (`i , `j ) = αx + β (the path through the
node `k+2 ), and the claim holds by the fact that α2x + β ≥ αx + β.
4. u ∈ Vb and v ∈ Vb : This case is symmetric to the previous one.
5. u ∈ Va and v ∈ Vb : Here, there are four cases:
(a) The shortest path in G does not visit the nodes `k+1 , rk+1 . In this case dG (u, v) =
dH (u, v).
(b) The shortest path in G visits only the node `k+1 and does not visit rk+1 : This case is
very similar to the case 3.b.
(c) The shortest path in G visits only the node rk+1 and does not visit `k+1 : This case is
symmetric to the previous case.
(d) The shortest path visits the two nodes `k+1 , rk+1 , thus, it visits some two nodes `i , rj .
In this case dG (u, v) can be written as the sum of three distances, dG (u, v) = dG (u, `i ) +
dG (`i , rj ) + dG (rj , v), in case i 6= j, it holds that α(dG (u, v)) + β ≥ dH (u, v) by the case
in which u = `i ∈ L and v = rj ∈ R such that i 6= j which was proved in the first case of
this proof. Otherwise, α(dG (u, v)) + β ≥ dH (u, v) by the case in which u = `i ∈ L and
v = rj ∈ R such that i = j which was proved in the second case of this proof.

25

Observation 6.4. Note that the number of edges E(G) is equal to Θ(E(H)). However, it is
straightforward to see that by adding a clique of size k to G and connecting it to some arbitrary
node we can control the number of edges in G. We add k additional edges to H in order to span this
clique, giving that the number of edges in G is Θ(n2 ), while the number of edges in H is Θ(n log(n))
(and if β > 2 the number of edges in H is equal to Θ(n)). If we want E(H) to match the known
bounds for the possible sparsity of an (α, β)-spanner for general graphs, we simply add more edges
of the clique to H.
Proof of Theorem 1.6 From the two lemmas 6.2 and 6.3 we deduce that H is an (α, β)-spanner
of G if and only if the two sets of Alice and Bob are disjoint. Note that for unweighted graphs
we need x to be equal to 1, thus, n = O(k · (α + β) log(n)), i.e., k = Ω( (α+β)nlog(n) ), and as
in the previous constructions from the previous sections, the size of the cut is O(log(n)). Thus,
the number of rounds needed for any algorithm to decide whether H is an (α, β)-spanner of G is
n
).
Ω( (α+β)·log
3
(n)
Weighted Graphs In order to achieve a higher lower bound for weighted graphs, we replace all
the P and P2 paths by edges of weights P and P2 respectively. Note that in this case k = Ω(n)
and we deduce that the number of rounds needed for any algorithm to decide whether H is an
(α, β)-spanner of G is Ω( logn2 (n) ).

7

Discussion

We introduce a new technique for reducing the Set-Disjointness communication problem to distributed computation problems, in a highly efficient way. Our reductions encode an instance of
e
Disjointness on k bits into a graph on only O(k)
nodes and edges with a small “communication-cut”
of size O(log k). All previous lower bound constructions had a cut of poly(k) size (e.g., [17,21,25,26]).
This efficiency allows us to answer several central open questions regarding the round complexity
of important distance computation problems in the CON GEST model.
There are several interesting directions for future work. First, there is still a log n factor gap
between the upper and lower bounds on the round complexity of computing the diameter in the
CON GEST model. Due to the fundamentality of the diameter, we believe that it will be interesting
to close this small gap.
Second, we believe our degree-reduction technique can be used also for our bounds on approximations, albeit with more involved modifications. We also believe this technique can be useful in
obtaining lower bounds on constant degree graphs in additional settings, beyond CONGEST.
Third, while our ideas greatly improve the state of the art lower bounds for shortest paths
problems on unweighted graphs, their potential in the regime of weighted graphs is yet to be
explored.
Finally, following our strong barriers for sparse graphs, it is important to seek further natural
restrictions on the networks that would allow for much faster distance computation. Planar graphs
are an intriguing setting in this context. A promising recent work of Ghaffari and Haeupler [22]
e
showed that computing a minimum spanning tree can be done in O(D)
rounds in planar graphs,
√
e
despite the Ω( n) lower bound for general graphs [17]. Can the diameter of a planar network
e
be computed in O(D)
rounds? While the graphs in our lower bounds are highly non-planar, it is
interesting to note that they have a relatively small treewidth of O(log n).

26

Acknowledgement: We thank Ami Paz for pointing out Observation 6.4, and for useful discussions.

References
[1] A. Abboud, A. Backurs, T. D. Hansen, V. V. Williams, and O. Zamir. Subtree isomorphism
revisited. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1256–1271, 2016.
[2] A. Abboud, F. Grandoni, and V. V. Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM
Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015,
pages 1681–1697, 2015.
[3] A. Abboud and V. V. Williams. Popular conjectures imply strong lower bounds for dynamic
problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS
2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434–443, 2014.
[4] A. Abboud, V. V. Williams, and J. R. Wang. Approximation and fixed parameter subquadratic
algorithms for radius and diameter in sparse graphs. In Proceedings of the Twenty-Seventh
Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA,
January 10-12, 2016, pages 377–391, 2016.
[5] A. Abboud, V. V. Williams, and O. Weimann. Consequences of faster alignment of sequences.
In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014,
Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 39–51, 2014.
[6] A. Abboud, V. V. Williams, and H. Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Proceedings of the Forty-Seventh Annual ACM on Symposium
on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 41–50,
2015.
[7] D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest
paths (without matrix multiplication). SIAM J. Comput., 28(4):1167–1181, 1999.
[8] A. Backurs and P. Indyk. Edit distance cannot be computed in strongly subquadratic time
(unless SETH is false). In Proceedings of the Forty-Seventh Annual ACM on Symposium on
Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 51–58, 2015.
[9] M. Borassi, P. Crescenzi, and M. Habib. Into the square - on the complexity of quadratic-time
solvable problems. CoRR, abs/1407.4972, 2014.
[10] M. Cairo, R. Grossi, and R. Rizzi. New bounds for approximating extremal distances in
undirected graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 363–376,
2016.
[11] M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, and S. Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for nonreducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 261–270, 2016.
27

[12] K. Censor-Hillel, P. Kaski, J. H. Korhonen, C. Lenzen, A. Paz, and J. Suomela. Algebraic
methods in the congested clique. In Proceedings of the 2015 ACM Symposium on Principles
of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015,
pages 143–152, 2015.
[13] K. Censor-Hillel, T. Kavitha, A. Paz, and A. Yehudayoff. Distributed construction of purely
additive spanners. Manuscript, 2016.
[14] T. M. Chan and R. Williams. Deterministic apsp, orthogonal vectors, and more: Quickly
derandomizing razborov-smolensky. In Proceedings of the Twenty-Seventh Annual ACM-SIAM
Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016,
pages 1246–1255, 2016.
[15] S. Chechik, D. H. Larkin, L. Roditty, G. Schoenebeck, R. E. Tarjan, and V. V. Williams.
Better approximation algorithms for the graph diameter. In Proceedings of the Twenty-Fifth
Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA,
January 5-7, 2014, pages 1041–1052, 2014.
[16] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Third
Edition. The MIT Press, 3rd edition, 2009.
[17] A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and
R. Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM J.
Comput., 41(5):1235–1265, 2012.
[18] A. Drucker, F. Kuhn, and R. Oshman. On the power of the congested clique model. In ACM
Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18,
2014, pages 367–376, 2014.
[19] M. Elkin. Unconditional lower bounds on the time-approximation tradeoffs for the distributed
minimum spanning tree problem. In Proceedings of the 36th Annual ACM Symposium on
Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 331–340, 2004.
[20] M. Elkin. An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput., 36(2):433–456, 2006.
[21] S. Frischknecht, S. Holzer, and R. Wattenhofer. Networks cannot compute their diameter
in sublinear time. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1150–1162, 2012.
[22] M. Ghaffari and B. Haeupler. Distributed algorithms for planar networks II: low-congestion
shortcuts, mst, and min-cut. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages
202–219, 2016.
[23] M. Henzinger, S. Krinninger, and D. Nanongkai. An almost-tight distributed algorithm for
computing single-source shortest paths. CoRR, abs/1504.07056, 2015.
[24] S. Holzer, D. Peleg, L. Roditty, and R. Wattenhofer. Distributed 3/2-approximation of the
diameter. In Distributed Computing - 28th International Symposium, DISC 2014, Austin, TX,
USA, October 12-15, 2014. Proceedings, pages 562–564, 2014.

28

[25] S. Holzer and N. Pinsker. Approximation of distances and shortest paths in the broadcast
congest clique. CoRR, abs/1412.3445, 2014.
[26] S. Holzer and R. Wattenhofer. Optimal distributed all pairs shortest paths and applications.
In ACM Symposium on Principles of Distributed Computing, PODC ’12, Funchal, Madeira,
Portugal, July 16-18, 2012, pages 355–364, 2012.
[27] L. Kor, A. Korman, and D. Peleg. Tight bounds for distributed minimum-weight spanning
tree verification. Theory Comput. Syst., 53(2):318–340, 2013.
[28] E. Kushilevitz and N. Nisan. Communication complexity. In Cambridge University Press,
1997.
[29] C. Lenzen and B. Patt-Shamir. Fast routing table construction using small messages: extended
abstract. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA,
June 1-4, 2013, pages 381–390, 2013.
[30] C. Lenzen and D. Peleg. Efficient distributed source detection with limited bandwidth. In
ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada,
July 22-24, 2013, pages 375–382, 2013.
[31] J. Leskovec and A. Krevl. {SNAP Datasets}:{Stanford} large network dataset collection. 2014.
[32] R. Meusel, S. Vigna, O. Lehmberg, and C. Bizer. The graph structure in the web - analyzed
on different aggregation levels. J. Web Science, 1(1):33–47, 2015.
[33] D. Nanongkai. Distributed approximation algorithms for weighted shortest paths. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014,
pages 565–573, 2014.
[34] D. Nanongkai, A. D. Sarma, and G. Pandurangan. A tight unconditional lower bound on
distributed randomwalk computation. In Proceedings of the 30th Annual ACM Symposium on
Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6-8, 2011, pages
257–266, 2011.
[35] D. Peleg. Distributed computing: a locality-sensitive approach. In Society for Industrial
Mathematics, 2000.
[36] D. Peleg, L. Roditty, and E. Tal. Distributed algorithms for network diameter and girth.
In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012,
Warwick, UK, July 9-13, 2012, Proceedings, Part II, pages 660–672, 2012.
[37] D. Peleg and V. Rubinovich. A near-tight lower bound on the time complexity of distributed
MST construction. In 40th Annual Symposium on Foundations of Computer Science, FOCS
’99, 17-18 October, 1999, New York, NY, USA, pages 253–261, 1999.
[38] A. A. Razborov. On the distributional complexity of disjointness. Theor. Comput. Sci.,
106(2):385–390, 1992.
[39] L. Roditty and V. V. Williams. Fast approximation algorithms for the diameter and radius of
sparse graphs. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA,
USA, June 1-4, 2013, pages 515–524, 2013.

29

[40] R. Williams. Faster all-pairs shortest paths via circuit complexity. In Symposium on Theory
of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 664–673,
2014.
[41] V. V. Williams and R. Williams. Subcubic equivalences between path, matrix and triangle
problems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS
2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 645–654, 2010.
[42] A. C. Yao. Some complexity questions related to distributive computing (preliminary report).
In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May
2, 1979, Atlanta, Georgia, USA, pages 209–213, 1979.

30

