Improved Deterministic Distributed Construction of Spanners
Ofer Grossman

Merav Parter

MIT
ofer.grossman@gmail.com

MIT
parter@mit.edu

arXiv:1708.01011v2 [] 12 Aug 2017

August 15, 2017

Abstract
Graph spanners are fundamental graph structures with a wide range of applications in distributed
networks. We consider a standard synchronous message passing model where in each round O(log n)
bits can be transmitted over every edge (the CONGEST model).
The state of the art of deterministic distributed spanner constructions suffers from large messages. The only exception is the work of Derbel et al. [10], which computes an optimal-sized
(2k − 1)-spanner but uses O(n1−1/k ) rounds.
In this paper, we significantly improve this bound. We present a deterministic distributed
algorithm that given an unweighted n-vertex graph G = (V, E) and a parameter k > 2, constructs
a (2k − 1)-spanner with O(k · n1+1/k ) edges within O(2k · n1/2−1/k ) rounds for every even k. For
odd k, the number of rounds is O(2k · n1/2−1/(2k) ). For the weighted case, we provide the first
deterministic construction of a 3-spanner with O(n3/2 ) edges that uses O(log n)-size messages and
e
O(1)
rounds. If the nodes have IDs in [1, Θ(n)], then the algorithm works in only 2 rounds!

Contents
1 Introduction & Related Work
1.1 Our Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Our Approach and Key Ideas in a Nutshell . . . . . . . . . . . . . . . .
1.2.1 Key Idea (I): Grouping Baswana-Sen Clusters into Superclusters
1.2.2 Key Idea (II): Better Spanners for Unbalanced Bipartite Graphs

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

2
3
4
4
5

2 Preliminaries, Notation and Model

5

e
3 3-Spanners in O(1)
Rounds

6

4 (2k − 1) Spanners
4.1 Take (I): O(n1−1/k )-Round Algorithm NaiveSpanner . . . . . . .
4.2 Key Tool (I): Sparser Spanner for Unbalanced Bipartite Graphs .
4.3 Key Tool (II): Superclustering – Grouping Baswana-Sen Clusters
4.4 (2k − 1)-Spanners in O(2k · n1/2−1/k ) Rounds . . . . . . . . . . .
4.5 Analysis of ImprovedSpanner for Graphs with diam(G) = O(1) . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

9
9
11
16
18
22

A Partitioning Lemma 4.5

26

B Missing Details of Alg. ImprovedSpanner for General Graphs

27

1

1

Introduction & Related Work

Graph spanners are fundamental graph structures that are used as a key building block in various
communication applications, e.g., routing, synchronizers, broadcasting, distance oracles, and shortest
path computations. For this reason, the distributed construction of sparse spanners has been studied
extensively [2,6–10,16]. The standard setting is a synchronous message passing model where per round
each node can send one message to each of its neighbors. Of special interest is the case where the
message size is limited to O(log n) bits, a.k.a. the CONGEST model.
The common objective in distributed computation of spanners is to achieve the best-known existential size-stretch trade-off as fast as possible: It is folklore that for every graph G = (V, E), there
exists a (2k − 1)-spanner H ⊆ G with O(n1+1/k ) edges. Moreover, this size-stretch tradeoff is believed
to be optimal, following the girth conjecture of Erdős.
Designing deterministic algorithms for local problems has been receiving a lot of attention since the
foundation of the area in 1980s. Towards the end of this section, we elaborate more on the motivation
for studying deterministic algorithms in the distributed setting.
State of the art for deterministic distributed constructions of spanners: Whereas there
are efficient randomized constructions for spanners, as the reader will soon notice, the state of the
art for distributed deterministic spanner constructions suffers from large message sizes: Derbel and
Gavoille [6] construct constant stretch spanners with o(n2 ) edges and O(n ) rounds for any constant
, using messages of size O(n). Derbel, Gavoille and Peleg improved this result and presented in [7]
a construction of an O(k)-spanner with O(kn1+1/k ) edges in O(logk−1 n) rounds. This was further
improved in the seminal work of Derbel, Gavoille, Peleg, and Viennot [8], which provides a deterministic k-round algorithm for constructing (2k − 1)-spanners with optimal size. However, again the
algorithm uses messages of size O(n). Using large messages is indeed inherent to all known efficient
deterministic techniques, which are mostly based on network decomposition and graph partitioning.
In the conventional approaches of network decomposition, the deterministic algorithms for spanners
usually require a vertex to learn the graph topology induced by its O(1)-neighborhood. This cannot
be done efficiently with small messages.
As Pettie [16] explicitly noted, all these constructions have the disadvantage of using large messages.
Derbel et al. [9] also pointed out that constructing sparse spanners deterministically with small message
sizes remains open.
The state of the art when using small messages: There are only two exceptions for this story.
Barenboim et al. [1] showed a construction of O(logk−1 n) spanner with O(n1+1/k ) edges in O(logk−1 n)
rounds. Hence, whereas the runtime is polylogarithmic, the stretch-size tradeoff of the output spanner
is quite far from the optimal one.
We are then left with only one previous work that fits our setting, due to Derbel, Mosbah and
Zemmari [10]. They provide a deterministic construction of an optimal-size (2k − 1)-spanner but using
O(n1−1/k ) rounds.
The state of the art in other distributed settings: Turning to randomized constructions, perhaps
one of the most well known approaches to construct a spanner is given by Baswana and Sen [2], which
we review soon. Recently, [4] showed that the Baswana-Sen algorithm can be derandomized in the
congested clique model of communication in which every pair of nodes (even non-neighbors in the
input graph) can exchange O(log n) bits per round. Note that this model is much stronger than the
standard model in which only neighboring vertices can communicate. Indeed the algorithm of [4]
requires a global evaluation of the random seed, thus implementing this algorithm in the standard
CONGEST model requires Ω(diam(G) + n1−1/k ) rounds where diam(G) is the diameter of the graph.
Hence, deterministic construction of spanners in the CONGEST model calls for new ideas!
Before we proceed with introducing our main contribution, we make a short pause to further
2

motivate the study of deterministic distributed algorithms.
A note on deterministic distributed algorithms: Much effort has been invested in designing
deterministic distributed algorithms for local problems. Examples include MIS (maximal independent
set), vertex coloring, edge coloring and and matching. Until recently, a deterministic poly-log n round
algorithm was known only for the maximal matching problem (see [13] and a recent improvement
by [11]). In a recent breakthrough [12], a polylogarithmic solution was provided also for the (2∆ − 1)
edge coloring1 . Aside from the general theoretical question, the distributed setting adds additional
motivation for studying deterministic algorithms (as nicely noted in [11]). First, in the centralized
setting, if the randomized algorithm ends with an error, we can just repeat. In the distributed setting,
detecting a global failure requires communicating to a leader, which blows up the runtime by a factor of
network diameter. Second, for problems as MIS, [5] showed that improving the randomized complexity
requires an improvement in the deterministic complexity.
Wheres most results for deterministic local problems are for the LOCAL model, which allows unbounded messages; the size of messages that are sent throughout the computation is a second major
attribute of distributed algorithms. It is therefore crucial to study the complexity of local problems
under bandwidth restrictions. Surprisingly, most of the algorithms for local problems already use only
small messages. The problem of spanners is distinguished from these problems, and in fact, spanners
is the only setting we are aware of, in which all existing deterministic algorithms use large messages.
Hence, the main challenge here is in the combination of deterministic algorithms with congestion
constraints.

1.1

Our Contribution

Our main result is:
Theorem 1.1. For every n-vertex unweighted graph G = (V, E) and even k, there exists a deterministic distributed algorithm that constructs a (2k − 1)-spanner with O(k · n1+1/k ) edges in
O(2k · n1/2−1/k ) rounds using O(log n)-size messagesa .
a

For odd k, we obtain a similar theorem, but with O(2k · n1/2−1/(2k) ) rounds.

A key element in our algorithm is the construction of sparser spanners for unbalanced bipartite
graph. This construction might become useful in other spanner constructions.
Lemma 1.2 (Bipartite Spanners). Let G = (A ∪ B, E) be an unweighted bipartite graph, with
|A| ≤ |B|. For even k ≥ 4, one can construct (in the CONGEST model) a (2k − 1) spanner H with
|E(H)| = O(k|A|1+2/k + |B|) edges within O(|A|1−2/k ) roundsa .
a

Hence, yielding an improved edge bound, for |A| ≤ n(k+1)/(k+2) .

Turning to weighted graphs, much less in known about the deterministic construction of spanners
in the distributed setting. The existing deterministic constructions of optimal-sized (2k − 1)-spanners
(even in the LOCAL model) are restricted to unweighted graphs, already for k = 2. If the edge weights
are bounded by some number W , there is a simple reduction2 to the unweighted setting, at the cost of
increasing the stretch by a factor of (1 + ) and the size of the spanner by a factor of log1+ W . Hence,
e 3/2 ) edges. Whereas
already in the LOCAL model and k = 2, we only have a (3 + ) spanner with O(n
our general approach does not support the weighted case directly, our algorithm for 3-spanners does
1
2

Where ∆ is the maximum degree in the graph.
Apply the algorithm for unweighted graphs separately for every weight scale ((1 + )i , (1 + )i+1 ].

3

extend for weighted graphs. Hence, we give here the first deterministic construction with nearly tight
tradeoff between the size, stretch and runtime.
Theorem 1.3 (3-Spanners for Weighted Graphs). For every n-vertex weighted graph G = (V, E),
there exists a deterministic distributed algorithm that constructs a 3-spanner with O(n3/2 ) edges
in O(log n) rounds using O(log n)-size messages. If vertices have IDs in the range of [1, O(n)], it
can be done in two rounds.

1.2

Our Approach and Key Ideas in a Nutshell

For the sake of discussion, let k = O(1) throughout this section.
A brief description of the randomized construction by Baswana-Sen. A clustering C =
{C1 , . . . , C` } is a collection of vertex disjoint sets which we call clusters. Every cluster has some a
special vertex which we call the cluster center. In the high level, the Baswana-Sen algorithm computes
k levels of clustering C0 , . . . , Ck−1 where each clustering Ci is obtained by sampling the cluster center
of each cluster in Ci−1 with probability n−1/k . Each cluster C ∈ Ci has in the spanner H, a BFS tree
of depth i rooted at the cluster center spanning3 all the nodes of C. The vertices that are not incident
to the sampled clusters become unclustered. For each unclustered vertex v, the algorithm adds one
edge to each of the clusters incident to v in Ci−1 . This randomized construction is shown to yield a
spanner with O(kn1+1/k ) edges in expectation and it can be implemented in O(k 2 ) rounds4 . Note that
the only randomized step in Baswana-Sen is in picking the cluster centers of the ith clustering. That
is, given the n1−(i−1)/k cluster centers Zi−1 of the clusters in Ci−1 , it is required to pick n−1/k fraction
of it, to be centers of the clusters in Ci−1 .
The brute-force deterministic solution in O(n) rounds: A brute-force approach to pick the
new cluster centers of Ci is to iterate over the clusters in Ci−1 one by one, checking if they satisfy
some expansion criteria. Informally, the expansion is measured by the number of vertices in the ith neighborhood of the cluster center (i.e., number of vertices that can be covered5 by the cluster center
in case it proceeds to the ith level). If the expansion is large enough, the current cluster “expands”
(i.e., covers vertices up to distance i), and joins the ith -level of the clustering Ci . Since in the first
level there are O(n) clusters (each vertex forms a singleton cluster), this approach gives an O(n)-round
algorithm. With some adaptations, this approach can yield an improved O(n1−1/k ) round algorithm
(as in [10]).
Our O(n1/2−1/k )-round deterministic solution: Inspired by the randomized construction of BaswanaSen and the work of Derbel, Gavoille, and Peleg [7], we present a new approach for constructing
spanners, based on two novel components which we discuss next.
1.2.1

Key Idea (I): Grouping Baswana-Sen Clusters into Superclusters

Our approach is based on adding an additional level of clustering on top of Baswana-Sen clustering. We
introduce the novel notion of a supercluster – a subset of Baswana-Sen clusters that are close to each
√
other in G. In every level i ≤ k/2, we group the O(n1−i/k ) clusters of Ci into O( n) superclusters, each
containing O(n1/2−i/k ) clusters which are also close to each other in G. Specifically, the superclusters
have the following useful structure: cluster-centers of the same supercluster are connected in G by a
constant depth tree (i.e., the weak diameter of the superclusters is O(1)), and the trees of different
superclusters are edge-disjoint. See Fig. 2 for an illustration.
3

The vertices of the tree are precisely the vertices of the cluster.
With some care, we believe the algorithm can also be implemented in O(k) rounds
5
We say the a vertex is covered by a cluster-center if it gets into its cluster.
4

4

Unlike the brute-force O(n)-round algorithm mentioned above, our algorithm iterates over superclusters rather than clusters. We define the neighborhood of the supercluster to be all vertices that
belong to – or have a neighbor in– one of the clusters of that supercluster. The expansion of the
supercluster is simply the size of this neighborhood. The importance of having this specific structure
in each supercluster is that it allows the superclusters to compute their expansion in O(1) rounds6 .
The faith of the superclusters (i.e., whether they continue on to the next level of clustering), in our
algorithm, is determined by their expansion. If the expansion of a supercluster is sufficiently high,
all the cluster centers of that supercluster join the next level i of the clustering. Otherwise, all these
clusters are discarded from the clustering. As we will show in depth, the algorithm makes sure that
at most O(n1/2−1/k ) superclusters pass this “expansion test” and the remaining superclusters with
low-expansion are handled using our second key tool as explained next.
1.2.2

Key Idea (II): Better Spanners for Unbalanced Bipartite Graphs

In our spanner construction, each supercluster with low-expansion has additional useful properties:
√
it has |A| = O( n) vertices and only |B| = O(n1/2+1/k ) many “actual” neighbors7 . We then apply
Lemma 1.2 on these superclusters by computing the (2k − 1)-spanner for each of these bipartite graphs
obtained taking the vertices of the supercluster to be on one side of the bipartition, A, and their
“actual” neighbors on the other side B. Since there are O(n1/2 ) superclusters, this adds O(n1/2+1/k ·
n1/2 ) = O(n1+1/k ) edges to the spanner.
Finally to provide a good stretch in the spanner for all the edges in G between vertices of the
same supercluster8 , we simply recurse inside each supercluster– this can be done efficiently since
the superclusters are vertex disjoint (as they contain sets of vertex disjoint clusters), and each of
√
supercluster has O( n) vertices.
Roadmap. The structure of the paper is as follows. We start by considering in Section 3 the simplified
case of 3-spanners (hence k = 2) and present a deterministic construction with O(log n) rounds. Section
4 considers the general case of k > 2. In Sec. 4.1, we first describe an O(n1−1/k )-round algorithm
that already contains some of the ideas of the final algorithm. Then, before presenting the algorithm,
we describe the two key tools that it uses. For didactic reasons, in Sec. 4.2, we first describe the
construction of sparser spanners for unbalanced bipartite graphs. Only later 4.3, we present the new
notion of superclusters. Finally, in Sec. 4.4, we show how these tools can be used to construct
(2k − 1)-spanners for graphs of low diameter. The extension for general graphs is in Appendix B.

2

Preliminaries, Notation and Model

Notations and Definitions. We consider an undirected unweighted n-vertex graph G = (V, E)
where V represents the set of processors and E is the set of links between them. Let diam(H) be the
diameter of the subgraph H ⊆ G. We denote the diameter of G by D = diam(G). For u, v ∈ V (G)
and a subgraph H, let dist(u, v, H) denote the u − v distance in the subgraph H ⊆ G. When
H = G, we omit it and write dist(u, v). Let Γ(u) = {v | (u, v) ∈ E} be the set of
S u’s neighbors
+
0
0
in G and Γ (u) = Γ(u) ∪ {u}. For a subset of the vertices V ∈ V , let Γ(V , G) = u∈V 0 Γ(u) and
Γ+ (V 0 , G) = Γ(V 0 , G) ∪ V 0 . Let Γi (v) = {u | dist(u, v) ≤ i}, for a subset V 0 , Γi (V 0 ) is defined
accordingly. For a subgraph H ⊆ G, let E(v, H) = {(u, v) ∈ E(H)} be the set of edges incident to v in
the subgraph H and let deg(v, H) = |E(v, H)| denote the degree of node v in G. For a set of vertices
6

using the collection of edge disjoint O(1)-depth trees that connect their cluster centers.
This term is informal, the actual neighbors are the vertices that are no longer clustered by the current clustering.
8
Vertices whose clusters belong to the same supercluster.
7

5

C, let G(C) be the induced graph of G on C. We say that the a tuple (a, b) > (c, d) if a > c or a = c
but b > d.
Spanners and Clustering. A subgraph H ⊆ G is a (2k − 1)-spanner if dist(u, v, H) ≤ (2k −
1)dist(u, v, G) for every u, v ∈ V . Given a graph G, a subgraph H, and an edge e = (u, v) in G,
we define the stretch of e in H to be the length of the shortest path from u to v in H. If no such
path exists, we say that the stretch is infinite. We say that an edge e = (u, v) is taken care of in H
if dist(u, v, H) ≤ (2k − 1). A cluster is a connected set C of vertices of the original graph. Often, a
cluster will have one of its vertices s ∈ C be the cluster center. The ID of the cluster is the ID of its
center. Two clusters C1 and C2 are neighbors if Γ(C) ∩ C 0 6= ∅. For a subset of vertices S ⊆ V , the
diameter of the subset is simply the diameter of the induced graph G on S.
Ruling Sets. An (α, β)-ruling set with respect to G and V 0 ⊆ V is a subset U ⊆ V 0 satisfying the
following: (I) All pairs u, v ∈ U satisfy dist(u, v) ≥ α, (II) For all v ∈ V 0 , there exists a u ∈ U such
that dist(u, v) ≤ β.
The Communication Model. We use a standard message passing model, the CONGEST model [15],
where the execution proceeds in synchronous rounds and in each round, each node can send a message
of size O(log n) to each of its neighbors. In this model, local computation is done for free at each
node and the primary complexity measure is the number of communication rounds. Each node holds
a processor with a unique and arbitrary ID of O(log n) bits. Throughout, we assume that the nodes
know a constant approximation on the number of nodes n, same holds also for [3].

3

e
3-Spanners in O(1)
Rounds

The key building block of the algorithm is the construction of a linear sized 3-spanner for a
bipartite graph. A similar idea already appeared in [7], but using O(n)-bit messages.

√
n×n

The core construction: 3-spanners for unbalanced bipartite graphs
√
Lemma 3.1. Let G = (A, B, E) be a (possibly weighted) bipartite graph where |A| = O( n), |B| =
O(n), and each vertex knows whether it is in A or in B. Then one can construct (in the CONGEST
model) a 3-spanner H with O(n) edges within two rounds.
Algorithm Bipartite3Spanner first forms |A| vertex-disjoint star clusters (clusters of radius 1), each
centered at a vertex of A. To do that, every vertex vb ∈ B picks one of its neighbors va ∈ Γ(vb ) ∩ A
to be its cluster center and sends the ID of its chosen neighbor va to all of its neighbors. We write
c(vb ) = va to denote that the cluster center of vb is va .
√
All edges (vb , c(vb )) are added to the spanner H. At this point, the graph contains O( n) clusters
centered at the vertices in A. We say that two stars S1 and S2 are neighbors if the center of S1 has
a neighbor in S2 , or vice-versa. Note that because the graph is bipartite, this is the only possible
connection between clusters. Then, for each vertex ua in A, and each neighboring star-cluster u0a , the
vertex ua adds to the spanner H one edge to one of its neighbors in the cluster of u0a . For a complete
description of the algorithm see Alg. 1. For illustration see Fig. 1. To adapt the algorithm for the
√

Algorithm 1 Bipartite3Spanner(G = (A ∪ B, E)) for |A| = O( n) and |B| = O(n)
1: H ← ∅
2: Each vertex vb ∈ B selects an arbitrary neighboring vertex va ∈ A, assigns c(vb ) = va and send c(vb ) to all its
neighbors. It adds the edge (vb , c(vb )) to H.
3: Each vertex ua ∈ A does the following (in parallel):
4: for each ID va received do
5:
Pick a single neighbor vb satisfying c(vb ) = va . Add the edge (ua , vb ) to H.

6

Figure 1: Illustration of the star decomposition and the spanner. The dashed edge that is omitted
from the spanner has a path of length three in the spanner.

weighted case, we simply let each vb ∈ B pick its closest neighbor in A. In addition, each vertex ua
connects to its closest neighbor in each star of u0a . It is easy to see that the algorithm takes 2 rounds.
Lemma 3.2. The output H of Alg. Bipartite3Spanner is a 3-spanner with O(n) edges.
Proof. First, we show that H is a 3-spanner. To analyze the stretch, consider an edge (x, y) ∈ G \ H
where x ∈ A and y ∈ B. Let z = c(y). Since (x, y) ∈
/ H, we have that dist(z, y, G) ≤ dist(x, y, G).
Let w ∈ B be the neighbor of x in the cluster of z such that the edge (x, w) was added to H. Since
(x, y) ∈
/ H, such an edge (z, w) exists and in addition, dist(x, w, G) ≤ dist(x, y, G). Overall, we have:
dist(x, y, H) ≤ dist(x, w, H) + dist(w, z, H) + dist(z, y, H)
= dist(x, w, G) + dist(w, z, G) + dist(z, y, G)
≤ dist(x, y, G) + dist(w, x, G) + dist(x, y, G)
≤ dist(x, y, G) + dist(y, x, G) + dist(x, y, G) = 3dist(x, y, G) .
We next bound the number of edges in H. In the first round (line 2 of Alg. 1), each element of B
adds at most one edge to H, for a total of |B| edges. In the second round, each element of A added at
most |A| elements to |H|. Overall, H has |B| + |A|2 = O(n) edges.
Constructing 3-spanners for general graphs in O(log n) rounds: Let Vh = {v ∈ V | deg(v, G) ≥
√
n} be the set of high degree vertices in G and let V` = V \ Vh be the remaining low -degree vertices.
First, the algorithm adds to the spanner H, all the edges of the low-degree vertices V` . Then, it pro√
ceeds by partitioning (in a way that will be described later) the high-degree vertices Vh into t = O( n)
√
balanced sets V1 , . . . , Vt . This partition gives rise to t bipartite n × n graphs Bi obtained by taking Vi
to be on one side of the partition and V \ Vi on the other side. We describe the partitioning procedure
in Lemma 3.3. We can then apply Algorithm Bipartite3Spanner to construct 3-spanners for all these
subgraphs in parallel. Finally, we simply add to H, all the internal edges Vi × Vi for every i, again
adding total of t · O(n) edges.

7

Algorithm Improved3Spanner
• (S0): Handling Low-Degree Vertices: Add to H all edges in (V` × V ) ∩ E(G).
• (SI): Balanced Partitioning of High-Degree Vertices Vh : Partition the high-degree
√
√
vertices of V into Θ( n) sets V1 , . . . , Vt each with O( n) vertices.
• (SII): Taking care of edges Vi × (V \ Vi ), for every i ∈ {1, . . . , t}:
– Define Bi = (Vi , V \ Vi ) for every i ∈ {1, . . . , t}.
– Apply Algorithm Bipartite3Spanner on each Bi graph in parallel to construct a
3-spanner Hi ⊆ Bi for every i and these Hi subgraphs to H.
• (SIII): Taking care of edges Vi × Vi , i ∈ {1, . . . , t}: Add to H all edges in Vi × Vi for
every i ∈ {1, . . . , t}.
Note that eventhough the bipartite graphs Bi are not vertex disjoint, each edge belongs to at most
two such graphs, and hence we can construct the 3-spanners for all Bi in parallel. It is also easy to
see that the final spanner has O(n3/2 ) edges.
The only missing piece at that point concerns the computation of partitioning Vh .
Balanced partitioning of Vh in O(log n) rounds: The partition procedure starts by computing
(4, O(log n))-ruling set R ⊆ V for the high-degree vertices Vh . We will use the following lemma that
uses standard technique for constructing (t, t log n)-ruling sets.
Lemma 3.3. Given a graph G = (V, E) and a subset Vh ∈ V of the vertices, one can compute in
O(log n) rounds in the CONGEST model, a (4, O(log n))-ruling set U ⊆ Vh with respect to G and the
high-degree vertices Vh .
We now view each of the vertices r ∈ R as a center of a cluster of diameter O(log n): let each
high-degree vertex join the cluster of the vertex closest to it in R, breaking ties based on IDs. Since
every vertex in Vh is at distance O(log n) from R, all the vertices Vh will be clustered within O(log n)
√
rounds. Each vertex r in R can then partition the vertices of its cluster into subsets of size b nc, and
√
an additional leftover subset of size at most n (this can be done using balanced partitioning lemma,
√
Lemma 4.5). We now claim that this partition is balanced. Clearly, all sets are of size O( n), so we
√
just show that there O( n) subsets. Since every r ∈ R is high-degree and since every two vertices in
√
R are at distance at least 4, we have that |R| = O( n). For each r ∈ R, there is at most one subset
√
√
√
of size less than b nc. Therefore, there are O( n) subsets of size less than b nc. All other subsets
√
√
√
are of size b nc. However, there can be at most O( n) disjoint subsets of size b nc, hence there are
√
O( n) subsets in total, as desired.
We conclude by showing:
Lemma 3.4 (3-Spanner Given Partition). Given a (possibly weighted) n-vertex graph G = (V, E) with
√
√
a vertex-partition V1 , V2 , . . . , Vt such that |Vi | = O( n) and t = O( n), one can construct a 3-spanner
H of size O(n3/2 ) in 2 rounds in the CONGEST model.
Proof. For each i, we construct a spanner Hi for the bipartite graph Bi = (Vi ∪ (V \ Vi )). Since
√
H1 , . . . , Ht can
each edge is in at most two of the bipartite graphs, all these t = O( n) spanners S
be constructed in parallel, while slowing down by a factor of at most 2. Let H = i Hi , we have
|H| =P
O(n3/2 ). In addition, we add to H all the internal edges inside each Vi . This adds a total of at
√
most `i=0 |Vi |2 edges to H. Since |Vi |2 = O(n), and ` = O( n), the total number of edges added is
P`
2
3/2 ), and |E(H)| = O(n3/2 ).
i=0 |Vi | = O(n
We now prove that H is a 3-spanner. Consider some edge (u, v). If both u and v are in the same
Vi , then (u, v) ∈ H. If u ∈ Vi and v ∈ Vj , then, consider the spanner Hi computed for the graph
8

Gi = (Vi ∪ (V \ Vi )). Since (u, v) is an edge in Gi , there must exist a path of length at most 3 from u
to v in Hi , and therefore in H. The lemma follows.
Finally, if the vertices IDs are bounded, two rounds are sufficient to construct the spanner.
Theorem 3.5 (Small IDs). Given a graph G = (V, E) where the IDs of the vertices have log(n) + O(1)
bits, one can construct a 3-spanner H of G with |H| = O(n3/2 ) edges in two rounds.
Proof. We can use the second half of the IDs of the vertices to partition V into subsets V1 , V2 , . . . , V` .
√
√
There are 2(log(n)+O(1))/2 = O( n) possibilities for the second half of the ID. Hence, ` = O( n).
√
√
Similarly, there are O( n) possibilities for the first half of the ID, so |Vi | = O( n) for all i. We now
apply Lemma 3.4 on G with the sets V1 , V2 , . . . , V` .

4

(2k − 1) Spanners

The structure of Baswana-Sen clustering. At the heart of the algorithm is a construction of
(k − 1)-levels of clustering C0 , . . . , Ck−1 . The initial clustering C0 = {{v}, v ∈ V } simply contains n
singleton clusters. For every i, each clusterSC ∈ Ci has a cluster center z and we denote by Zi the
collection of cluster centers. We define Vi = z∈Zi Γi (z). A vertex v is i-clustered if v ∈ Vi , otherwise it
is i-unclustered. Hence Vi is the set of clustered vertices appearing in the clusters of Ci . The algorithm
consists of k − 1 steps where at the end of step i ∈ {1, . . . , k − 1}, we have an ith -level clustering
Ci = {C1 , . . . , C` } and a partial spanner Hi that satisfies the following: (P1) The clustering Ci contains
` = O(n1−i/k ) clusters. (P2) For each cluster Cj ∈ Ci with a center zj , the subgraph Hi contains a BFS
tree Ti (C) of depth at most i that spans all the vertices of C (i.e., the vertices of Ti (C) are precisely
C) and (P3) For every u ∈ Vi−1 \ Vi , and every v ∈ Γ(u), dist(u, v, Hi ) ≤ 2k − 1.

High-Level Description of Phase i in Baswana-Sen Algorithm
• (SI) Selecting O(n1−i/k ) cluster centers Zi ⊆ Zi−1 . In the randomized algorithm, this is
done by sampling each center in Zi−1 independently with probability n−1/k . We then have
Vi = Γ+
i (Zi ) are the i-clustered vertices.
• (SII) Taking care of unclustered vertices Vi−1 \ Vi . That is, taking care of the vertices
that stopped being clustered at that point.
• (SIII) Forming the clusters of Ci around Zi . This is done by letting each u ∈ Vi join
the cluster of its closest center in Zi breaking tie based on ID’s. The latter can be
implemented in O(i) rounds of constructing BFS trees of depth i from all centers Zi while
breaking ties appropriately.
At the final phase of Baswana-Sen, there are O(n1/k ) clusters in Ck−1 and at that point, each vertex
v ∈ V adds one edge to each of its neighboring clusters in Ck−1 .
Note that the only step that uses randomness in this algorithm is sub-step (SI), and the other two
sub-steps (SII-SIII) and the final phase are completely deterministic. Our challenge is to implement
sub-step (SI) deterministically in a way that in sub-step (SII) we do not add too many edges to the
spanner. The algorithms presented from now on, will simulate the ith phase of Baswana-Sen only
without using randomness. Sub-step (SIII) and the final phase will be implemented exactly as in
Baswana-Sen.

4.1

Take (I): O(n1−1/k )-Round Algorithm NaiveSpanner

It is easy to see that 0th -level clustering containing n singleton clusters satisfies properties (P1-P3).
To simulate the ith phase of Baswana-Sen algorithm, we employ O(i · n1−i/k ) deterministic rounds:
9

Initially, we unmark all the vertices and over time, some of the vertices will get marked (i.e., indicating
that they are i-clustered). The procedure consists of O(n1−i/k ) steps where at each step, we look at the
0
remaining set Zi−1
of cluster centers in Zi−1 that have not yet been added to Zi . Let U be the current
0
0 . For each cluster
set of unmarked vertices and let Ci−1
⊆ Ci−1 be the corresponding
clusters of Zi−1
S
C ∈ Ci−1 , define its unmarked neighborhood by ΓU (C) = u∈C Γ(u) ∩ U and its current unmarkeddegree by degU (C) = |ΓU (C)|. We say that cluster C is a local-maxima in its unmarked neighborhood
if it has the maximum tuple (lexicographically) (degU (C), ID(C)) among all other clusters C 0 that
have mutual unmarked neighbors (i.e., ΓU (C) ∩ ΓU (C 0 ) 6= ∅).

Phase i of Algorithm NaiveSpanner
(SI): Defining the centers Zi .
0
Set Zi−1
← Zi−1 , U = V and for O(n1−i/k ) steps do the following:
0
• Every center z ∈ Zi−1
of cluster C computes degU (C).
0
• Every center z ∈ Zi−1
whose cluster C has the maximum tuple (degU (C), ID(C)) in its
unmarked neighborhood, degU (C), joins Zi only if degU (C) ≥ ni/k .

• Remove from Zi0 the centers z ∈ C that join Zi and mark ΓU (C).
(SII): Taking care of unclustered vertices.
0
• Let Ci−1
be the clusters whose centers did not join Zi .
0 .
• Every remaining unmarked vertex u, adds one edge per neighboring cluster in Ci−1

(SIII): Forming the Ci clusters centered at Zi . As in Baswana-Sen.
Sketch of the Analysis: The key part to notice is that by picking the local-maxima clusters, we
have that for any two cluster-centers z1 ∈ C1 , z2 ∈ C2 that join Zi , their unmarked neighborhoods
ΓU (C1 ), ΓU (C2 ) are vertex disjoint, hence Zi contains O(n1−i/k ) centers; in addition, after O(n1−i/k )
steps, the clusters of all remaining centers have O(ni/k ) unmarked neighbors. Hence, at step (SII),
total of O(n1−(i−1)/k ) · O(ni/k ) = O(n1+1/k ) edges are added to the spanner. Turning to runtime, we
claim that each of the O(n1−i/k ) steps can be implemented in O(i) rounds. Since each cluster C ∈ Ci−1
is connected i G by a depth-i tree, and since trees of different clusters are vertex-disjoint, computing
the unmarked degree degU (C) of each cluster C can be done in O(i) rounds; To avoid the double of
counting of unmarked vertices that have many neighbors at the same cluster, each unmarked vertex
respond to only one its neighbors in each cluster. Similarly, also selecting the local maxima clusters can
be done in O(i) rounds. We note that the time complexity of the algorithm is O(n1−1/k ), as opposed
to O(n), since after O(n1−1/k ) iterations of finding clusters of locally maximal unmarked degree, all
remaining clusters will have low unmarked degree, and can be dealt with in parallel in O(1) rounds, by
adding an edge to every unmarked neighbor. Towards speeding up this algorithm, we now introduce
our key technical tools.
A remark regarding step (SII):. Let Vi0 = Vi−1 \ Vi be the set of newly unclustered vertices. In
Baswana-Sen algorithm, step (SII) takes care of all the edges in Vi0 ×V . That is, the edges added to the
spanner H at that stage provide that dist(u, v, H) ≤ 2i−1 for every (u, v) ∈ (Vi0 ∈ V )∩E. Most of the
algorithms we present in this paper, have a weaker but sufficient guarantee when implementing step
(SII). In particular, we only add edges between the remaining unmarked vertices and the remaining
clusters whose centers did not join Zi . We now show why it is sufficient. Consider an edge (u, v) ∈ E.
Let iu be the largest level of the clustering such that u is iu -clustered, define the same for v. Without
loss of generality, assume that iv ≤ iu . Case (1): iu = k − 1: Let C be the cluster of u in Ck−1 .
Since in the last step, v adds one edge to Γ(v) ∩ C, the claim holds. Case (2): iu ≤ k − 2: Consider
phase (iu + 1) where the clustering Ciu +1 is constructed given Ciu . By definition, in step (SII) of phase
10

(iu + 1) we have that the vertex v is unmarked and the vertex u belongs to a remaining cluster C ∈ Ciu .
Since every unmarked vertex adds one edge to each remaining cluster, we have that v added one edge
to C ∩ Γ(v). The claim follows.

4.2

Key Tool (I): Sparser Spanner for Unbalanced Bipartite Graphs

In this section, we consider Lemma 1.2. Similarly to the construction of 3-spanners in Section 3, a
key ingredient in our algorithm is the construction of sparser spanners for unbalanced A × B bipartite
graphs for |A| ≤ |B|. The algorithm of [7] constructs a (2k − 1) spanners for these bipartite graphs
with O(|A||B|2/k ) edges in the LOCAL model, using large messages. Our algorithm is slower than that
of [7], but has the benefit of obtaining a sparser (2k − 1)-spanner with only O(k|A|1+2/k + |B|) edges
and while using O(log n)-bit messages.
The high-level strategy of Alg. SparserBipartiteSpanner is to first compute |A| star clusters (clusters
of radius 1) by letting each vertex of B join an arbitrary neighbor in A. Hence, after one step of
clustering, we have |A| clusters rather than O(n1−1/k ) clusters is in Baswana-Sen. We then consider
star graph GS obtained contracting each star into a vertex, and essentially apply Alg. NaiveSpanner on
the star-graph GS to construct a (k −1)-spanner HS ⊆ GS with O(|A|1+2/k ) edges within O(k|A|1−2/k )
rounds. To get a (2k − 1) spanner H ⊆ G from HS , for every star-edge (Si , Sj ) ∈ HS , add a single edge
in (S1 × S2 ) ∩ E to H. Finally, adding the star edges to the spanner, gives a total of O(|A|1+2/k + |B|)
edges. Simulating Alg. NaiveSpanner on the star-graph in the CONGEST model requires some effort.
We now provide the description of Alg. SparserBipartiteSpanner and its analysis.

Full Description of Algorithm SparserBipartiteSpanner
Given a bipartite graph G = (A ∪ B, E) and even integer k ≥ 4, the goal of this section is to construct
in O(|A|1−2/k ) rounds, a (2k − 1)-spanner H ⊆ G with O(|A|1+2/k + |B|) edges.
We note that very often in our constructions, we apply this algorithm on graphs with |A| = O(n1/2 )
and |B| = O(n1/2+1/k ). In this case, we get a (2k − 1)-spanner containing O(n1/2+1/k ) edges within
O(kn1/2−1/k ) rounds.
In the first step of the algorithm, each vertex b in B picks a neighboring vertex ai in A, and joins the
star centered at ai . We call ai the leader of its star Si . Now, our graph is partitioned into |A| vertexdisjoint stars. The idea, at the high level, is to implement the NaiveSpanner on the star-graph (the
graph obtained from contracting each of the stars into a vertex), with parameter k 0 = k/2 to obtain a
spanner H 0 on the star-graph. Then, this spanner H 0 , along with the edges within stars, are combined
0
to obtain the final spanner H. Hence, we should output a spanner with O(|A|1+1/k ) = O(|A|1−2/k )
0
edges within O(|A|1−1/k ) = O(|A|1−2/k ) rounds. Implementing NaiveSpanner on the star-graph instead
of on the given graph involves some subtleties, which we elaborate on in this section.
Clustering in the Star-Graph. Let Si ⊆ V be the set of vertices in the star centered at ai and
S = {Si | ai ∈ A} be the set of all stars. Many times we call ai ∈ Si the leader of the star. For every
vertex v and a collection of stars S 0 ⊆ S, let ΓS 0 (v) = {Si ∈ S 0 | Γ+ (v) ∩ Si 6= ∅} be the neighboring
stars of vertex v in S 0 . Throughout, a cluster is defined by a collection of stars, that is C ⊆ S. A
0
clustering Ci in the ith -level is a collection of O(|A|1−i/k ) star-disjoint clusters (where k 0 = k/2), each
of radius i in the star-graph. We say that a star sj ∈ S is i-clustered if it belongs to one of the clusters
in Ci . Otherwise, it is an i-unclustered
star.
S
For a cluster C, let V (C) = S∈C S be the vertices in the stars contained in C. Even though our
cluster is a collection of stars, we still morally think of it as a collection of vertices belonging to these
stars. Also, the center of the cluster is a real vertex a ∈ A and not a star. We say that a cluster C is
a neighbor of star Sj if
[
V (C) ∩
Γ+ (u) 6= ∅.
u∈Sj

11

For a collection of stars S 0 ⊆ S and a cluster C, define the neighboring star of C in S 0 by
[
ΓS 0 (v) .
ΓS 0 (C) =

(1)

v∈V (C)

For a clustering Ci−1 and a star Sj ∈ S, define the neighboring clusters in Ci−1 of star Sj by
Γ(Sj , Ci−1 ) = {C ∈ Ci−1 | Sj ∈ ΓS (C)} .

(2)

For a collection of unmarked stars U ⊆ S, define the unmarked star-neighborhood of a cluster C by
[
ΓU (C) =
ΓU (v) and degU (C) = |ΓU (C)|.
v∈V (C)

A cluster C is a local-maxima in its unmarked star-neighborhood, if for every other cluster C 0 with
∩ ΓU (C 0 ) 6= ∅, it holds that

ΓU (C)

(degU (C), ID(C)) > (degU (C 0 ), ID(C 0 )).
d U (C) of their unmarked star-degree
In our algorithm, the clusters C compute a 2-approximation deg
degU (C). Hence, instead of looking for clusters which are local-maxima, we will look for clusters which
are approximate local maxima. That is, clusters C satisfying
d U (C), ID(C)) > (deg
d U (C 0 ), ID(C 0 ))
(deg
for every other C 0 with ΓU (C) ∩ ΓU (C 0 ) 6= ∅.
As in Alg. NaiveSpanner, the centers of the clusters join the next level of the clustering only if
(1) their clusters are (approximate) local-maxima in their unmarked star-neighborhood; and (2) their
(approximate) unmarked star-degree is large enough. These two conditions guarantee that only a
bounded number of cluster centers joins the next level (as each of these clusters has a large set of
neighboring stars, and all these sets are disjoint).
The 0th -level clustering C0 . Recall that the collection of (vertex-disjoint) stars S is defined by
letting each vertex in b join star Si of one of its neighbors ai in A. The 0th -level of clustering C0 =
{{S1 }, . . . , {S` }} consists of all singleton stars.
We now explain how to compute the ith level of the clustering Ci given the (i−1)th level Ci−1 within
0
O(k · |A|1−i/k ) rounds. Note the star-graph is in our mind mainly for the purpose of intuition, when
implementing it, the centers Zi ⊆ A are still vertices in the original graph.
The ith Phase of Algorithm SparserBipartiteSpanner
(S1): Selecting the cluster centers Zi of the ith -clustering. We employ the following iterative
0
process for |A|1−i/k iterations. Initially, unmark all the stars of S by letting U = S. The next steps
are similar to those of Alg. NaiveSpanner with the only exception that we unmark stars rather than
vertices.
0
Let U 0 ⊆ S be the set of current unmarked stars and let Zi−1
⊆ Zi−1 be the set of cluster centers
0
that have not yet joined Zi . As in Alg. NaiveSpanner, each cluster center zj ∈ Zi−1
computes (an
U
approximation of) the unmarked star-degree deg (Cj ) of its cluster Cj .
Lemma 4.1. Every cluster center z ∈ C can compute deterministically a 2-approximation for degU (C)
0
0
within O(min(|A|1−1/k , |A|1−(i−1)/k )) rounds. In addition, once it is computed in the first iteration of
the phase, it can be maintained in each future iteration of that phase, using O(k) rounds.
12

Proof. We distinguish between the first phase and phase i for i ≥ 2. In the first phase, the cluster
d U (C) for the unmarked star-degree of their cluster.
centers z ∈ C compute only a 2-approximation deg
In phase i ≥ 2, the cluster centers z ∈ C compute the exact value degU (Cj ). The reason for this
difference is as follows. In the first phase, the 0th -clustering contains O(|A|) clusters (stars in this
case), and hence it might take up to O(|A|) rounds for each star leader to compute the list of all its
0
neighboring stars. However, in phase i ≥ 2, the (i − 1)th -level clustering contains O(|A|1−1/k ) clusters,
0
allowing stars to compute the exact number of neighboring clusters within O(|A|1−1/k ) rounds, as will
see next.
Phase i = 1: In the first phase, all clusters are simply stars. Recall that Sj , S` are neighbors if
Γ(Si ) ∩ Sj 6= ∅. The neighboring stars S` of a star Sj can be connected to the vertices of Sj in one
of two ways. Either a neighboring star S` is connected to Sj by an edge with an endpoint at aj , the
center of the star Sj , alternatively S` is connected to Sj by an edge with endpoint b`0 ∈ Sj \ {aj }.
To approximate the star-degree of Sj , the leader aj computes the number of edges in each of these
two types. By adding these two values, we achieve a 2-approximation of the degree. To compute the
edges of the first type, we let each vertex sending its star-ID to its neighbor in G. This allows the
center aj to compute the number of stars in which it has a neighbor in. To compute the number of
stars connected to Sj via a vertex in Sj \ {aj }, we do as follows: each vertex ai in A sends a single ACK
to each of its neighboring stars S` (by picking a unique neighbor in Sj arbitrarily, and sending an ACK
to it). The total number of ACKs received by the vertices in Sj is exactly the number of stars that
have a neighbor in Sj \ {aj }. Finally, by letting aj add these two values, we have a 2-approximation
for the star-degree. Note that this takes O(1) communication rounds. Hence, in each iteration of the
d U (C) by applying the above computation
first phase, the star leaders can compute their update deg
restricted to the set U of unmarked stars.
0
Phase i ≥ 2: At that phase, the clustering Ci−1 contains O(|A|1−(i−1)/k ) clusters. At the beginning
of the phase, the vertex aj ∈ Sj computes a representative vertex bj ∈ Sj with a neighbor in C 0 for
every C 0 ∈ Γ(Sj , Ci−1 ) (see Eq. (2)). That is, for each neighboring cluster C` , the center aj finds a
vertex bj,` ∈ Sj that has a neighbor in C` . This information is represented by a tuple (bj,` , C` ) for
every C` ∈ Γ(Sj , Ci−1 ). The length of this list is bounded by the number of clusters in Ci−1 , hence by
0
O(|A|1−(i−1)/k ). The leader aj sends this list to all its star members and by that, each vertex b` knows
the set of clusters C 0 ∈ Γ(Sj , Ci−1 ) that is responsible for. We next explain how the cluster centers can
now compute their (exact) star-degree. Each representative vertex bj,` sends an ACK message to one
neighbor in each of the clusters C` it is responsible for. Note that since the clusters are vertex-disjoint,
each vertex bj,` sends only one message on each of its edges. In addition, note that in every cluster C` ,
there is exactly one vertex that receives a message for each neighboring star Sj . Hence, by upcasting
the number of ACKs received by the vertices of the cluster C` , the center of the cluster C` can compute
degS (C) within O(i) rounds. Since in the beginning of phase i, all stars are unmarked, degS (C) is
0
the initial unmarked star-degree of this phase. Overall, computing degS (C) takes O(i + |A|1−(i−1)/k )
0
rounds and hence we cannot recompute this value from scratch in each of the O(|A|1−i/k ) iterations
of that phase, as stars get marked.
We next show how the cluster centers can maintain the unmarked star-degree of their cluster over
0
the O(|A|1−i/k ) iterations of this phase, when stars become marked. The goal is to have each star Sj
that got marked, send exactly one message to each neighboring cluster. Then, every cluster can count
the total number of messages it received to know how many of its neighboring stars got marked and
update its unmarked star-degree. It takes some care to make sure that exactly one message is sent
to every neighboring cluster. The key will be to use the tuples (bj,` , C` ) computed earlier, so for each
neighboring cluster C` , the corresponding vertex bj,` will be in charge of notifying the cluster C` if the
star of bj,` gets marked. Since we have computed these tuples at the beginning of the phase, and each
vertex in the star knows the neighboring clusters it is responsible for, we can ensure that each cluster

13

gets exactly one message from each neighboring star that gets marked.
More formally, assume that the number of unmarked neighboring stars was maintained by each
0
cluster up to the (t − 1)th iteration and now consider the tth iteration where stars get marked. Let Ci−1
be the set of clusters whose centers have not yet joined Zi . Note that all the current unmarked stars
0 , as otherwise they would not be unmarked at that point. That
have all their cluster neighbors in Ci−1
0 ) = Γ(S , C
is, for every unmarked star at the beginning of the tth iteration, it holds that Γ(Sj , Ci−1
j i−1 ).
At the end of the iteration, each star that becomes now marked sends a “marking” message to exactly
0 ). For each neighboring cluster C ,
one vertex b` in each of its neighboring clusters C` ∈ Γ(Sj , Ci−1
`
there is a tuple (bj,` , C` ) which was computed before, where bj,` neighbors C` . The vertices of each
0
cluster C` in Ci−1
now upcast the number x of “marked” messages they got, which allows the center of
the cluster to subtract this number from its current unmarked star-degree in order to get an updated
value for the unmarked star-degree.
In addition, we have:
0
Lemma 4.2. Every center in Zi−1
can verify if its cluster is an approximate-local-maxima (i.e., the
U
d (C), ID(C)) is larger than any other cluster it shares an unmarked star
value it computed for (deg

neighbor with) within O(i) rounds.
Proof. The procedure is very similar to the one used in the standard algorithm NaiveSpanner. Each
d U (C), ID(C)) to every neighboring star (either marked or not).
cluster has all of its vertices send (deg
Every vertex bj ∈ Sj then sends the largest tuple it received to the center aj of its star. The center of
the stars aj ∈ Sj computes the largest tuple they received and sends this tuple to all the vertices in
their Sj . These vertices then send an ACK to all their neighbors which originally sent this maximal
message. If a cluster received a message from all its edges, then it is an approximate local maxima.
Since communication within clusters can be done in O(i) rounds, the round complexity follows.
d U (C) ≥ |A|i/k0 .
Every cluster-center of an (approximate) local-maxima cluster joins Zi only if deg
We call such a cluster a successful cluster. Every star Sj that has a neighboring cluster which is
successful marks itself.
(SII): Taking care of unclustered stars. Let U 0 be the remaining unmarked stars and let Ci0 be
the remaining clusters in Ci−1 whose centers did not join Zi . At this point, we let each cluster C ∈ Ci0
0
add one edge to each of its neighboring unmarked stars in ΓU (C).
0

Lemma 4.3. Step (SII) takes O(i + |A|i/k ) rounds.
0

Proof. Each of the remaining clusters in Ci0 has O(|A|i/k ) unmarked stars in U 0 . Hence, the cluster
0
center can compute a list of its neighboring unmarked stars in O(|A|1/k ) rounds. It can also, within
0
O(|A|i/k ) rounds, compute for each unmarked star, a neighbor in its cluster, and thus create a list of
tuples (Sj , v), where for each neighboring unmarked star Sj there is a vertex v ∈ C in the cluster such
0
that v neighbors Sj . The cluster center sends this list of tuples to the entire cluster in O(i + |A|1−1/k )
rounds. As a result, every vertex v ∈ C that is assigned to Sj , adds an edge to one neighbor in Sj
(SIII): Defining the clusters of Ci . This is done as in Baswana-Sen – building a BFS tree up to
depth i, only in the star-graph, while breaking ties based on distance and cluster-ID. This can be done
by running a BFS on the star-graph, centered at each cluster center. When a star joins a BFS tree, its
center informs all of the other vertices in the star of the cluster which was joined. In the case where
there is a tie, and two BFS trees reach the same star at the same depth, the star will choose which of
the clusters to join based on the cluster IDs.

14

We now describe the next phase of the algorithm, which is done after the (k 0 −1)th level of clustering
has been computed.
Last phase: After applying the above for (k 0 − 1) phases, in the (k 0 − 1)th -level of clustering, we have
0
O(|A|1−1/k ) clusters of radius (k 0 − 1) in the star-graph. At this point, each star Sj adds to H an
edge to one of its neighbors in each of its neighboring clusters. This completes the description of the
algorithm.
We now proceed to analyze the number of rounds and provide a stretch and size analysis for the
output spanner.
0

Size Analysis. We show that the output spanner contains O(k|A|1+1/k + |B|) edges. Initially, when
each vertex of B joins a star centered at A, we add |B| edges to the spanner.
We now bound the number of edges added when constructing the ith clustering Ci from the (i − 1)th
clustering Ci−1 . Every cluster of the (i − 1)th -clustering that joins the ith -clustering has a unmarked
0
star-degree at least |A|i/k at the time it joined. Since the unmarked star-neighborhoods of the elected
0
clusters are disjoint (since when a cluster is chosen, it marks its neighbors), there are at most |A|1−i/k
0
clusters whose centers join ith -clustering. Also, there are |A|1−i/k iterations for electing the cluster of
0
locally maximal unmarked star-degree. Let Ci−1
be the remaining clusters whose cluster centers did
0
0
0
not join Zi and let U be the remaining unmarked stars. It then holds that degU (C) ≤ |A|i/k .
Each one of these non-chosen clusters adds to H one edge to each of its unmarked star-neighbors.
0
Since there are O(|A|i/k ) such star neighbors for each cluster, and O(|A|1−(i−1)/k ) clusters, overall,
0
0
0
this adds O(|A|i/k |A|1−(i−1)/k ) = O(|A|1+1/k ) edges to the spanner. Summing over all k 0 phases give
0
a total of O(k 0 |A|1−1/k ) edges that were added to the spanner.
0
0
0
At the end of these k 0 phases, the (k − 1)th -clustering has O(|A|1−(k −1)/k ) = O(|A|1/k ) clusters.
For each such cluster, the partial spanner contains a BFS tree of radius (k 0 − 1), which adds O(|V |) =
O(|A| + |B|) edges. At this point, we let each vertex in A add an edge to each of its neighboring
0
0
0
clusters. In total, this adds O(|A|) · O(|A|1−(k −1)/k ) = O(|A|1+1/k ) edges to the spanner.
0
Summing over all of the above gives the desired bound of O(k 0 |A|1+1/k +|B|) = O(k|A|1+2/k +|B|).
Stretch Analysis. Consider an edge (va , vb ) ∈ A × B. Either at some point one of va or vb got
unclustered, or both were clustered throughout. First, we deal with the case where at least one of va
or vb became unclustered. Assume without loss of generality, that va stopped being clustered for the
first time at step i not after vb (in the case where vb became unclustered first, the argument proceeds
identically). That is, both the stars of va and vb are clustered in the (i − 1)th -clustering Ci−1 , but the
star of va is unclustered in Ci . The cluster of vb in the (i − 1)th -clustering added one edge to each
neighboring unclustered star. In particular, it adds an edge to the star containing va . Since the cluster
of vb has radius i − 1 in the star-graph, the distance from vb to va in the star-graph is at most (2i − 1).
Since i ≤ k 0 , in the original graph their distance is at most 4k 0 − 1 = 2k − 1.
We now deal with the remaining case where va and vb are both clustered throughout. So, in
particular, va and vb are in the (k 0 −1)th clustering. after the (k 0 −1)th clustering, each star neighboring
the cluster of va adds an edge to the cluster of va . In particular, the star of vb will add an edge to the
cluster of va . Hence, the distance from the star of va to the star of vb in the spanner induced on the
star-graph will be at most 2k 0 − 1, and therefore in the original graph their distance will be at most
2(2k 0 − 1) + 1 = 2k − 1, as desired.
Round Complexity. We now turn to bound the number of rounds of the algorithm. Consider the
ith -step, where we construct the ith -clustering. We will analyze the number of rounds taken by Step
(SI), (SII), and (SIII) separately. Steps (SI) and (SII) take the most time, with (SIII) being faster in
comparison.
First, we analyze the round complexity of Step (SI). For each cluster in the (i−1)th clustering, com0
0
puting its unmarked star degree, the number of neighboring unmarked stars, takes O(min(|A|1−1/k , |A|1−(i−1)/k ))

15

0

rounds by Lemma 4.1. Summing over all i from 1 to k 0 − 1 gives O(|A|1−1/k ) = O(|A|1−2/k ). Then,
to check if a cluster is a local maxima takes O(i) rounds by Lemma 4.2.
0
Step (SII) takes a total of O(i + |A|i/k ) rounds by Lemma 4.3. Summing over all i from 1 to
0
k 0 − 1 gives O(k 02 + |A|1−1/k ) = O(k 2 + |A|1−2/k ) rounds. If k 2 is comparable with |A|1−2/k , then
we can simply add a spanner with k 0 = 10, thus having an edge bound of O(|A|1+1/10 + |B|) ≤
O(k|A|1+1/k + |B|) edges in the spanner, as desired. Furthermore, the number of rounds required will
be O(|A|1−1/10 ) ≤ O(|A|1−2/k ). Thus, we can ignore the additive factor of k 2 , achieving a bound of
O(|A|1−2/k ) rounds.
Step (SIII) takes time O(i), as in Baswana-Sen.
This completes the proof of Lemma 1.2. For odd k, we get a similar algorithm and analysis. The
only difference is that instead of constructing a (k − 1)-spanner of the star-graph, we construct a
(k − 2)-spanner of the star-graph. This results in:
Lemma 4.4 (Bipartite Spanners: Odd k). Let G = (A ∪ B, E) be a bipartite graph.Then one can construct a (2k − 1)-spanner with O(k|A|1+2/(k−1) + |B|) edges within O(|A| + k 2 ) rounds in the CONGEST
model for odd k ≥ 3.

4.3

Key Tool (II): Superclustering – Grouping Baswana-Sen Clusters

Why Superclusters? In this section, we describe the main tool that allows us to speed up Alg.
√
NaiveSpanner by a factor of n. The idea is to group the n1−i/k clusters in the ith -clustering Ci
√
into n superclusters, each containing O(n1/2−i/k ) clusters. Then, instead of iterating over clusters
one by one (as in Alg. NaiveSpanner), we iterate over the superclusters. Each time, either all the
cluster centers of a given supercluster join the next level of clustering, or none of them join. As will
be shown later, in order to construct the ith -clustering Ci , it will be sufficient for our algorithm to
√
consider n1/2−1/k superclusters (and not all n superclusters), hence yielding the round complexity
of O(n1/2−1/k ) (for fixed k). For a supercluster to compute the number of its (unmarked) neighbors,
all cluster centers in a given supercluster should be able to communicate efficiently. For that purpose,
we make sure that the cluster centers in each supercluster are connected by an O(2k )-depth tree9 ,
and that the trees of different superclusters are edge-disjoint. These trees will allow us to aggregate
information to leader of each supercluster in parallel, see Fig. 2.
Defining the Superclusters. Let Ci be a collection of O(n1−i/k ) i-clusters. A supercluster SCi,j =
{Cj1 , . . . , Cj` } is a collection of clusters from Ci . SA Superclustering SC i = {SCi,1 , . . . , SCi,p } is a
covering partition of all clusters from Ci . That is, pj=1 SCi,j = Ci , and the superclusters are clusterdisjoint (every cluster in Ci belongs to exactly one supercluster). To select the cluster centers of level
i, the algorithm constructs in each phase i ∈ {1, . . . , k/2} a superclustering SC i which satisfies some
helpful properties. We call a superclustering satisfying these properties a nice superclustering. Before
defining the properties of a nice S
supercluster, we introduce some notation. For a supercluster SCi,j =

Cj1 , . . . , Cjp , let V (SCi,j ) = C∈SCi,j C be the set of all vertices in its clusters and NV (SCi,j ) =
|V (SCi,j )| be the number of vertices in the supercluster SCi,j . Also, let NC (SCi,j ) denote the number
of clusters that the supercluster SCi,j contains. A supercluster SCi,j with only one cluster (i.e.,
NC (SCi,j ) = 1) is called a singleton. In addition, a singleton supercluster is called a small-singleton
√
√
if NV (SCi,j ) ≤ n (otherwise, if NV (SCi,j ) > n, it is a large-singleton). Our (2k − 1)-spanner
construction is based upon the construction of superclusters with some nice useful properties, as
defined next.
√
Nice Superclustering. A superclustering SC i = {SCi,1 , . . . , SCi,` } is nice if it contains ` = O( n)
superclusters, and each of these superclusters SCi,j ∈ SC i satisfies the following:
9

This bound arises in Appendix B and will be discussed later on.

16

𝑆𝐶𝑖,𝑗

𝑠ℓ
𝒊

𝐶ℓ
1 𝑖

𝑂(𝑛2−𝑘 )

Figure 2: Illustration of the superclusters. Left: Baswana-Sen clusters are shown in blue circles. Each
such cluster C` contains a center s` and a BFS tree of depth i rooted at s` spans all the vertices of
the cluster. The supercluster SCi,j groups these clusters by adding a low-diameter tree that connects
all the cluster centers. It might be the case that the vertices connecting the centers are vertices that
belong to clusters; either in the same supercluster or in another one. Since the trees are edge disjoint,
this does not increase congestion (by more than factor 2) in any case. Right: The collection of all
√
O(n1−i/k ) clusters in the ith -level of the clustering grouped into O( n) superclusters.
√
(N0) [Singleton] If NV (SCi,j ) = Ω( n), then NC (SCi,j ) = 1.
Every non-singleton supercluster SCi,j (i.e., every supercluster containing at least two clusters) satisfies:
(N1) [Cluster Balance] NC (SCi,j ) = O(n1/2−i/k ), and
√
(N2) [Vertex Balance] NV (SCi,j ) = O( n).
(N3) [Connectivity] In the graph G, each SCi,j ∈ SC i has a tree T (SCi,j ) of depth10 O(2k ). In
addition, the trees T (SCi,1 ), . . . , T (SCi,` ) are edge-disjoint.
Intuitive discussion of these properties. Property (N0) implies that if a supercluster has many
√
vertices (more than n), then it is a singleton supercluster. Property (N1) implies that non-singleton
superclusters with at least two clusters are balanced with respect to the number of clusters from
Ci that they contain. Since there are O(n1−i/k ) clusters in the ith clustering, dividing it “fairly”
√
between n superclusters yields this bound. Property (N2) also implies a balance among non-singleton
superclusters, but this time with respect to the number of vertices. Finally, Property (N3) provides
the existence of a O(2k )-depth tree that connects the cluster centers of that supercluster. This “weird”
looking depth of O(2k ) shows up when computing the 0th -level superclustering for general graphs (for
graphs of constant diameter a much simpler construction exists). In particular, it shows up in Step
(SI) of Alg. ConsZeroSuperclustering described in Appendix B. Finally, (N4) requires these trees to be
edge-disjoint to allow communication within different superclusters, in parallel without congestion.
As will be shown in the next subsection, to satisfy Properties (N1) and (N2), the construction of
the ith -level of superclustering requires to partition both the vertices and the clusters into balanced the
√
n superclusters. The next lemma describes the key tool to achieve it.
The Balanced Partitioning Lemma. The input to the partitioning lemma is a vertex-weighted
tree T , where every vertex v in T has a non-negative weight w(v) and in addition, we are given a bound
10
When the diameter of the original graph G is O(1), the diameter of T (SCi,j ) = O(1). The term O(2k ) appears when
dealing with graphs of large diameter, and will become clear in Section B.

17

B on the allowed total weight of each tree. The goal is to partition the tree into edge-disjoint subtrees,
such that, all but one of the subtrees have a weight in [B, 2B]. The lemma achieves this but with some
subtle specification. It partitions the vertices of the tree T into p disjoint sets: Vb (T0 ), Vb (T1 ), . . . , Vb (Tp ).
The total weight of each set Vb (Ti ), except for at most one, Vb (T0 ), is bounded by [B, 2B]. Hence, the
partition respects the weight bound. Next, each set Vb (Ti ) is connected by a subtree Ti ⊆ T . The
important feature of these trees Ti is that they might contain an additional vertex v ∈ V (T ) \ Vb (Ti ).
This additional vertex v, if exists, is the root of Ti and it is essential to connect the vertices in Vb (Ti ).
Intuitively, this additional vertex helps us to communicate between the vertices of Vb (Ti ). Even though
the trees Ti are not vertex disjoint, they are shown to be edge disjoint, which is sufficient for our
applications.
Lemma 4.5 (Balanced Partitioning Lemma). In O(diam(T )) rounds, one can construct subtrees
T0 , T1 , . . . , Tp ⊆ T, with roots r(T0 ), r(T1 ), . . . r(Tp ) and corresponding disjoint vertex sets
Vb (T0 ), Vb (T1 ), . . . , Vb (Tp )
such that:
S
(D1) The Vb (Ti ) sets are vertex disjoint and pi=1 Vb (Ti ) = V (T ).
(D2) W (Ti ) ∈ [B, 2B] for every i ≥ 1, and W (T0 ) ≤ 2B where W (Ti ) =

P
u∈Vb (Ti )

w(u).

(D3) V (Ti ) = Vb (Ti ) ∪ r(Ti ).
(D4) All T0 , . . . , Tp are edge-disjoint and with diameter at most diam(T ).
Intuitively, the important vertex set of the tree Ti is the set of vertices Vb (Ti ) and hence the weight
of the tree in Property (D2) is defined by summing over all these vertices (instead of summing over all
vertices in the tree). Property (D3) implies that the tree Ti might contain, in addition to Vb (Ti ), also
an additional vertex – its root – that allows the connectivity of the set Vb (Ti ) in Ti . The full proof of
Lemma 4.5 appears Appendix A. In the common application of this lemma, the tree T is a tree that
connects the cluster-centers of a given supercluster, these cluster-centers are given a weight (e.g., the
size of their cluster) and the remaining vertices in T are given a zero weight. The bound corresponds
to the maximum allowed number of clusters (or vertices) in the supercluster (as in 4.3(N2,N3)).

4.4

(2k − 1)-Spanners in O(2k · n1/2−1/k ) Rounds

We first consider the construction for graphs with constant diameter. At the end of the section, and in
Section B we discuss the extension for general graphs with arbitrary diameter. Recall that for i ≤ k/2,
Ci is a clustering that contains O(n1−i/k ) vertex-disjoint clusters centered at the vertices Zi . The set
of i-clustered vertices Vi are in Γi (Zi ).
The first part of the algorithm contains k/2 phases. In each phase i ∈ {1, . . . , k/2}, we are given a
(i − 1)th nice superclustering SC i−1 (whose superclusters contain the clusters of Ci−1 ) and the current
spanner H. We then construct the ith nice superclustering SC i and add edges to H in order to take
care of the newly unclustered vertices in Vi−1 \ Vi . At the end of the first part, we have a (k/2)th
√
superclustering SC k/2 with O( n) clusters. At that point, the number of clusters is small enough, and
so Alg. NaiveSpanner can be applied.
Constructing the 0th -level superclustering SC 0 in O(diam(G)) rounds. To compute SC 0 , we
apply the Partitioning Lemma 4.5 on a BFS tree T rooted at some arbitrary vertex (e.g., of maximum
√
ID) using weights of w(v) = 1 for each v ∈ V and bound B = O( n). This partitions the vertices into
√
√
Θ( n) subsets Si , each of size O( n). Each such subset Si = {vi,0 , . . . , vi,` } defines a supercluster
18

√
SC0,i = {{vi0 }, . . . , {vi,` }} containing the singleton clusters of Si ’s vertices. By that, we get O( n)
superclusters SC 0 = {SC0,1 , . . . , SC0,√n }. By the partitioning lemma, we also have a tree Ti for each
SC0,i , satisfying Prop. (N3).
The ith phase of Algorithm ImprovedSpanner for i ∈ {1, . . . , k/2}. At the beginning of the phase,
we are given the (i − 1)th -clustering Ci−1 grouped into the nice superclustering SC i−1 . Our first goal is
to use the superclustering SC i−1 to define the set of new O(n1−i/k ) cluster centers Zi . The high-level
idea here is to implement Alg. NaiveSpanner on each supercluster rather than on each cluster. Given
a set U of unmarked vertices and a supercluster SC ∈ SC i−1 , define its unmarked neighborhood and
unmarked degree by
[
(Γ+ (v) ∩ U ) and degU (SC) = |ΓU (SC)| .
(3)
ΓU (SC) =
v∈V (SC)

Similarly to before, we say that a supercluster SC is a local-maxima in its unmarked neighborhood, if
for every other SC 0 such that ΓU (SC) ∩ ΓU (SC 0 ) 6= ∅, it holds that
(degU (SC), ID(SC)) > (degU (SC 0 ), ID(SC 0 )).
We say that supercluster SC has low-expansion if degU (SC) ≤ n1/2+1/k . Otherwise, it has highexpansion. Note that unlike the previous algorithms presented before, here the expansion threshold
n1/2+1/k is independent11 of the level i. See Table 1 for a summary of notation.
Notation
Ci
Zi
Vi
SC i
SCi,j
U
Γ (C), degU (C)
ΓU (SC), degU (SC)

Local-maxima (super)cluster
Successful (super)cluster

Meaning
The i-level of clustering containing O(n1−i/k ) clusters
The cluster centers of Ci .
The vertices that are i-clustered, i.e., Vi = Γi (Zi )
Superclustering at level i:
√
A partition of the O(n1−i/k ) clusters of Ci into n groups
Supercluster in SC i containing a subset of O(n1/2−i/k ) clusters
belonging to Ci
The unmarked neighborhood, degree of cluster C
The unmarked degree of supercluster SC
(Super)cluster that has the maximum unmarked degree
in its unmarked neighborhood, breaking ties based on ID
Local-maxima supercluster (cluster) with large unmarked degree

Page
9
9
9
16
16
9
18

9,18
9,18

Table 1: List of notation
Step (S1) of phase i: Selecting the centers Zi . Selecting the O(n1−i/k ) cluster centers of Zi is
done in O(n1/2−1/k ) iterations. We start by unmarking all vertices. At each iteration, we have a set U
of remaining unmarked vertices and a subset of remaining superclusters SC 0i−1 of superclusters whose
cluster centers have not yet been added to Zi . All superclusters SC ∈ SC 0i−1 compute their unmarked
degree degU (SC) in parallel. (This can be done in O(i · 2k ) rounds thanks to Prop. (N3) in Desc. 4.3).
Definition 4.6 (Successful Supercluster). A supercluster SC that is local-maxima in its unmarked
neighborhood and has high-expansion, that is degU (SC) ≥ n1/2+1/k , is called a successful supercluster.
11

The intuition is that in each level i, the superclusters have at most
if the size of its neighborhood size is factor n1/k larger.

19

√

n vertices, and we say that it has high expansion

It is easy to see that the leader (vertex v of maximum ID in V (SC)) of every supercluster SC can
verify in O(i · 2k ) rounds whether it is a local-maxima in its unmarked neighborhood.
In the algorithm, each successful supercluster SC adds all its cluster centers to Zi , and mark all
the vertices in ΓU (SC). This continues for O(n1/2−1/k ) iterations.
As we will show in the analysis section, since the unmarked neighborhoods of successful superclusters are disjoint and large, there are at most O(n1/2−1/k ) such superclusters. In addition, by Prop. (N2),
each supercluster has O(n1/2−(i−1)/k ) clusters, overall |Zi | = O(n1/2−(i−1)/k · n1/2−1/k ) = O(n1−i/k ) as
desired.
Step (S2) of phase i: Taking care of unclustered vertices. After O(n1/2−1/k ) steps of computing successful superclusters, all remaining superclusters SC have low-expansion with respect to the
remaining unmarked vertices U 0 . That is, degU (SC) ≤ n1/2−1/k . First, we take care of the singleton
superclusters.
(S2.1): Singleton supercluster SC with low-expansion: Each unmarked vertex u ∈ U 0 add
√
to H an edge to one of its neighbor in Γ(u) ∩ V (SC). Since there are O( n) superclusters, each with
0
degU (SC) ≤ n1/2+1/k , overall we add O(n1+1/k ) such edges.
(S2.2): Non-singleton superclusters SC with low-expansion: Here, the construction of sparser
spanners for bipartite graphs comes into play (see Sec. 4.2). Recall that by Prop. (N2), NV (SC) =
√
0
0
O( n) vertices. Let ΓU ,− (SC) = ΓU (SC) \ V (SC) be the unmarked neighbors of SC excluding
0
the vertices of the supercluster SC. Since SC has low-expansion, it also holds that |ΓU ,− (SC)| =
0
O(n1/2−1/k ). For every such supercluster SC, we consider the bipartite graph B(SC) = (V (SC), ΓU ,− (SC)),
and apply Alg. SparserBipartiteSpanner to compute for it a (2k − 1)-spanner H(SC) ⊆ B(SC) with
O(n1/2+1/k ) edges (see Lemma 1.2). This is done for all the graphs B(SC) in parallel.
Note that the graphs B(SC) are not necessarily vertex disjoint since an unmarked vertex can
appear in several such graphs. The key observation that allows the parallel computation of all these
spanners, is that every edge (u, v) can belong to at most two bipartite graphs, say, B(SC) and B(SC 0 ),
√
where SC, SC 0 is the supercluster of u, v respectively12 . Overall, since there are O( n) superclusters,
this adds O(n1/2 · n1/2+1/k ) = O(n1+1/k ) edges.
Finally, it remains to take care of all edges between vertices belonging to the same supercluster.
Note that in Alg. NaiveSpanner, there was no need for such a step since all vertices belonging to the
same cluster are connected in H by an i-depth BFS tree rooted at the cluster center. However, in
our setting, vertices that belong to different clusters of the same superclusters might still have large
stretch (as cluster centers of the same supercluster might be at distance O(2k ) in G). At that point,
√
we use the fact that all superclusters are vertex disjoint and each contains O( n) vertices. We then
recursively apply the algorithm ImprovedSpanner on each of these superclusters in parallel. That is,
we apply ImprovedSpanner on the induced subgraph on V (SC) for every such supercluster SC.
Note that since in each phase we unmark all the vertices, unclustered vertices can become clustered
again and in particular, edges between newly unclustered vertices and clustered vertices will be taken
care of later on. This completes the description of the second step. See Fig. 3 for an illustration.
Steps (SIII) and (SIV): Defining ith -clustering and the ith -superclustering: The clusters
Ci centered at the cluster centers Zi computed at step (SI) are computed exactly as in Baswana-Sen
Algorithm. The depth i-trees of these clusters are added to the spanner. The main challenge here is to
√
re-group the new O(n1−i/k ) clusters into O( n) superclusters, in a way that satisfies all the properties
of the nice superclustering mentioned in Desc. 4.3.
Our starting point is as follows: we have a collection of O(n1/2−1/k ) successful superclusters SC ∈
SC i−1 whose cluster centers joined Zi . Since SC i−1 is nice, by Prop. (N3), each such supercluster SC
12

Recall that the superclusters share no vertex in common.

20

Γ 𝑈 𝑆𝐶 − 𝑉(𝑆𝐶)
𝐶ℓ
Construct spanner
recursively

Figure 3: Shown is supercluster SC of low-expansion. To provide a good stretch for the edges
between its vertices – we apply Alg. ImprovedSpanner recursively. To provide a good stretch between
the supercluster vertices and its unmarked neighbors, we apply Alg. SparserBipartiteSpanner.

has a tree T (SC) of depth O(2k ) that spans all its cluster centers.
√
First, we let each cluster C ∈ Ci with Ω( n) vertices, to define its own singleton superclusters.
√
Since clusters are vertex disjoint, there are O( n) such superclusters. It now remains to re-group the
√
remaining clusters of Ci into O( n) superclusters.
√
For each successful supercluster SC, we now consider only its centers of clusters with O( n)
vertices. First, we consider Property (N1) and use Lemma 4.5 with the tree T (SC), weights w(z) = 1
√
for every cluster-center z of SC (only those that have O( n) vertices in their cluster) and bound
B = O(n1/2−i/k ). All other vertices v 0 in T (SC) have w(v 0 ) = 0 (in particular, the centers z of clusters
in SC which have been turned into singleton superclusters, we set w(z) = 0). By Prop. (N2) for
SC i−1 , we know that SC ∈ SC i−1 has O(n1/2−(i−1)/k ) cluster centers. Hence, the partition procedure
will partition each of these superclusters into O(n1/k ) superclusters SC1 , . . . , SC` . In addition, by
Lemma 4.5(D5), all these resulting superclusters SCj are equipped with edge-disjoint trees T (SCj ) of
diameter O(2k ). Since there are O(n1/2−1/k ) successful superclusters, overall after this partition there
are O(n1/2−1/k ) · O(n1/k ) superclusters.
We then turn to property (N3), and farther partition the superclusters to obtain a balance partition
of the vertices into superclusters. For that purpose, for each supercluster SC 0 (obtained from the step
√
above), we again apply the Partitioning Lemma on T (SC 0 ). This time we use B = n and the weight
w(z) of each cluster center z in SC 0 is the number of vertices in its cluster C, that is w(z) = |C| (for
clusters v 0 which have turned into singleton superclusters, or any other non-center vertex in T (SC 0 ),
we set w(v 0 ) = 0). Since the vertices of superclusters are disjoint, this step increase the number of
√
superclusters only by an additive O( n) term. Hence, overall the number of superclusters is kept
√
bounded by O( n). This completes the description of the ith phase of Alg. ImprovedSpanner.
√
The terminating step k/2. At the (k/2)th step we have O( n) superclusters, each containing
√
O(1) clusters, hence overall we have O( n) clusters. Now we can afford using Algorithm NaiveSpanner
(described near the beginning of Section 4), which iterates over the clusters one by one. This completes
the description of the algorithm for graph with diam(G) = O(1). For a summary of the algorithm, see
below.

21

Phase i of Algorithm ImprovedSpanner
(SI): Defining the centers Zi .
Set SC 0i−1 ← SC i−1 , U = V and for O(n1/2−1/k ) steps do the following:
• Each remaining supercluster SCi,j ∈ SC 0i−1 computes degU (SCi,j ).
• The cluster-centers of local-maxima superclusters SCi,j ∈ SC 0i−1 and with
degU (SCi,j ) ≥ n1/2+1/k join Zi . We call these superclusters successful.
• Remove the successful superclusters SCi−1,j from SC 0i−1 and mark the vertices ΓU (SCi−1,j ).
(SII): Taking care of unclustered clusters. At that point, all remaining superclusters
SCi−1,j ∈ SC 0i−1 have degU (SCi,j ) ≤ n1/2+1/k .
• For every singleton supercluster SCi−1,j ∈ SC 0i−1 do the following:
– For each unmarked vertex u ∈ ΓU (SCi−1,j ), add one edge (u, v) to some
v ∈ V (SCi−1,j ) ∩ Γ(u).
• Consider all remaining non-singleton superclusters SCi−1,j ∈ SC 0i−1 .
U
• Let ΓU,−
i,j = Γ (SCi−1,j ) \ V (SCi−1,j ).

• Let Bi,j = (V (SCi−1,j ), ΓU,−
i,j ) be the corresponding bipartite graph.
– Taking care of edges in V (SCi−1,j ) × ΓU,−
i,j :
∗ Apply Alg. SparserBipartiteSpanner on each Bi,j to compute (2k − 1)-spanners
Hi,j and add these Hi,j spanners to H.
– Taking care of edges in V (SCi−1,j ) × V (SCi−1,j ):
∗ Apply Algorithm ImprovedSpanner recursively on G(V (SCi−1,j )).
(SIII): Forming the Ci clusters centered at Zi . As in Baswana-Sen. Add the edges of the
i-depth trees of each cluster to the spanner.
(SIV): Defining the ith -superclustering SC i .
√
• Let each cluster C ∈ Ci with Ω( n) vertices form its own supercluster (i.e., singleton
supercluster).
• For each successful supercluster SCi−1,j do the following:
– Balance w.r.t. number of clusters: Use the Partitioning Lemma 4.5 to partition
the superclusters into cluster-balanced superclusters – each containing O(n1/2−i/k )
(small) clusters.
– Balance w.r.t. number of vertices: Use the Partitioning Lemma 4.5 again, on
each of the resulting superclusters from above, to further partition them into
√
vertex-balanced superclusters, each with O( n) vertices.

4.5

Analysis of ImprovedSpanner for Graphs with diam(G) = O(1)

Stretch Analysis. We begin by showing that the output subgraph is a (2k − 1) spanner. A vertex v
is i-clustered if it belongs to Vi , i.e., belongs to one of the clusters C belonging to a supercluster SCi,j
of the ith -superclustering SC i . Otherwise, it is i-unclustered. Consider an edge (u, v) ∈ G \ H. Let
r(u) be the largest index such that u is r(u)-clustered. The index r(v) is defined similarly. Without
loss of generality, assume that r(u) ≤ r(v).
First, consider the case where r(v) + 1 < k, let i = r(v) + 1. Hence, v is (i − 1)-clustered but both
22

u and v are i-unclustered. Let v be in cluster C ∈ SCi−1,j . Since at step i, u is unclustered, it remains
unmarked after computing all the superclusters with high-expansion at the ith phase.
Case 1: u and v belong to the same cluster C. Since H contains a BFS tree of depth i that spans all
the vertices of C, we have that dist(u, v, H) ≤ 2i − 1.
Case 2: u and v belong to different clusters in the same supercluster SCi−1,j . In such a case, by
definition, SCi−1,j is not singleton. Recall that the graph G0i,j is the induced subgraph on V (SCi−1,j ),
hence (u, v) ∈ G0i,j . Since the algorithm computes a (2k − 1)-spanner to the graph G0i,j , the edge (u, v)
has a stretch of at most 2k − 1 in H.
Case 3: u and v belong to clusters of different superclusters. In this case, the edge (u, v) is the in
the bipartite graph Bi,j = (SCi−1,j , ΓU,−
(SCi−1,j )), where ΓU,−
(SCi−1,j ) = ΓU
i (SCi−1,j ) \ V (SCi−1,j ).
i
i
Since we add to H a (2k − 1)-spanner for Bi,j , the edge (u, v) has a stretch of at most (2k − 1) in H.
Case 4: u unclustered. In this case, the edge (u, v) is the in the bipartite graph
Bi,j = (SCi−1,j , ΓU,−
(SCi−1,j )).
i
Since we add to H a (2k − 1)-spanner for Bi,j , the edge (u, v) has a stretch of at most (2k − 1) in H.
Finally, consider the case where r(v) = k − 1. In the last stage the cluster containing v adds an
edge to each neighboring vertex, including u. Hence, since the radius of the cluster of u is k − 1, the
distance in H from u to v is at most 2k − 1, as desired.
Size Analysis. We proceed by showing that the output subgraph contains O(k · n1+1/k ) edges. At
the step of computing the ith -superclustering, we add the following edges to the spanner H. For the
clusters in a supercluster that has high-expansion, we add BFS trees of depth i rooted at their centers.
Since the clusters are vertex-disjoint, in total we add O(n) edge to the spanner. For each supercluster
SCi−1,j of low-expansion, we first use Lemma 1.2 to construct a (2k − 1)-spanner for the bipartite
√
graph Bi,j = (SCi−1,j , ΓU,− (SCi−1,j )) with O(k · n1/2+1/k ) edges. Since there are O( n) superclusters
in SC i , this adds O(kn1+1/k ) edges to the spanner H.
Next, we bound the number of edges added in Step (SII) of phase i, due to the computation of
the (2k − 1)-spanners for each of the induced subgraphs G0i,j on the vertices of V (SCi−1,j ) for every
supercluster SCi−1,j ∈ SC i of low-expansion. Since this is done only for non-singleton superclusters,
√
√
by Prop. (N2) of the nice superclustering, |V (SCi−1,j )| = O( n). Since there are O( n) superclusters
√
√ 1+1/k
in the superclustering SC i−1 , in total it adds O( n) · O(( n)
) = O(n1+1/2k ) edges.
√
After k/2 phases of Alg. ImprovedSpanner, we have O( n) clusters and at that point we apply
Alg. NaiveSpanner on these remaining clusters (i.e., it is like starting Alg. NaiveSpanner from (k/2)th
phase). This adds only O(kn1+1/k ) edges to the spanner by using the exact same argument as in Sec.
4.1. Finally, in the terminating part, where we only have O(n1/k ) clusters, we add O(n1/k ) edges for
each vertex (i.e., each vertex v adds an edge to one neighbor u ∈ C ∩ Γ(v) for every cluster C), for a
total of O(n1+1/k ) edges as well. This completes the size analysis of the spanner.
Round Complexity. By Lemma 4.7, constructing the 0th -superclustering SC 0 takes O(2k · n1/2−1/k )
rounds. We now claim that for i ≥ 1, constructing the ith -superclustering from the (i − 1)th superclustering takes O(2k · n1/2−1/k ) rounds. By property (N3), the centers of all clusters in supercluster SCi−1,j are connected by subgraph of depth O(2k ). Since these subgraphs are edge-disjoint,
the unmarked degree of all the superclusters SCi−1,j ∈ SC i−1 can be computed in O(i · 2k ) rounds.
We now consider step (S2). By Lemma 1.2, constructing a (2k − 1)-spanners for a bipartite graphs
Bi,j = (V (SCi−1,j ), ΓU,−
(SCi−1,j )) takes O(k · n1/2−1/k ) rounds, and since each edge is contained in at
i
most two of these subgraphs, all these spanners can be constructed in parallel within O(k · n1/2−1/k )
rounds (while slowing down the algorithm of Lemma 1.2 by a factor of 2, due to the congestion).
Next, the algorithm considers all the non-singleton superclusters SCi−1,j with low-expansion and
recursively computes a (2k − 1)-spanner for the subgraph G0i,j (the induced subgraph on the vertices of
SCi−1,j ). Since the superclusters are vertex disjoint and this is done only for non-singleton superclusters
23

√
√
SCi−1,j which by Prop. (N2) consists of O( n) vertices, it takes O(( n)1/2−1/k ) = O(n1/4 ) rounds,
for all these superclusters in parallel.
√
After k/2 phases, we have n clusters and at that point, applying Alg. NaiveSpanner for k/2 − 1
phases takes O(k · n1/2−1/k ) rounds. The terminating part, where we have O(n1/k ) clusters, and each
vertex adds an edge to a unique neighbor in each these clusters takes O(1) rounds.
Extension for general graphs of diameter diam(G). The only step that requires adaptation is
that of constructing the 0th -level superclustering SC 0 . In Appendix B, we show:
Lemma 4.7. One can construct in O(2k ·n1/2−1/k ) rounds, nice superclustering SC 0 = {SC0,1 , . . . , SC0,p }
along with a subgraph H 0 with O(kn1+1/k ) edges such that for every vertex u not participating in the
clusters of these superclusters SC0,j ∈ SC 0 , it holds that dist(u, v, H 0 ) ≤ 2k − 1 for every v ∈ Γ(u).

References
[1] Leonid Barenboim, Michael Elkin, and Cyril Gavoille. A fast network-decomposition algorithm
and its applications to constant-time distributed computation. TCS, 2016.
[2] Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms, 30(4):532–563,
2007.
[3] Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures and Algorithms, 30(4):532–563,
2007.
[4] Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing local distributed
algorithms under bandwidth restrictions. CoRR, abs/1608.01689, 2016.
[5] Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized
and deterministic complexity in the local model. In FOCS, 2016.
[6] Bilel Derbel and Cyril Gavoille. Fast deterministic distributed algorithms for sparse spanners.
Theoretical Computer Science, 2008.
[7] Bilel Derbel, Cyril Gavoille, and David Peleg. Deterministic distributed construction of linear
stretch spanners in polylogarithmic time. In DISC, pages 179–192. Springer, 2007.
[8] Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. On the locality of distributed
sparse spanner construction. In PODC, pages 273–282, 2008.
[9] Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. Local computation of nearly
additive spanners. In DISC, 2009.
[10] Bilel Derbel, Mohamed Mosbah, and Akka Zemmari. Sublinear fully distributed partition with
applications. Theory of Computing Systems, 47(2):368–404, 2010.
[11] Manuela Fischer and Mohsen Ghaffari. Deterministic distributed matching: Simpler, faster, better. arXiv preprint arXiv:1703.00900, 2017.
[12] Manuela Fischer, Mohsen Ghaffari, and Khun Fabian. Deterministic distributed edge-coloring via
hypergraph maximal matching. arXiv preprint arXiv:1704.02767, 2017.

24

[13] Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. On the distributed complexity
of computing maximal matchings. SIDMA, 15(1):41–57, 2001.
[14] Alessandro Panconesi and Aravind Srinivasan. Improved distributed algorithms for coloring and
network decomposition problems. In STOC, pages 581–592. ACM, 1992.
[15] David Peleg. Distributed Computing: A Locality-sensitive Approach. SIAM, 2000.
[16] Seth Pettie. Distributed algorithms for ultrasparse spanners and linear size skeletons. Distributed
Computing, 22(3):147–166, 2010.

25

A

Partitioning Lemma 4.5

Proof. The idea of the proof is as follows: starting with root of the tree, we recursively partition each
of its children subtrees. The challenge is in combining the resulting partitions. The main obstacle is
that if each of the subtrees has a leftover set in its output partition, it is not clear how to combine the
child-partitions at the root in a way that results in only one leftover set. We deal with that problem
by merging leftover sets together. Since we only want the trees to be edge-disjoint, we allow the trees
to share one vertex in common (e.g., the root).
Let r1 , r2 , . . . , rd be the children of the root r in the tree T . Our algorithm is recursive. For the
recursion to hold, we need an additional auxiliary property:
(D5) W (T0 ) ≤ 2B and r(T0 ) = r(T ). If W (T0 ) ≤ B (we call such a T0 the leftover set), then
Vb (T0 ) = V (T0 ).
For the base case (if the tree contains only one vertex), we simply return the trivial partition.
Otherwise, we recursively apply the algorithm to each of the subtrees of r1 , . . . , rd . We now wish to
combine these d partitions to create a single balanced partition. Note that the union of these partitions
satisfies Properties (D3) and (D5). Also, it satisfies Property (D1) for all vertices except for the root r
of T . Property (D2) is not yet satisfied since there might be small leftover sets in each of the recursive
partitions. Therefore, when combining the partitions we may have up to d small sets. In order to deal
with this, we combine leftover sets together so that there will be at most one small leftover set (all
other sets will be combined so their total weight is at least B).
Suppose the leftover sets S1 , S2 , . . . , Sd have weights
W (S1 ), W (S2 ), . . . , W (Sd ) ≤ B.
We iterate over these subsets in order and group them together until the combined set S10 has weight
larger then B (i.e., S10 is the union of S1 , S2 , . . . , Si , for the smallest i such that the combined weight
is larger than B). We then proceed combining the sets Si+1 , ...Si+j , until we get another set S20 of
weight at least B. By that, we get a collection of new sets S10 , . . . , S`0 , where each except perhaps for
the last one, S`0 , has weight in [B, 2B]. We then add the root r to the trees Tj0 of each of the Sj0 for
j ∈ {1, . . . , ` − 1} but only as an auxiliary vertex to aid the communication. If the weight of the last
set S`0 is at least B, r is added to S`0 as an auxiliary communication vertex, and r becomes a singleton
leftover supercluster. Otherwise, if the weight of last set S`0 is less than B, The root r is added to the
last set S`0 . Note that in this case, even when adding r to Vb (T`0 ), we still have a total weight less than
0 . This guarantees
2B since w(r) ≤ B. If the weight of S`0 is at least B, we let r be its own set S`+1
property (D1) because all vertices other than r are in some V̂ by the recursion, and we ensure that r
is in one of the sets as well. Note that this also provides property (D2) for each of the Sj0 sets, and for
the other sets (D2) holds by the recursion.
By this construction only the last set of the Si can have weight less than B, providing property
(D2). Since only the root is common to the Sj0 sets, the resulting trees are indeed edge disjoint, thus
satisfying property (D4).
We now consider the distributed implementation. Note that at each step of the recursion, the
root r of the current subtree has all the information needed to decide on how to combine the leftover
subsets. For each child v whose subtree has a leftover subset T0 , the root r sends to v the ID of the
new vertex set Ti which T0 combined with. The child v can then propagate that information downward
to the rest of the nodes in T0 leftover subset, by that all the vertices know the tree Ti to which they
belong.

26

B

Missing Details of Alg. ImprovedSpanner for General Graphs

In this section, we prove Lemma 4.7. This is done by constructing 0th -Superclustering for graphs with
arbitrary diameter.

Constructing the 0th -Superclustering
Our goal in this section is to construct a 0th -level nice superclustering. For the properties of the nice
superclustering, please see Description 4.3. In contrast to our algorithm for O(1)-diameter graphs, the
0-superclustering SC0 would not cover all the vertices in the graph. However, for all vertices V 0 that
are uncovered by the 0-superclustering, we will add edges to the spanner H so that dist(u, v, H) ≤ V 0
for every u ∈ V 0 and v ∈ Γ(u).
We make use of the following procedure that computes ruling set in power graphs.
Tool: computing ruling-set in the power-graph. Our algorithm is based on the algorithm
Generic Spanner from [7]. It uses the (3, 4) ruling set algorithm from [14], slightly adapted to our
case to find a (3, 4) ruling set for the graph Gt , while operating in the CONGEST model on the graph
G (i.e., we find a (3t, 4t)-ruling set on G):
Lemma B.1. Given a graph G = (V, E), a subset of vertices V 0 ⊆ V (each vertex knows whether
it is in V 0 or not), and a positive integer parameter t, one can construct a subset X√ ⊆ V 0 that is a
(3, 4)-ruling set with respect to Gt and V 0 . Furthermore, the algorithm runs in t2O( log n) rounds in
the CONGEST model.
Proof. The algorithm is based on the (3, 4)-ruling set algorithm of [14]. We simply adapt their algorithm to work on the power-graph Gt instead of G. We will go through all of the steps of the algorithm,
and confirm the algorithm for Gt can be simulated in G using O(log n)-size messages. First, every
vertex v in parallel must be able to test whether d(v) ≥ g(n), where d refers to the degree in Gt . This
can be done as follows. Each vertex v sends to each of its neighbors u, the list of its neighbors Γ(v),
if |Γ(v)| < g(n). Otherwise, v sends a message specifying that |Γ(v)| ≥ g(n).
Thus, each vertex can tell whether it has high degree in G2 . If it does not have high degree, it has
a list of all its neighbors in G2 . It is simple to extend this algorithm for larger t by having t steps
where on the ith step, each vertex sends the list Γi (v) of all vertices at distance at most i (or a message
specifying that |Γi (v)| ≥ g(n)). Hence, the size of the messages sent is bounded by g(n). Overall, the
algorithm has t steps, each with messages of size g(n), which can be simulated using short messages
in a total of t · g(n) rounds.
Next, we must check whether we can compute a g(n)-coloring on a graph where all vertices have
degree less than g(n). This can be done using the standard coloring algorithm: partition the vertices
into two parts based on the last bit of their ID, then color each part, and merge. To merge, we simply
have each vertex figure out the set of colors at distance t away from it, which is possible with t rounds
with messages of size g(n).
Next, we must verify that we can find a (3, 3 log n)-ruling set. For this we use the standard
(3t, 3t log n) ruling set algorithm from [14]. Since all of the steps of the algorithm for (3, 4)-ruling
√
set on Gt can be simulated in G in tg(n) rounds, we can construct a (3t, 4t)-ruling set in t2O( log n)
rounds.
We are now ready to describe Alg. ConsZeroSuperclustering, the output of the algorithm is a nice
SC 0 along with a partial spanner H 0 .

27

Description of Algorithm ConsZeroSuperclustering
0 .
To construct the 0th -superclustering, the algorithm computes k/2 levels of pre-clustering C00 , . . . , Ck/2

Each clustering Ci0 contains O(n1−i/k ) clusters, but unlike the clustering of Baswana-Sen, the diameter
of each cluster C ∈ Ci0 is exponential in i (i.e., in Baswan-Sen, the diameter is i). Again, we denote
the cluster centers of level i, by Zi , and by Vi the set of i-clustered vertices.
√
0
After k/2 phases, the (k/2)th clustering Ck/2
contains O( n) vertex-disjoint clusters, for each
cluster C, we have a tree T (C) of diameter O(2k ) that spans all the vertices in C. We then turn these
O(2k )-diameter clusters into superclusters in SC 0 .
We begin by describing phase i for i ∈ {1, . . . , k/2}. The following definitions are useful. For every
0 , define:
supercluster C ∈ Ci−1
Γ+ (C) = C ∪

[

Γ(u) and deg(C) = |Γ+ (C)|

(4)

u∈C
0
We say that C ∈ Ci−1
has high-expansion if deg(C) ≥ ni/k . Otherwise, it has low-expansion.
The initial pre-clustering C00 = {{v}} consists of n singleton clusters, each spanning a subtree of
diameter 0. For Ci0 , the set Zi is the set of cluster centers of the clusters of Ci0 . As we will see, for every
i, Ci0 consists of O(n1−i/k ) clusters. Each cluster Cj ∈ Ci0 has a center zi ∈ Z and a tree of diameter
24i rooted at the cluster center spanning all the cluster vertices. Hence, our clustering staifies all the
properties (P1-P3) of Baswana-Sen, with the only distinction of having diameter 24i rather than i. As
will be clear later, these clusters are not important not for the purpose of having small stretch, but
rather to create the initial supercluering (hence, the factor 24k appears in our round complexity – the
cost of communicating inside superclusters, but not in the stretch bound). Each phase i ∈ {1, . . . , k/2},
consists of 3 steps as defined next.
0
Step (S1): Selecting the cluster centers Zi ⊆ Zi−1 : Every cluster C ∈ Ci−1
computes its deg(C)
4i
0
0
in O(2 ) rounds. A cluster C with high-expansion, adds its center to Zi−1 . Hence, Zi−1
is the cluster
i/k
centers of all clusters with high-expansion (i.e., deg(C) ≥ n )).
0
Next, we use Lemma B.1 to compute (24i , 24(i−1) ) ruling set Zi ⊆ Zi−1
in G. This can be done in
√
log
n+4i
0
O(2
) rounds using Lemma B.1 with V = Zi−1 . Since all the cluster centers that belong to Zi
have a cluster with high expansion, the number of clusters |Zi | is bounded by n/ni/k = n1−i/k (this is
shown later explicitly in the analysis).

Step (S2): Taking Care of unclustered vertices Vi−1 \ Vi : All the newly unclustered vertices
belong to low-expanded clusters C ∈ Ci0 , i.e., with deg(C) ≤ ni/k . We first consider all edges connecting
C to vertices in V \C. For every such cluster C, we define the bipartite graph B(C) = (C, Γ(C)\C) and
apply Alg. SparserBipartiteSpanner to construct a (2k −1)-spanner H(C) ⊆ B(C). In the analysis part,
we show that this step adds O(n1+1/k ) edges to the spanner, and can be implemented in O(n1/2−1/k )
rounds.
Finally, it remains take care of the edges internal to the low-expanded clusters C. By definition,
√
the low-exapnded C has less than ni/k vertices, and since i ≤ k/2, it has O( n) vertices. Since the
clusters are vertex disjoint, we simply apply the algorithm recursively on the induced graph G(C) of
each such cluster C.
Step (S3): Defining the clustering Ci : Finally, we use the cluster centers Zi to define the new
clusters of Ci0 . This step is done exactly as in Baswana-Sen, only that in our case, the diameter of each
cluster is 24(i−1) . A summary description of phase i is given below.

28

Phase i of Algorithm ConsZeroSuperclustering
(SI): Defining the centers Zi .
0
0
• Let Zi−1
be the cluster centers of all clusters C ∈ Ci−1
with deg(C) ≥ ni/k .
0
0
• For the Zi−1
vertices, compute (24i , 24(i−1) ) ruling set Zi ⊆ Zi−1

(SII): Taking care of unclustered vertices.
0
For every Cj ∈ Ci−1
with deg(Cj ) ≤ ni/k , do the following:
• Taking Care of Edges in Cj × (Γ(Cj ) \ Cj ):
– Apply Alg. SparserBipartiteSpanner on the bipartite graph Bi−1,j = (Cj , (Γ(Cj ) \ Cj )).
– Add the (2k − 1)-spanner Hi−1,j ⊆ Bi−1,j to H.
• Taking Care of Edges in Cj × Cj :
Apply Alg. ImprovedSpanner recursively on the graph G(C).
(SIII): Forming the Ci0 clusters centered at Zi . As in Baswana-Sen only that this time, the
diameter of each cluster is 24(i−1) .
√
0
Termination Phase: After k/2 phases, the (k/2)th clustering Ck/2
contains O( n) vertex-disjoint
clusters, for each cluster C, we have a tree T (C) of diameter O(24k ) that spans all the vertices in
C. We then turn these O(24k )-diameter clusters into superclusters in SC 0 . To do that, we need the
√
O( n) clusters to be balanced with respect to the number of vertices they contain. Hence, we apply
√
√
√
0
the Partitioning Lemma 4.5 to turn to O( n) clusters of Ck/2
into O( n) clusters each with O( n)
√
0
vertices. Specifically, on each C ∈ Ck/2
with at least n vertices, apply the Partitioning Lemma 4.5
√
√
on T (C), w(v) = 1 for every v ∈ C and bound B = n. By that we get O( n) clusters, each with
√
` = O( n) vertices. At that point, each such cluster is now defined as a supercluster in SC 0 with
√
O( n) singelton clusters.
Lemma B.2. For every i ∈ {0, . . . , k/2}, Ci0 contains O(n1−i/k ) clusters.
Proof. The lemma follows from the following two facts:
1. The clusters are disjoint.
2. Each cluster contains at least ni/k vertices.
The first item follows by construction (in step (SIII), when constructing the clusters, we break ties
based on IDs to ensure that every vertex joins at most one cluster).
0
The second item follows by noting that if a center center z joins Zi , its cluster in Ci−1
had degree
i/k
i/k
at least n . Also, no other cluster which joined Zi neighbored any of those n , since the centers
joining Zi form a ruling set of Zi−1 , Hence, these ni/k neighbors will join the cluster centered at z in
0 .
the clustering Ci−1
0 . By
Size Analysis of Step (SII): By Lemma B.2, at step i, we have O(n1−(i−1)/k ) clusters in Ci−1
i/k
definition of the cluster of low-expansion, deg(Ci−1,j ) ≤ n . We then construct a (2k − 1) spanner
Hi−1,j for the bipartite graph Bi−1,j = (Ci−1,j , Γ(Ci−1,j ) \ Ci−1,j ). By Lemma 1.2, E(Hi−1,j ) can be
bounded by:

E(Hi−1,j ) = O(|Ci−1,j |1+2/k + |Γ(Ci−1,j ) \ Ci−1,j |)
= O(k · |Ci−1,j |1+2/k + ni/k ) ≤ O(k · |Ci−1,j | · n1/k + ni/k ).
29

√
Since all clusters are vertex disjoint, |Ci−1,j | ≤ ni/k ≤ n, and there O(n1−(i−1)/k ) clusters, we have
that over all we added O(k · n1+1/k ) edges to the spanner. In fact, a tighter analysis can give only
O(n1+1/k ) edges.
Finally, we claim that the edges added by applying the algorithm recursively on a cluster C can
be bounded by O(k · |C|1+1/k ) as well. This follows since clusters are vertex disjoint, and in addition,
2
each cluster is of size at most ni/k , thus O(n1+i/k ) edges added to the spanner in the ith phase. In
total, we have O(n1+1/k ) edges added to the spanner.
Round Analysis of Step (SII): It is easy to see that each edge in the bipartite graph Bi1 ,j appears
in at most 2 bipartite graphs. Hence, when applying Lemma 1.2 on all of the bipartite graphs in
parallel, the algorithm will experience congestion of at most 2. Then, by Lemma 1.2, it will take at
most O(kn1/2+1/k ) rounds, since each of the bipartite graphs has at most n1/2 vertices on one side (the
side corresponding to the cluster C).
When constructing the spanner recursively, each of the clusters in which we recursively construct
√
a spanner is of size up to n, and can all be done in parallel (since the clusters are disjoint). Hence,
√
the step of the recursion will take a total of T ( n) rounds (where T (n) denotes the number of rounds
used by the algorithm on an n-vertex graph), which is negligible compared to T (n) (even if run k/2
times, one for each phase).
Lemma B.3. Algorithm ConsZeroSuperclustering terminates within O(24k n1/2−1/k ) rounds.
Proof. For Step (SI), we first have each cluster compute its degree. This can be done in O(diam(C))
rounds in a way similar to that of algorithm NaiveSpanner: ever vertex sends a message to all its
neighbors containing its cluster ID, and then each vertex sends one ACK to each neighboring cluster.
The cluster can then upcast the count of number of ACKs it received, which is exactly its degree.
4i 4(i−1) ) ruling set
The next stage of Step (SI) takes the same number
√ of rounds as computing the (2 , 2
0 , which by Lemma B.1 takes O(24i 2O( log n) ) rounds. Summing over all k/2 phases gives
Zi ⊆ Zi−1
√
O(24k 2O( log n) ) rounds. Step (SII) takes O(kn1/2+1/k ) rounds, as shown above. Step (SIII) involves
running BFSs of depth O(22i ) from each of the cluster centers in Zi (as well as breaking ties based
on IDs). This takes a total of O(22i ) rounds. Summing over all k/2 phases gives O(2k ) ≤ O(24k )
rounds.
We are now ready to complete the proof of Lemma 4.7.
Lemma 4.7. By Lemma B.3, the algorithm takes O(24k · n1/2−1/k ) rounds. By the size analysis above,
we also have the total number of edges added to the spanner is O(kn1+1/k ).
Showing that the output 0th -superclustering SC 0 is nice. We first show that Ci0 contains
0
O(n1−i/k ) clusters. This follows since the set Zi ⊆ Zi−1
is a (24i , 24 (i − 1)) ruling-set, where each
z ∈ Zi0 have Ω(ni/k ) vertices in its (24(i−2) + 1)-neighborhood. Since the (24(i−2) + 1)-neighborhoods
of z, z 0 ∈ Zi are disjoint, Zi = O(|Zi−1 |/ni/k ) = O(n1−i/k ).
0
Therefore after k/2 stages, Ck/2
contains O(n1/2 ) clusters. We now show that these clusters can
define the superclusters of SC 0 while satisfying all the nice properties of Desc. 4.3. Each of these
clusters C has a tree T (C) of diameter at most 24k (since in each phase, the radius of the cluster
√
0
increases by a constant factor less than 16). For every cluster Ci ∈ Ck/2
with Ω( n) vertices, we can
use the Partitioning Lemma 4.5 on the tree T (Ci ), weights w(v) = 1 for each v ∈ T (Ci ) and bound
√
B = n. This will partition Ci into a collection Ci1 , . . . , Ci` of new clusters (along with a subtree in
T (C) for each Cij ) such that |Cij | = Θ(n) for every i ≥ 2 and |Ci,1 | = O(n), i.e., there exists at most
√
0
one cluster, Ci1 , with less than n vertices. Since the clusters of Ck/2
are vertex disjoint, applying
√
0
1/2
that to all clusters Ck/2 with at least n
clusters, partitions these clusters into a a total of O( n)
√
new clusters each with O( n) vertices. The partitioning lemma also gives a tree T (Cij ) ⊆ T (Ci ) that
30

0 are vertex disjoint, the trees T (C )
connects the vertices of Cij . Note that since the Ci clusters in Ck/2
ij
of all new clusters Cij are edge-disjoint. More accurately, by (D4) of Lemma 4.5, T (Cij ), T (Cij 0 ) (trees
of new clusters that originate at the same cluster Ci ) are edge-disjoint for j 6= j 0 ; and the trees of
T (Cij ), T (Ci0 j 0 ) for i 6= i0 (trees of new clusters that originate at the different clusters Ci , Ci0 ) are
vertex disjoint, since Ci , Ci0 are vertex disjoint and T (Cij ) ⊆ T (Ci ).
√
√
Finally, each of the O( n) new-clusters Cij = {vij ,1 , . . . , vij ,` } with ` = O( n) vertices becomes a
supercluster SC0,ij = {{vij ,1 }, . . . , {vij ,` }}, i.e., each vertex vij ,p is singelton cluster {vij ,p } of SC0,ij .
All properties of Desc. 4.3 hold.

Showing that all edges of unclustered vertices are handled in H. Consider an edge (u, v)
where either u or v is k/2-unclustered (i.e., not appearing in the clusters of SC 0 ). We will show that
the edge has a stretch of at most (2k − 1) in the partial spanner H. Consider the first phase i in which
either u or v became unclustered. Then in the previous phase (i − 1), both u and v are clustered.
Suppose without loss of generality that u becomes unclustered in phase i. There are two cases:
0 . Since we apply Alg. ImprovedSpanner recursively
Case 1: u and v belong to the same cluster C ∈ Ci−1
in the cluster C (see Step (SII)) and add the output spanner for H, we have dist(u, v, H) ≤ 2k − 1.
0 : In such a case, the center of v’s cluster did not
Case 2: u and v belong to different clusters in Ci−1
join Zi (otherwise u would be clustered). Since we employ Alg. SparserBipartiteSpanner on a bipartite
graph between u’s cluster and its neighbors (which include v), we have dist(u, v, H) ≤ 2k − 1 (see
Step (SII)).
For the case of odd k, we use a similar algorithm and analysis. The only difference is that we
terminate our for loop at (k − 1)/2 instead of k/2, and use the bipartite spanner algorithm for odd k.
This yields the following similar lemma:
Lemma B.4 (0-Superclustering Lemma: Odd k). Let G = (V, E) be a graph and k ≥ 3 be a positive
odd integer. One can construct the nice 0th -level superclustering in O(n1/2−1/(2k) ) rounds.

31

