Deterministic graph connectivity in the broadcast
congested clique
Pedro Montealegre⋆ and Ioan Todinca

arXiv:1602.04095v3 [cs.DC] 9 Jun 2017

Univ. Orléans, INSA Centre Val de Loire, LIFO EA 4022, Orléans , France
(pedro.montealegre | ioan.todinca)@univ-orleans.fr

Abstract. We present deterministic constant-round protocols for the graph connectivity problem in
the model where each of the n nodes of a graph receives a row of the adjacency matrix, and broadcasts
a single sublinear size message to all other nodes. Communication rounds are synchronous. This model
is sometimes called the broadcast congested clique. Specifically, we exhibit a deterministic protocol that
computes the connected components of the input graph in ⌈1/ǫ⌉ rounds, each player communicating
O(nǫ · log n) bits per round, with 0 < ǫ ≤ 1.
We also provide a deterministic one-round protocol for connectivity, in the model when each node
receives as input the graph induced by the nodes at distance at most r > 0, and communicates
O(n1/r ·log n) bits. This result is based on a d-pruning protocol, which consists in successively removing
nodes of degree at most d until obtaining a graph with minimum degree larger than d. Our technical
novelty is the introduction of deterministic sparse linear sketches: a linear compression function that
permits to recover sparse Boolean vectors deterministically.

Keywords: broadcast congested clique; graph connectivity; spanning forest; deterministic
protocol

1

Introduction

This paper proposes the first (to our knowledge) constant-round deterministic protocol that
computes a spanning forest1 in the broadcast congested clique model with sub-linear message
size.
The congested clique model is a message-passing model of distributed computation where
n nodes communicate with each other in synchronous rounds over a complete network [1,2,4,5].
The joint input of the n nodes is an undirected graph G on the same set of nodes, with node
v receiving the list of its neighbors in G. Nodes have pairwise distinct identities, which are
numbers upper bounded by some polynomial in n. Moreover, all nodes know this upper
bound. At the end of a protocol, each node must produce the same output. In the broadcast
congested clique (denoted BClique[f (n)]) each node broadcasts, in each round, a single
O(f (n))-sized message2 along each of its n − 1 communication links, while in the unicast
congested clique (denoted UClique[f (n)]) nodes are allowed to send different O(f (n))-size
messages through different links.
There exists a basic O(log n)-round connectivity protocol in the BClique[log n] model.
Each node successively sends a neighbor outside its current cluster (initially the clusters
consist in single nodes), and at each round the adjacent clusters are merged. The protocol
⋆
1
2

Research supported by Conicyt-Becas Chile-72130083.
In this paper a spanning forest designs a maximal one.
Some authors consider that in the congested clique model only O(log n)-size messages are allowed. In our case the
congestion refers to sublinear capacity communication channels.

can be adapted to compute a maximum weight spanning forest. Despite its simplicity, only
few results exist improving the basic connectivity protocol.
On one hand, Lotker et al. [8] proposed the first improvement in the unicast congested
clique, namely a O(log log n)-round protocol for maximum weight spanning forest in the
UClique[log n] model, which also runs in O(1/ǫ) rounds in UClique[nǫ ], for any constant
ǫ > 0. Later, Hegeman et al. [6] improved the number of rounds to O(log log log n), also in
UClique[log n], but in a randomized protocol, which outputs a maximum weight spanning
forest with high probability. On the other hand, in the broadcast congested clique, a oneround randomized protocol for graph connectivity in BClique[log3 n] was proposed by Ahn
et al. [1], using an elegant techinque called linear sketches.
Our results. First, we observe that the basic connectivity protocol can be used to produce, for each 0 < ǫ ≤ 1 a O(1/ǫ)-round protocol that computes a spanning forest in the
BClique[nǫ · log n] model.
We also propose a one-round connectivity protocol, this time the BCliquer [n1/r log n]
model. This corresponds to the broadcast congested clique model, when each node receives
as input the graph induced by the nodes at distance at most r (one may think of this model
as the one where vertices are allowed to perform r unrestricted local communications, and
then some congested global communications).
Our main tool is a protocol to prune a graph. The d-pruning of graph G, for d > 0, consists
of finding a sequence of nodes (x1 , . . . , xp ), together with their incident edges, such that each
vertex xi has degree at most d in the graph obtained by removing vertices {x1 , . . . , xi−1 }
from G, and the graph obtained by removing the whole sequence has minimum degree strictly
larger than d.
Becker et al. [4] provide a one-round deterministic protocol for d-pruning a graph in
BClique[d2 · log n]. They actually work on the reconstruction of d-degenerate graphs, i.e.,
graphs for which the pruning sequence is the whole vertex set.
We give a new protocol for d-pruning, which also runs in one round, but improves the
message size to O(d · log n). Our protocol is optimal since the number of d-degenerate graphs
is 2Ω(nd log n) . This new protocol is inspired by the fingerprint technique, which uses the
Schwartz-Zippel Lemma for equality testing in randomized communication complexity [7].
The protocol is based on a derandomized version of fingerprints to compute sparse linear
sketches: a linear compression function that permits to recover d-sparse Boolean vectors
deterministically. This technique has its own interest and we believe that can be used in
other applications.

2

Pruning and connectivity

Theorem 1. Let 0 < ǫ ≤ 1. There is a ⌈1/ǫ⌉-round deterministic protocol that computes
the connected components of the input graph in the BClique[nǫ · log n] model. The protocol
returns a spanning forest of the input graph.
Proof sketch. Let G = (V, E) the input graph. The protocol is very similar to the basic
connectivity protocol described in the introduction. First, denote V̂ the set of supernodes,
which initially are the n singletons {{u}|u ∈ V }. At each round, every node sends nǫ arbitrary

neighbors in pairwise different supernodes (if it sees less than nǫ supernodes, then it sends
one neighbor for each of them). At the end of each round adjacent supernodes are merged.
A supernode of round t > 1 is called active if it contains at least nǫ supernodes of round
t − 1, and otherwise is called inactive. Note that at any round t > 0, an inactive supernode
corresponds to a connected component of G. The protocol finishes when every supernode is
inactive. Let nt be the number of active supernodes at round t ≥ 0. Since the number of
active nodes at round t + 1 at most nt /nǫ , the protocol stops in at most ⌈1/ǫ⌉ rounds.
⊔
⊓
We remark that when ǫ ≤ 1/(log n) our protocol matches de basic one. When ǫ = 1/2,
we obtain a sublinear, two-round protocol for connectivity. To our knowledge, there are no
nontrivial lower bounds for deterministic protocols solving graph connectivity in the broadcast congested clique, even restricted to one-round protocols. However, even in the powerful
unicast congested clique, there are no known sublinear one-round deterministic protocols. In
the following, we propose a one-round deterministic protocol for graph connectivity in the
BCliquer model.
Theorem 2. There exists a deterministic protocol in the BClique[d · log n] model that
computes a d-pruning in one round.
Let d > 0. We say that a vector is d-sparse if it has at most d nonzero coordinates. We
show that there exists a linear function compressing integer vectors, and such that if the
compressed vector is Boolean and d-sparse, the vector can be recovered. We emphasize that
the recovery property does not work over all d-sparse integer vectors, but only on Boolean
ones. In the following Fp denotes the field of integers modulo p, where p > 0 is prime.
Lemma 1. Let n, d > 0. There exists a function f : Zn → Fp , for some prime number
p = 2O(d·log n) , such that: (1) f is linear, and (2) f is injective when restricted to d-sparse
Boolean inputs.
P
Proof sketch. Let B = {b ∈ {0, 1}n : ni=1 bi ≤ d} be the family of d-sparse Boolean vectors
of dimension n, and T = {t ∈ {−1, 0, 1}n : ∃ distinct b, b′ ∈ B, t = b − b′ }. Call p = p(n, d)
the smallest prime number greater than (1 + n)2d · n. Let P (T ) be the family
Pn of polynomials
over the field Fp associating to each t ∈ T the polynomial P (t, X) = i=1 ti X i−1 (values
are taken modulo p). Let x = x(n, d) be the minimum integer in Fp which is not a root of
any polynomial in P (T ); x exists because there are at most |T | polynomials in P (T ), each
polynomial has at most n roots in Fp , and p > |T | · n. We define then for each v ∈ Zn the
function f (v) = P (v, x). Clearly f is linear, and by definition of x, for any distinct b, b′ ∈ B,
we have f (b) = P (b, x) 6= P (b′ , x) = f (b′ ).
⊔
⊓
Proof sketch of Theorem 2. In the d-pruning protocol, each player i sends the message
Mi = (Mi1 , Mi2 ) = (di , f (ai )), where di is its degree, ai is the row of the adjacency matrix
corresponding to node i, and f is the function of Lemma 1. The number of communicated
bits is O(d log n). Call M(G) = (M1 , . . . , Mn ) the messages vector of G. The nodes use M(G)
to prune the graph as follows. First they look for a node k such that Mk1 ≤ d. Using the injectivity property of f they can obtain the neighborhood of k in G. Then, using the linearity
of f they compute the messages vector of G − {k} updating Mj = (Mj1 − 1, Mj2 − f (ek ))
for each j neighbor of k, where ek is the Boolean vector having a unique one in the k-th

coordinate. The process is reiterated (with no extra communication) until there is no more
node of degree at most d.
⊔
⊓
We use our d-pruning protocol to produce a one-round connectivity protocol, this time
in the BCliquer [n1/r · log n] model. Our protocol is based in the following propositions
respectively found in [3], and [5]. Let G = (V, E) be a graph, r > 0, and σ some total
ordering of E. For each cycle of length at most 2r pick the maximum edge of the cycle
according to σ. Call Ẽ the set of picked edges, and call G̃ = (V, E − Ẽ). Note that G̃ has no
cycles of length at most 2r.
Proposition 1 ([3]). G is connected if and only if G̃ is connected, and any spanning forest
of G̃ is a spanning forest of G.
The following proposition shows that G̃ has sublinear degeneracy. Recall that the girth
of a graph is the length of a shortest cycle.
Proposition 2 ([5]). Let G be a graph of girth at least 2r. Then G is O(n1/r )-degenerate.
Theorem 3. There is a one-round deterministic protocol that computes the connected components of the input graph in the BCliquer [n1/r · log n] model. The protocol returns a spanning forest of the input graph.
Proof. Choose an ordering of the edges of G, for example if we denote the edges e = (u, v)
with u < v, then (u1 , v1 ) < (u2 , v2 ) if either u1 < u2 or u1 = u2 and v1 < v2 .
In the protocol, a node v looks for all cycles of length at most 2r in G that contain
it. Notice that nodes do this without any communication since they see all neighbors at
distance at most r. For each such cycle, v picks the maximum edge according to the edge
ordering, obtaining the row of the adjacency matrix of G̃ corresponding to v. Then each
node can simulate the s-pruning protocol when the input graph is G̃, where s = O(n1/r ) is
the degeneracy of graphs of girth at least 2r, obtained from Proposition 2. Each node then
reconstructs G̃ and computes a spanning forest of G̃.

3

Discussion

We have shown that, in the BClique[nǫ · log n] model, O(1/ǫ) rounds are enough to decide
connectivity deterministically. If nodes see the graph induced by the nodes at distance at most
r, then connectivity can be decided by a deterministic one-round protocol, with messages of
size O(n1/r · log n).
These results rely on a deterministic protocol for d-pruning, which in particular reconstructs d-degenerate graphs. We believe that this protocol, and the sketch function it is based
on, might be of interest for further applications.
Like Ahn et al.’s results [1], our connectivity protocol can be transformed into protocols to
detect if the input graph is bipartite. Moreover, the d-pruning protocol can be implemented
as a O(nd log n)-space protocol in the dynamic graph streaming model.
To wrap up, let us recall that the existence of a one-round deterministic protocol for
connectivity, in the broadcast congested clique with sublinear message size, is still open. We
might as well ask whether the problem could be solved by randomized protocols using only
private coins.

4

Acknowledgments

We thank F. Becker and I. Rapaport for fruitful discussions on the subject, and the anonymous referees for useful suggestions. P. Montealegre would like to thank the support of
Conicyt Becas Chile-72130083.

References
1. K. J. Ahn, S. Guha, and A. McGregor. Analyzing graph structure via linear measurements. In Proc. of the 23rd
Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, pages 459–467, 2012.
2. K. J. Ahn, S. Guha, and A. McGregor. Graph sketches: Sparsification, spanners, and subgraphs. In Proc. of the
31st Symposium on Principles of Database Systems, PODS ’12, pages 5–14, 2012.
3. B. Awerbuch, O. Goldreich, R. Vainish, and D. Peleg. A trade-off between information and communication in
broadcast protocols. J. ACM, 37(2):238–256, Apr. 1990.
4. F. Becker, A. Kosowski, M. Matamala, N. Nisse, I. Rapaport, K. Suchan, and I. Todinca. Allowing each node to
communicate only once in a distributed system: shared whiteboard models. Distributed Computing, 28(3):189–200,
2015.
5. A. Drucker, F. Kuhn, and R. Oshman. The communication complexity of distributed task allocation. In Proc. of
the 2012 ACM Symposium on Principles of Distributed Computing, PODC ’12, pages 67–76, 2012.
6. J. W. Hegeman, G. Pandurangan, S. V. Pemmaraju, V. B. Sardeshmukh, and M. Scquizzato. Toward optimal
bounds in the congested clique: Graph connectivity and mst. In Proceedings of the 2015 ACM Symposium on
Principles of Distributed Computing, PODC ’15, pages 91–100, New York, USA, 2015. ACM.
7. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, New York, USA, 1997.
8. Z. Lotker, B. Patt-Shamir, E. Pavlov, and D. Peleg. Minimum-weight spanning tree construction in O(log log n)
communication rounds. SIAM Journal on Computing, 35(1):120–131, 2005.

