Distributed Testing of Excluded Subgraphs
Pierre Fraigniaud∗1 , Ivan Rapaport†2 , Ville Salo‡2 , and Ioan Todinca3
1

arXiv:1605.03719v1 [cs.DC] 12 May 2016

2

CNRS and University Paris Diderot, France
DIM-CMM (UMI 2807 CNRS), Universidad de Chile, Chile
3
Université d’Orléans, France

Abstract
We study property testing in the context of distributed computing, under the classical
CONGEST model. It is known that testing whether a graph is triangle-free can be done in a
constant number of rounds, where the constant depends on how far the input graph is from
being triangle-free. We show that, for every connected 4-node graph H, testing whether a
graph is H-free can be done in a constant number of rounds too. The constant also depends
on how far the input graph is from being H-free, and the dependence is identical to the one
in the case of testing triangles. Hence, in particular, testing whether a graph is K4 -free, and
testing whether a graph is C4 -free can be done in a constant number of rounds (where Kk
denotes the k-node clique, and Ck denotes the k-node cycle). On the other hand, we show
that testing Kk -freeness and Ck -freeness for k ≥ 5 appear to be much harder. Specifically, we
investigate two natural types of generic algorithms for testing H-freeness, called DFS tester
and BFS tester. The latter captures the previously known algorithm to test the presence of
triangles, while the former captures our generic algorithm to test the presence of a 4-node
graph pattern H. We prove that both DFS and BFS testers fail to test Kk -freeness and
Ck -freeness in a constant number of rounds for k ≥ 5.
Keywords: property testing, decision and verification algorithms, CONGEST model.

∗

Additional support from ANR project DISPLEXITY, and Inria project GANG.
Additional support from CONICYT via Basal in Applied Mathematics, Núcleo Milenio Información y Coordinación en Redes ICM/FIC RC130003, Fondecyt 1130061.
‡
Additional support from FONDECYT project 3150552.
†

1

Introduction

Let P be a graph property, and let 0 < ǫ < 1 be a fixed parameter. According to the usual
definition from property testing [17], an n-node m-edge graph G is ǫ-far from satisfying P if
applying a sequence of at most ǫm edge-deletions or edge-additions to G cannot result in a
graph satisfying P. In the context of property testing, graphs are usually assumed to be stored
using an adjacency list, and a centralized algorithm has the ability to probe nodes, via queries
of the form (i, j) where i ∈ {1, . . . , n}, and j ≥ 0. The answer to a query (i, 0) is the degree
of node i, while the answer to a query (i, j) with j > 0 is the identity of the jth neighbor of
node i. After a small number of queries, the algorithm must output either accept or reject. An
algorithm Seq is a testing algorithm for P if and only if, for every input graph G,

G satisfies P =⇒ Pr[Seq accepts G] ≥ 32 ;
G is ǫ-far from satisfying P =⇒ Pr[Seq rejects G] ≥ 32 .
(An algorithm is 1-sided if it systematically accepts every graph satisfying P). The challenge
in this context is to design testing algorithms performing as few queries as possible.
In the context of distributed property testing [7], the challenge is not the number of queries
(as all nodes perform their own queries in parallel), but the lack of global perspective on the
input graph. The graph models a network. Every node of the network is a processor, and every
processor can exchange messages with all processors corresponding to its neighboring nodes in
the graph. After a certain number of rounds of computation, every node must output accept
or reject. A distributed algorithm Dist is a distributed testing algorithm for P if and only if,
for any graph G modeling the actual network,

G satisfies P =⇒ Pr[Dist accepts G in all nodes] ≥ 23 ;
G is ǫ-far from satisfying P =⇒ Pr[Dist rejects G in at least one node] ≥ 23 .
The challenge is to use as few resources of the network as possible. In particular, it is desirable that every processor could take its decision (accept or reject) without requiring data from
far away processors in the network, and that processors exchange messages of size respecting
the inherent bounds imposed by the limited bandwidth of the links. These two constraints
are well captured by the CONGEST model. This model is a classical model for distributed
computation [28]. Processors are given distinct identities, that are supposed to have values in
[1, nc ] in n-node networks, for some constant c ≥ 1. All processors start at the same time,
and then proceed in synchronous rounds. At each round, every processor can send and receive
messages to/from its neighbors, and perform some individual computation. All messages must
be of size at most O(log n) bits. So, in particular, every message can include at most a constant
number of processor identities. As a consequence, while every node can gather the identities of
all its neighbors in just one round, a node with large degree that is aware of all the identities
of its neighbors may not be able to send them all simultaneously to a given neighbor. The latter observation enforces strong constraints on distributed testing algorithms in the CONGEST
model. For instance, while the LOCAL model allows every node to gather its t-neighborhood
in t rounds, even just gathering the 2-neighborhood may require Ω(n) rounds in the CONGEST
model (e.g., in the Lollipop graph). As a consequence, detecting the presence of even a small
given pattern in a graph efficiently is not necessarily an easy task.
The presence or absence of a certain given pattern (typically, paths, cycles or cliques of
a given size) as a subgraph, induced subgraph, or minor, has a significant impact on graph
properties, and/or on the ability to design efficient algorithms for hard problems. This paper
investigates the existence of efficient distributed testing algorithms for the H-freeness property,
depending on the given graph H. Recall that, given a graph H, a graph G is H-free if and only
1

if H is not isomorphic to a subgraph of G, where H is a subgraph of a graph G if V (H) ⊆ V (G),
and E(H) ⊆ E(G). Recently, Censor-Hillel et al. [7] established a series of results regarding
distributed testing of different graph properties, including bipartiteness and triangle-freeness.
A triangle-free graph is a K3 -free graph or, equivalently, a C3 -free graph, where Kk and Ck
respectively denote the clique and the cycle on k vertices. The algorithm in [7] for testing
bipartiteness (of bounded degree networks) requires O(log n) rounds in the CONGEST model,
and the authors conjecture that this is optimal. However, quite interestingly, the algorithm for
testing triangle-freeness requires only a constant number of rounds, O(1/ǫ2 ), i.e., it depends
only on the (fixed) parameter ǫ quantifying the ǫ-far relaxation.
In this paper, we investigate the following question: what are the (connected) graphs H for
which testing H-freeness can be done in a constant number of rounds in the CONGEST model?

1.1

Our results

We show that, for every connected 4-node graph H, testing whether a graph is H-free can be
done in O(1/ǫ2 ) rounds. Hence, in particular, testing whether a graph is K4 -free, and testing
whether a graph is C4 -free can be done in a constant number of rounds. Our algorithm is
generic in the sense that, for all 4-node graphs H, the global communication structure of the
algorithm is the same, with only a variant in the final decision for accepting or rejecting, which
of course depends on H.
In fact, we identify two different natural generic types of testing algorithms for H-freeness.
We call the first type DFS tester, and our algorithm for testing the presence of 4-node patterns
is actually the DFS tester. Such an algorithm applies to Hamiltonian graphs H, i.e., graphs
H containing a simple path spanning all its vertices. It performs in |H| − 1 rounds. Recall
that, for a node set A, G[A] denotes the subgraph of G induced by A. At each round t of the
DFS tester, at every node u, and for each of its incident edges e, node u pushes a graph G[At ]
(where, initially, A0 is just the graph formed by u alone). The graph G[At ] is chosen u.a.r.
among the sets of graphs received from the neighbors at the previous round. More specifically,
upon reception of every graph G[At−1 ] at round t − 1, node u forms a graph G[At−1 ∪ {u}], and
the graph G[At ] pushed by u along e at round t is chosen u.a.r. among the collection of graphs
G[At−1 ∪ {u}] currently held by u.
We call BFS tester the second type of generic testing algorithm for H-freeness. The algorithm in [7] for triangle-freeness is a simplified variant of the BFS tester, and we prove that
the BFS tester can test K4 -freeness in O(1/ǫ2 ) rounds. Instead of guessing a path spanning H
(which may actually not exist for H large), the BFS tester aims at directly guessing all neighbors in H simultaneously. The algorithm performs in D − 1 rounds, where D is the diameter
of H. For the sake of simplicity, let us assume that H is d-regular. At each round, every node
u forms groups of d neighboring nodes. These groups may overlap, but a neighbor should not
participate to more than a constant number of groups. Then for every edge e = {u, v} incident
to u, node u pushes all partial graphs of the form G[At−1 ∪ {v1 , . . . , vt }] where v ∈ {v1 , . . . , vt },
At−1 is chosen u.a.r. among the graphs received at the previous round, and the vi ’s will be in
charge of checking the presence of edges between them and the other vj ’s.
We prove that neither the DFS tester, nor the BFS tester can test Kk -freeness in a constant
number of rounds for k ≥ 5, and that the same holds for testing Ck -freeness (with the exception
of a finite number of small values of k). This shows that testing Kk -freeness or Ck -freeness for
k ≥ 5 in a constant number of rounds requires, if at all possible, to design algorithms which
explore G from each node in a way far more intricate than just parallel DFSs or parallel BFSs.
Our impossibility results, although restricted to DFS and BFS testers, might be hints that
testing Kk -freeness and Ck -freeness for k ≥ 5 in n-node networks does require to perform a

2

number of rounds which grows with the size n of the network.

1.2

Related work

The CONGEST model has become a standard model in distributed computation [28]. Most of
the lower bounds in the CONGEST model have been obtained using reduction to communication
complexity problems [12, 24, 9]. The so-called congested clique model is the CONGEST model in
the complete graph Kn [11, 23, 25, 27]. There are extremely fast protocols for solving different
types of graph problems in the congested clique, including finding ruling sets [21], constructing
minimum spanning trees [20], and, closely related to our work, detecting small subgraphs [8, 10].
The distributed property testing framework in the CONGEST model was recently introduced
in the aforementioned paper [7], inspired from classical property testing [17, 18]. Distributed
property testing relaxes classical distributed decision [13, 14, 19], typically designed for the
LOCAL model, by ignoring illegal instances which are less than ǫ-far from satisfying the considered property. Without such a relaxation, distributed decision in the CONGEST model requires
non-constant number of rounds [9]. Other variants of local decision in the LOCAL model have
been studied in [2, 3], where each process can output an arbitrary value (beyond just a single bit
— accept or reject), and [4, 22], where nodes are bounded to perform a single round before to
output at most O(log n) bits. Distributed decision has been also considered in other distributed
environments, such as shared memory [15], with application to runtime verification [16], and
networks of finite automata [29].

2

Detecting Small Graphs Using a DFS Approach

In this section, we establish our main positive result, which implies, in particular, that testing
C4 -freeness and testing K4 -freeness can be done in constant time in the CONGEST model.
Theorem 1 Let H be a graph on four vertices, containing a P4 (a path on four vertices)
as a subgraph. There is a 1-sided error distributed property-testing algorithm for H-freeness,
performing in a constant number of rounds in the CONGEST model.
Proof. We show the theorem by exhibiting a generic distributed testing protocol for testing
H-freeness, that applies to any graph H on four vertices containing a P4 as a subgraph. The
core of this algorithm is presented as Algorithm 1. Note that the test H ⊆ G[u, u′ , v ′ , w′ ] at
step 4 of Algorithm 1 can be performed thanks to the bit b that tells about the only edge that
node u is not directly aware of. Algorithm 1 performs in just two rounds (if we omit the round
used to acquire the identities of the neighbors), and that a single O(log n)-bit message is sent
through every edge at each round. Clearly, if G is H-free, then all nodes accept.
Algorithm 1: Testing H-freeness for 4-node Hamiltonian H. Instructions for node u.
1
2
3

4
5

Send id(u) to all neighbors;
For every neighbor v, choose a received identity id(w) u.a.r., and send (id(w), id(u)) to v;
For every neighbor v, choose a received pair (id(w′ ), id(u′ )) u.a.r., and send
(id(w′ ), id(u′ ), id(u), b) to v, where b = 1 if w′ is a neighbor of u, and b = 0 otherwise;
For every received 4-tuple (id(w′ ), id(v ′ ), id(u′ ), b), check whether H ⊆ G[u, u′ , v ′ , w′ ];
If H ⊆ G[u, u′ , v ′ , w′ ] for one such 4-tuple then reject else accept.

In order to analyze the efficiency of Algorithm 1 in case G is ǫ-far from being H-free,
let us consider a subgraph G[{u1 , u2 , u3 , u4 }] of G containing H, such that (u1 , u2 , u3 , u4 ) is
3

a P4 spanning H. Let E be the event “at step 2, vertex u2 sends (id(u1 ), id(u2 )) to its
neighbor u3 ”. We have Pr[E] = 1/d(u2 ). Similarly, let E ′ be the event “at step 3, vertex u3 sends (id(u1 ), id(u2 ), id(u3 )) to its neighbor u4 ”. We have Pr[E ′ |E] = 1/d(u3 ). Since
Pr[E ∧ E ′ ] = Pr[E ′ |E] · Pr[E], it follows that
Pr[H is detected by u4 while performing Algorithm 1] ≥

1
.
d(u2 )d(u3 )

(1)

Note that the events E and E ′ only depend on the choices made by u2 for the edge {u2 , u3 } and
by u3 for the edge {u3 , u4 }, in steps 3 and 4 of Algorithm 1, respectively. Since these choices
are performed independently at all nodes, it follows that if H1 and H2 are edge-disjoint copies
of H in G, then the events E1 and E2 associated to them are independent, as well as the events
E ′ 1 and E ′ 2
The following result will be used throughout the paper, so we state it as a lemma for further
references.
Lemma 1 Let G be ǫ-far from being H-free. Then G contains at least ǫm/|E(H)| edge-disjoint
copies of H.
To establish Lemma 1, let S = {e1 , . . . , ek } be a smallest set of edges whose removal from G
results in an H-free graph. We have k ≥ ǫm. Let us then remove these edges from G according
to the following process. The edges are removed in arbitrary order. Each time an edge e is
removed from S, we select an arbitrary copy He of H containing e, we remove all the edges of
He from G, and we reset S as S \ E(He ). We proceed as such until we have exhausted all the
edges of S. Note that each time we pick an edge e ∈ S, there always exists a copy He of H
containing e. Indeed, otherwise, S \ {e} would also be a set whose removal from G results in
an H-free graph, contradicting the minimality of |S|. After at most k such removals, we get
a graph that is H-free, and, by construction, for every two edges e, e′ ∈ S, we have that He
and He′ are edge-disjoint. Every step of this process removes at most |E(H)| edges from S,
hence the process performs at least ǫm/|E(H)| steps before exhausting all edges in S. Lemma 1
follows.
Let us now define an edge {u, v} as important if it is the middle-edge of a P4 in one of the
ǫm/|E(H)| edge-disjoint copies of H constructed in the proof of Lemma 1. We denote by I(G)
the set of all important edges. Let N0 be the random variable counting the number of distinct
copies of H that are detected by Algorithm 1. As a direct consequence of Eq (1), we get that
X
1
.
E(N0 ) ≥
d(u)d(v)
{u,v}∈I(G)

Define an edge {u, v} of G as good if d(u)d(v) ≤ 4m|E(H)|/ǫ, and let g(G) denote the set of
good edges. Note that if there exists a constant γ > 0 such that |I(G) ∩ g(G)| ≥ γm, then the
expected number of copies of H detected during a phase is
X
1
γǫ
1
≥ γm
=
.
(2)
E(N0 ) ≥
d(u)d(v)
4m|E(H)|/ǫ
4|E(H)|
{u,v}∈I(G)∩g(G)

We now show that the number of edges that are both important and good is indeed at least a
3
fraction γ of the egdes, for some constant γ > 0. We first show that G has at least (1− 4|E(H)|
ǫ)m
P
good edges. Recall that u∈V (G) d(u) = 2m, and define N (u) as the set of all neighbors of
node u. We have
X
X
X
1 X
d(u)
d(v) ≤
d(u) m ≤ 2m2 .
d(u)d(v) =
2
{u,v}∈E(G)

u∈V (G)

v∈N (u)

4

u∈V (G)

Thus G must have at least (1 −
X

d(u)d(v) ≥

{u,v}∈E(G)

3
4|E(H)| ǫ)m

X

good edges, since otherwise
d(u)d(v) >

{u,v}∈E(G)\g(G)

3
4m|E(H)|
ǫm
= 3m2 ,
4|E(H)|
ǫ

3
contradicting the aforementioned 2m2 upper bound. Thus, G has at least (1 − 4|E(H)|
ǫ)m good
edges. On the other hand, since the number of important edges is at least the number of edgedisjoint copies of H in G, there are at least ǫm/|E(H)| important edges. It follows that the
ǫ
m. Therefore, by Eq. (2),
number of edges that are both important and good is at least 4|E(H)|
we get that

2
ǫ
E(N0 ) ≥
.
4|E(H)|

All the above calculations were made on the ǫm/|E(H)| edge-disjoint copies of H constructed
(0)
(0)
in the proof of Lemma 1. Therefore, if Xi denotes the random variable satisfying Xi = 1 if
P
(0)
ǫm/|E(H)|
(0)
the ith copy H is detected, and Xi = 0 otherwise, then we have N0 = i=1
Xi , and
(0)
the variables Xi , i = 1, . . . , ǫm/|E(H)|, are mutually independent. Let
T = 8 ln 3



4|E(H)|
ǫ

2

.

P −1
By repeating the algorithm T times, and defining N = Tt=0
Nt where Nt denotes the number
of copies of H detected at the tth independent repetition, we get
E(N ) ≥ 8 ln 3.
P −1 Pǫm/|E(H)| (t)
(t)
In fact, we also have N = Tt=0
Xi where Xi = 1 if the ith copy H is detected
i=1
(t)
at the tth iteration of the algorithm, and Xi = 0 otherwise. All these variables are mutually
independent, as there is mutual independence within each iteration, and all iterations are performed independently. Therefore, Chernoff bound applies (see Theorem 4.5 in [26]), and so, for
every 0 < δ < 1, we have
2
Pr[N ≤ (1 − δ)E[N ]] ≤ e−δ E[N ]/2 .
By taking δ =

1
2

we get
Pr[N ≤ 4 ln 3] ≤

1
.
3

Therefore, a copy of H is detected with probability at least 23 , as desired, which completes the
proof of Theorem 1.

Remark. Theorem 1 requires the existence of a P4 in the graph H. All connected graphs H
of four vertices satisfy this condition, with the only exception of the star K1,3 (a.k.a. the claw ).
Nevertheless, detecting whether a graph G has a star K1,3 as a subgraph is trivial (every node
rejects whenever its degree at least three).

3

Limits of the DFS Approach

Algorithm 1 can be extended in a natural way to any k-node graph H containing a Hamiltonian
path, as follows. Given a graph G = (V, E), and A ⊆ V , let G[A] = (A, EA ) denote the subgraph
of G induced by A (i.e., for every two nodes u and v in A, {u, v} ∈ EA ⇐⇒ {u, v} ∈ E).
5

The extension of Algorithm 1 to Hamiltonian graphs H is depicted in Algorithm 2. At the first
round, every vertex u sends its identifier to its neighbors, and composes the d(u) graphs formed
by the edge {u, v}, one for every neighbor v. Then, during the k − 2 following rounds, every
node u forwards through each of its edges one of the graphs formed a the previous round.
Algorithm 2: Testing H-freeness: Hamiltonian H, |V (H)| = k. Instructions for node u.

8

send the 1-node graph G[u] to every neighbor v;
form the graph G[{u, v}] for every neighbor v;
repeat k − 2 times
for every neighbor v do
choose a graph G[A] u.a.r. among those formed during the previous round;
send G[A] to v;
receive the graph G[A′ ] from v;
form the graph G[A′ ∪ {u}];

9

if H ⊆ G[A] for one of the graphs formed at the last round then reject else accept.

1
2
3
4
5
6
7

Let (u1 , u2 , . . . , uk ) be a simple path in G, and assume that G[{u1 , u2 , . . . , uk }] contains H.
If, at each round i, 2 ≤ i < k, vertex ui sends to ui+1 the graph G[{u1 , . . . , ui }], then, when the
repeat-loop completes, vertex uk will test precisely the graph G[{u1 , u2 , . . . , uk }], and thus H
will be detected by the algorithm.
Theorem 1 states that Algorithm 2 works fine for 4-node graphs H. We show that, k = 4 is
precisely the limit of detection for graphs that are ǫ-far from being H-free, even for the cliques
and the cycles.
Theorem 2 Let H = Kk for arbitrary k ≥ 5, or H = Ck for arbitrary odd k ≥ 5. There
exists a graph G that is ǫ-far from being H-free in which any constant number of repetitions of
Algorithm 2 fails to detect H, with probability at least 1 − o(1).
For the purpose of proving Theorem 2, we use the following combinatorial result, which
extends Lemma 7 of [1], where the corresponding claim was proved for k = 3, with a similar
proof. The bound on p′ is not even nearly optimal in Lemma 2 below, but it is good enough
for our purpose1 .
Lemma 2 Let k be a constant. For any sufficiently large p, there exists a set X ⊂ {0, . . . , p−1}
of size p′ ≥ p

log log p+4
1− log log
log p

k−1
X

such that, for any k elements x1 , x2 , . . . , xk of X,

xi ≡ (k − 1)xk

(mod p)

=⇒

x1 = · · · = xk−1 = xk .

i=1

k
j
Proof. Let b = ⌊log p⌋ and a = logloglogp p . Take p sufficiently large so that a < b/k is satisfied.
X is a set of integers encoded in base b, on a b-ary digits, such that the digits of each x ∈ X are
a permutation
Pa−1 of i{0, 1, . . . , a − 1}. More formally, for any permutation π over {0, . . . , a − 1}, let
Nπ = i=0 π(i)b . Then, let us set X = {Nπ | π is a permutation of {0, . . . , a − 1}}. Observe
that different permutations π and π ′ yield different numbers Nπ and Nπ′ because these numbers
have different digits in base b. Hence X has p′ = a! elements. Using the inequality z! > (z/e)z
as in [1] (Lemma 7), we get that a! ≥ p1−

log log log p+4
log log p

1

, as desired.

The interested reader can consult
[30] for the state-of-the-art on such combinatorial constructions, in partic√
′
1−c/ log p
, for a constant c depending on k.
ular constructions for p ≥ p

6

log p

Now, for any x ∈ X, we have x ≤ p/k. Indeed, x < a·ba−1 ≤ k1 ba , and ba ≤ (log p) log log p = p.
Consequently, the modulo in the statement of the Lemma becomes
Pk−1 irrelevant, and we will simply
consider integer sums. Let x1 , . . . , xk−1 , xk in X, such that l=1 xi = (k − 1)xk . Viewing the
xi ’s as integers in base b, and having in mind that all digits are smaller than b/k, we get that
the equality must hold coordinate-wise. For every 1 ≤ l ≤ k, let πl be the permutation such
that xl = Nπl . For every i ∈ 0, . . . , a − 1, we have
k−1
X

πl (i) = (k − 1)πk (i).

l=1

By the Cauchy-Schwarz inequality applied to vectors (π1 (i), . . . , πk−1 (i)) and (1, . . . , 1), for
every i ∈ {0, . . . , a − 1}, we also have
k−1
X

(πl (i))2 ≥ (k − 1) (πk (i))2 .

l=1

Moreover equality holds if and only if π1 (i) = · · · = πk−1 (i) = πk (i). By summing up
P the 2a
inequalities induced by the a coordinates, observe that both sides sum to exactly (k−1) a−1
i=0 i .
Therefore, for every i, the Cauchy-Schwarz inequality is actually an equality, implying that the
ith digit is identical in all the k integers x1 , . . . , xk . As a consequence, x1 = · · · = xk−1 = xk ,
which completes the proof.

Proof of Theorem 2. Assume that G[{u1 , u2 , . . . , uk }] contains H, where (u1 , u2 , . . . , uk ) is
a path of G. For 2 ≤ i ≤ k − 1, let us consider the event “at round i, vertex ui sends the
graph G[u1 , . . . , ui }] to ui+1 ”. Observe that this event happens with probability d(u1 i ) because
ui choses which subgraph to send uniformly at random among the d(ui ) constructed subgraphs.
With the same arguments as the ones used to establish Eq. (1), we get
Pr[H is detected along the path (u1 , . . . , uk )] =

1
.
d(u2 )d(u3 ) . . . d(uk−1 )

(3)

We construct families of graphs which will allow us to show, based on that latter equality, that
the probability to detect a copy of H vanishes with the size of the input graph G. We actually
use a variant of the so-called Behrend graphs (see, e.g., [1, 5]), and we construct graph families
indexed by k, and by a parameter p, that we denote by BC(k, p) for the case of cycles, and by
BK(k, p) for the case of cliques. We prove that these graphs are ǫ-far from being H-free, while
the probability that Algorithm 2 detects a copy of H in these graphs goes to 0.
Let us begin with the case of testing cycles. Let p be a large prime number, and let X be
log log log p+4

a subset of {0, . . . , p − 1} of size p′ ≥ p1− log log p , where p′ is as defined in Lemma 2. Graph
BC(k, p) is then constructed as follows. The vertex set V is the disjoint union of an odd number
k of sets, V 0 , V 2 , . . . V k−1 , of p elements each. For every l, 0 ≤ l ≤ k − 1, let uli , i = 0, . . . , p − 1
be the nodes in V l so that
V l = {uli | i ∈ {0, . . . , p − 1}}.
For every i ∈ {0, . . . , p − 1} and every x ∈ X, edges in BC(k, p) form a cycle
k−1
Ci,x = (u0i , . . . , uli+lx , ul+1
i+(l+1)x , . . . , ui+(k−1)x ),

where the indices are taken modulo p. The cycles Ci,x form a set of pp′ edge-disjoint copies of
Ck in BC(k, p). Indeed, for any two distinct pairs (i, x) 6= (i′ , x′ ), the cycles Ci,x and Ci′ ,x′ are
7

edge-disjoint. Otherwise there exists a common edge e between the two cycles. It can be either
between two consecutive layers V l and V l+1 , or between V 0 and V k−1 . There are two cases. If
′
′
′
′
e = {uly , ul+1
z } we must have y = i + lx = i + lx and z = i + (l + 1)x = i + (l + 1)x , where
equalities are taken modulo p, and, as a consequence, (i, x) = (i′ , x′ ). If e = {u0y , uzk−1 } then we
have y = i = i′ and z = i + (k − 1)x′ = i′ + (k − 1)x′ , and, since p is prime, we also conclude
that (i, x) = (i′ , x′ ).
We now show that any k-cycle has exactly one vertex in each set V l , for 0 ≤ l < k − 1. For
this purpose, we focus on the parity of the layers formed by consecutive vertices of a cycle. The
“short” edges (i.e., ones between consecutive layers) change the parity of the layer, and hence
every cycle must include “long” edges (i.e., ones between layers 0 and k − 1). However, long
edges do not change the parity of the layer. Therefore, every cycle contains an odd number of
long edges, and an even number of short edges. For this to occur, the only possibility is that
the cycle contains a vertex from each layer.
Next, we show that any cycle of k vertices in BC(k, p) must be of the form Ci,x for some pair
k−1
(i, x). Let C = (u0y0 , . . . ulyl , ul+1
yl+1 , . . . , uyk−1 ) be a cycle in BC(k, p). For every l = 1, . . . , k − 1,
l
let xl = yl − yl−1 mod p. We have xl ∈ X because the edge {ul−1
yl−1 , uyl } is in some cycle Ci,xl .
} is in the cycle Cy0 ,xk . In particular we must
Also set xk ∈ X such that the edge {u0y0 , uyk−1
k−1
have that yk−1 = y0 + (k − 1)xk . It follows that yk−1 = y0 + (k − 1)xk = y0 + x1 + x2 + · · · + xk−1 .
By Lemma 2, we must have x1 = · · · = xk−1 = xk , so C is of the form Ci,x .
It follows from the above that BC(k, p) has exactly pp′ edge-disjoint cycles of k vertices.
Since BC(k, p) has n = kp vertices, and m = kpp′ edges, BC(k, p) is ǫ-far from being Ck -free,
for ǫ = k1 . Also, each vertex of BC(k, p) is of degree 2p′ because each vertex belongs to p′
edge-disjoint cycles.
Let us now consider an execution of Algorithm 2 for input BC(k, p). As BC(k, p) is regular
2k
to detect any given cycle C
of degree d = 2p′ , this execution has probability at most dk−2
of k vertices. Indeed, C must be detected along one of the paths formed by its vertices in
graph BC(k, p), there are at most 2k such paths in C (because all Ck ’s in BC(k, p) are induced
subgraphs, and paths are oriented), and, by Eq. (3), the probability of detecting the cycle along
1
. Therefore, applying the union bound, the probability of detecting a
one of its paths is dk−2
2k
given cycle C is at most dk−2
.
′
Since there are pp edge-disjoint cycles, the expected number of cycles detected in one execu2kpp′
tion of Algorithm 2 is at most (2p
′ )k−2 . It follows that the expected number of cycles detected by
repeating the algorithm T times is at most

2kpT
.
2(2p′ )k−3

Consequently, the probability that the al-

2kpT
′
1−o(1) ,
gorithm detects a cycle is at most 2(2p
′ )k−3 . Plugging in the fact that, by Lemma 2, p = p
we conclude that, for any constant T , the probability that T repetitions of Algorithm 2 detect
a cycle goes to 0 when p goes to ∞, as claimed.

The case of the complete graph is treated similarly. Graphs BK(k, p) are constructed in
a way similar to BC(k, p), as k-partite graphs with p vertices in each partition (in particular, BK(k, p) also has n = kp vertices). The difference with BC(k, p) is that, for each pair
(i, x) ∈ {0, . . . , p − 1} × X, we do not add a cycle, but a complete graph Ki,x on the vertex
k−1
set {u0i , . . . , uli+lx , ul+1
i+(l+1)x , . . . , ui+(k−1)x }. By the same arguments as for BC(k, p), BK(k, p)
contains contains exactly pp′ edge-disjoint copies of Kk (namely Ki,x , for each pair (i, x)). This
fact holds even for even values of k, because any k-clique must have
 a vertex in each layer, no
matter the parity of k. Thus, in particular BK(k, p) has m = k2 pp′ edges, and every vertex
2
.
is of degree d = (k − 1)p′ . The graph BK(k, p) is ǫ-far from being Kk -free, for ǫ = k(k−1)
k!
The probability that Algorithm 2 detects a given copy of Kk is at most dk−2
. Indeed, a given
Kk has k! (oriented) paths of length k, and, by Eq. (3), the probability that the algorithm

8

detects this copy along a given path is

1
.
dk−2

The expected number E[N ] of Kk ’s detected in
′

T pp
k! pT
T runs of Algorithm 2 is, as for BC(k, p), at most k!dk−2
= (k−1)k−2
. Therefore, since
(p′ )k−3
Pr[N 6= 0] ≤ E[N ], we get that the probability that the algorithm detects some Kk goes to 0
as p goes to ∞. It follows that the algorithm fails to detect Kk , as claimed.


Remark. The proof that Algorithm 2 fails to detect Ck for odd k ≥ 5, can be extended to all
(odd or even) k ≥ 13, as well as to k = 10. The cases of C6 , C8 , are C12 are open, although we
strongly believe that Algorithm 2 also fails to detect these cycles in some graphs.

4

Detecting Small Graphs Using a BFS Approach

We discuss here another very natural approach, extending the algorithm proposed by CensorHillel et al. [7] for testing triangle-freeness. In the protocol of [7], each node u samples two neighbors v1 and v2 uniformly at random, and asks them to check the presence of an edge between
them. We generalize this protocol as follows. Assume that the objective is to test H-freeness,
for a graph H containing a universal vertex. Each node u samples d(u) sets S1 , . . . , Sd(u) , of
|V (H)| − 1 neighbors each. For each i = 1, . . . , d(u), node u sends Si to all its neighbors in Si ,
asking them to check the presence of edges between them, and collecting their answers. Based
on these answers, node u can tell whether G[Si ∪ {u}] contains H. We show that this very
simple algorithm can be used for testing K4 -freeness.
Theorem 3 There is a 1-sided error distributed property-testing algorithm for K4 -freeness,
performing in a constant number of rounds in the CONGEST model.
Proof. Again, we show the theorem by exhibiting a generic distributed testing protocol for
testing H-freeness, that applies to any graph H on four vertices with a universal vertex. The
core of this algorithm is presented as Algorithm 3 where all calculations on indices are performed
modulo d = d(u) at node u. This algorithm is presented for a graph H with k nodes.
Algorithm 3: Testing H-freeness for H with a universal vertex. Instructions for node u
of degree d. We let k = |V (H)|.
1
2
3
4
5
6
7
8
9

send id(u) to all neighbors;
index the d neighbors v0 , . . . , vd−1 in increasing order of their IDs;
pick a permutation π ∈ Σd of {0, 1, . . . , d − 1}, u.a.r.;
for each i ∈ {0, . . . , d − 1} do
Send (id(vπ(i) ), id(vπ(i+1) ), . . . , id(vπ(i+k−2) )) to vπ(i) , vπ(i+1) , . . . , vπ(i+k−2) ;
for each i ∈ {0, . . . , d − 1} do
for each of the k − 1 tuples (id(w(1) ), . . . , id(w(k−1) )) received from vi do
Send (b(1) , . . . , b(k−1) ) to vi where b(j) = 1 iff u = w(j) or {u, w(j) } ∈ E;
If ∃i ∈ {0, . . . , d − 1} s.t. H ⊆ G[u, vπ(i) , . . . , vπ(i+k−2) ] then reject else accept.

At Step 3, node u picks a permutation π u.a.r., in order to compose the d(u) sets S1 , . . . , Sd(u) ,
which are sent in parallel at Steps 4-5. At Step 8, every node u considers separately each of
the k − 1 tuples of size k − 1 received from each of its neighbors, checks the presence of edges
between u and each of the nodes in that tuple, and sends back the result to the neighbor from
which it received the tuple. Finally, the tests H ⊆ G[u, vπ(i) , vπ(i+1) , . . . , vπ(i+k−2) ] performed at
the last step is achieved thanks to the (k − 1)-tuple of bits received from each of the neighbors
9

vπ(i) , vπ(i+1) , . . . , vπ(i+k−2) , indicating the presence or absence of all the edges between these
nodes. Note that exactly 2k − 5 IDs are actually sent through each edges at Steps 4-5, because
of the permutation shifts. Similarly, 2k − 5 bits are sent through each edge at Steps 6-8.
Therefore Algorithm 3 runs in a constant number of rounds in the CONGEST model.
We now show that, for any given G which is ǫ-far from being K4 -free, Algorithm 3 for
H = K4 rejects G with constant probability.
Let K be a copy of K4 containing a node u. Note that d(u) ≥ k − 1 (this condition will
be implicitly used in the sequel). Observe that, if u samples the vertices of K \ {u} (Step 5 of
Algorithm 3), then u will detect K. Let us first prove that


d(u)
Pr[u detects K] = d(u)/
.
(4)
k−1
Indeed, among the d(u)! permutations π of Σd(u) , the ones that sample K \ {u} are those
where the vertices of K \ {u} appear consecutively as vπ(i) , . . . , vπ(i+d−1) , for some i, 0 ≤ i ≤
d(u)−1 (recall that indices are taken modulo d in Algorithm 3). We say that we insert a sequence
(y0 , . . . yk−2 ) into a sequence (x0 , . . . , xi , xi+1 . . . , xd(u)−k ) starting from position i ≤ d(u)−k+1,
for creating the sequence
(x0 , . . . , xi−1 , y0 , . . . , yk−2 , xi , . . . , xd(u)−k ).
If i > d(u) − k + 1, the insertion of (y0 , . . . yk−2 ) into (x0 , . . . , xd(u)−k ) at position i means the
sequence
(yd(u)−i , . . . , yk−2 , x0 , . . . , xd(u)−k , y0 , . . . , yd(u)−i−1 ).
The permutations that sample K\{u} are the permutations obtained from one of the (d(u) − k + 1)!
permutations of the vertices of N (u) \ K by inserting one of the (k − 1)! permutations of K \ {u}
starting from position i, 0 ≤ i ≤ d(u) − 1, which proves Equation 4.
Since G is ǫ-far from being K4 -free, it follows from Lemma 1 that the graph G contains a
family of ǫm
6 edge-disjoint copies of K4 . For each vertex u, denote by c(u) the number of copies
(i)

in this family that contain u. For i = 0, . . . , c(u) − 1, let Xu be the random variable indicating
whether u detects the ith copy of K4 incident to it, and denote by Xu the random variable
indicating whether u detects at least one of these copies. We have:
Pr[Xu = 1] = Pr[(Xu(0) = 1) ∨ (Xu(1) = 1) ∨ · · · ∨ (Xu(c(u)−1) = 1)].
By the inclusion-exclusion principle and Bonferroni’s inequality [6] (Exercise 1.7 in [26]), we get
Pr[Xu = 1] ≥

c(u)
X

Pr[Xu(i) = 1] −

i=1

X

Pr[Xu(i) = 1 ∧ Xu(j) = 1].

(5)

1≤i<j≤c(u)

(i)

Now, for every i, Pr[Xu = 1] is given by Equation 4. In particular,
Pr[Xu(i) = 1] =

(k − 1)!
,
(d(u) − 1)(d(u) − 2) . . . (d(u) − k + 2)

which, for k = 4, gives
Pr[Xu(i) = 1] ≥

6
,
(d(u) − 1)(d(u) − 2)

10

(6)

and

c(u)
X

Pr[Xu(i) = 1] ≥

i=1

6c(u)
.
(d(u) − 1)(d(u) − 2)

(7)

We now claim that, for any pair i, j such that 0 ≤ i < j ≤ c(u), we have
Pr[Xu(i) = 1 ∧ Xu(j) = 1] ≤

d(u)2 ((k − 1)!)2 (d(u) − 2(k − 1))!
.
d(u)!

Indeed, let K i and K j be edge-disjoint copies of K4 containing u corresponding to the random
(i)
(j)
(i)
variables Xu and Xu . Among the d(u)! permutations of N (u), those who will satisfy Xu =
(j)
Xu = 1 are such that the elements of K i \ {u} and of K j \ {u} appear consecutively (in the
cyclic order). Such a permutation is obtained from one of the (d(u) − 2(k − 1))! permutations
of N (u) \ (K i ∪ K j ), by inserting one of the (k − 1)! permutations of K i \ {u}, and one of the
(k − 1)! permutations of K j \ {u}, each at one of the d(u) possible positions between 0 and
d(u) − 1. The inequality holds automatically if d(u) ≥ 2(k − 1), as otherwise there cannot be
two edge-disjoint copies of Kk containing u. In particular, for k = 4, we obtain
Pr[Xu(i) = 1 ∧ Xu(j) = 1] ≤

36d(u)
36d(u)2 (d(u) − 6)!
=
.
d(u)!
(d(u) − 1)(d(u) − 2) . . . (d(u) − 5)

Therefore,
X

Pr[Xu(i)

1≤i<j≤c(u)

=1∧

Xu(j)

= 1] ≤




c(u)
36d(u)
.
2 (d(u) − 1)(d(u) − 2) . . . (d(u) − 5)

For each u, we have c(u) ≤ d(u)
3 because c(u) counts edge-disjoint copies of K4 containing u. So


d(u) − 3
c(u)
c(u)(c(u) − 1)
≤ c(u) ·
,
=
2
6
2
and
X

0≤i<j≤c(u)

Pr[Xu(i) = 1 ∧ Xu(j) = 1] ≤ c(u)

6d(u)
.
(d(u) − 1)(d(u) − 2)(d(u) − 4)(d(u) − 5)

(8)

By Eq. (5), and by subtracting Eq. (7) and (8), we obtain


d(u)
6c(u)
1−
.
Pr[Xu = 1] ≥
(d(u) − 1)(d(u) − 2)
(d(u) − 4)(d(u) − 5)
If d(u) ≥ 8, the the expression in the parenthesis is at least 1/3. Therefore, if d(u) ≥ 8 then
Pr[Xu = 1] ≥

2c(u)
.
d(u)2

For vertices u such that d(u) < 8, observe that c(u) ≤ 2. Therefore, thanks to Eq. (6), we deduce
2c(u)
that the probability that u detects a K4 is at least d(u)
2 . Consequently, for any vertex u,
Pr[Xu = 1] ≥

11

2c(u)
.
d(u)2

(9)

Let Y denote the random variable counting thePnumber of vertices u such that u detects one of
the ǫm
u∈V (G) Xu and, by Equation 9,
6 edge-disjoint copies of K4 . Hence Y =
E[Y ] ≥

X 2c(u)
d(u)2

u∈V (G)

Let us prove that this expectation is lower bounded by a positive constant. We say that the
vertex u is good if d(u) ≤ 24c(u)
ǫ . Otherwise, u is bad. The set of good vertices is denoted by
Good(G) and the set of bad vertices is denoted by Bad(G). Observe that
X
ǫm
c(u) <
,
12
u∈Bad(G)

because
2m =

X

X

d(u) ≥

u∈V (G)

X

d(u) >

u∈Bad(G)

u∈Bad(G)

24c(u)
.
ǫ

ǫm
6

Therefore, among the
edge-disjoint copies of K4 , at least half do not contain bad nodes, i.e.,
all their nodes are good. Hence, the number of edges between good vertices is at least ǫm
2 .
Now, we claim that among good vertices, at least half have degree at most 8g
ǫ . By contra′
diction, let g = |Good(G)| and assume that there is a set Good (G) ⊆ Good(G) containing at
least 2g vertices, each of degree greater than 8g
ǫ . Then
m≥

1
2

X

d(u) >

u∈Good′ (G)

1 g 8g
2g2
· ·
=
.
2 2 ǫ
ǫ

The number of edges between good vertices is at most

g
2

and at least

ǫm
2 .

In particular,

 
ǫ 2g2
g
ǫm
> ·
= g2 ,
≥
2
2 ǫ
2
a contradiction.
It follows from the above that
E[Y ] ≥

X

2

u∈Good(G)

and, by summing only over the at least

g
2

c(u)
≥
d(u)2

X

u∈Good(G)

2

c(u) 1
d(u) d(u)

good vertices of degree at most

E[Y ] ≥ 2 ·

8g
ǫ ,

we conclude that

ǫ
ǫ2
g ǫ
·
·
=
.
2 24 8g
192

Recall that Y is the sum of independent boolean variables Xu . Let N be the random variable
counting the number of vertices detecting a K4 in T iterations of Algorithm 3, so N = T · Y .
For T = 8 ln 3 · 192
, we have that
ǫ2
E[N ] ≥ 8 ln 3.
Chernoff bound applies to variable N and, as in the proof of Theorem 1, we conclude that
Pr[N ≤ 4 ln 3] ≤ 31 . Altogether, a copy of K4 is detected with probability at least 23 , which
completes the proof.

12

5

Limits of the BFS Approach

As it happened with the DFS-based approach, the BFS-based approach fails to generalize to
large graphs H. Actually, it already fails for K5 .
Theorem 4 Let k ≥ 5. There exists a graph G that is ǫ-far from being Kk -free in which any
constant number of repetitions of Algorithm 3 fails to detect any copy of Kk , with probability at
least 1 − o(1).
Proof. The family of graphs BK(k, p) constructed in the proof of Theorem 2 for defeating
Algorithm 2 can also be used to defeat Algorithm 3. Recall that those graphs have n = kp
vertices, m = k2 pp′ edges, and every vertex is of degree d = (k − 1)p′ , for p′ = p1−o(1) .
Moreover, they have exactly pp′ copies of
Kk , which are pairwise edge-disjoint. BK(k, p) is
k
ǫ-far from being Kk -free with ǫ = 1/ 2 . By Equation 4, for each copy K of Kk , and for
d 
α
for some constant α > 0.
every u ∈ K, the probability that u detects K is d/ k−1
≤ dk−2
Therefore, when running the algorithm T times, it follows from the union bound that the
pp′
, which tends to 0 when p → ∞, for
expected number of detected copies of Kk is at most αkT
dk−2
any k ≥ 5. Consequently, the probability of detects at least one copy of Kk also tends to 0. 

6

Conclusion and Further Work

We have proved that not only the presence of triangles can be tested in O(1) rounds in the
CONGEST model, but also the presence of any 4-node subgraph. On the other hand, we have also
proved that the natural approaches used to test such small patterns fail to detect larger patterns,
like the presence of Kk for k ≥ 5. Interestingly, as mentioned before, the lower bound techniques
for the CONGEST model are essentially based on reductions to communication complexity
problems. Such an approach does not seem to apply easily in the context of distributed testing.
The question of whether the presence of large cliques (or cycles) can be tested in O(1) rounds
in the CONGEST model is an intriguing open problem.
It is worth mentioning that our algorithms generalize to testing the presence of induced
subgraphs. Indeed, if the input graph G contains at least ǫm edge-disjoint induced copies of H,
for a graph H on four vertices containing a Hamiltonian path, then Algorithm 1 detects an
induced subgraph H with constant probability (the only difference is that, in the last line of
the algorithm, we check for an induced subgraph instead of just a subgraph). Moreover, if the
input contains ǫm edge-disjoint induced claws (i.e., induced subgraphs K1,3 ), then Algorithm 3
detects one of them with constant probability. Thus, for any connected graph H on four vertices,
distinguishing between graphs that do not have H as induced subgraph, and those who have
ǫm edge-disjoint induced copies of H can be done in O(1) rounds in the CONGEST model.
However, we point out that, unlike in the case of subgraphs, a graph that is ǫ-far from having
H as induced subgraph may not have many edge-disjoint induced copies of H.

13

References
[1] Noga Alon, Tali Kaufman, Michael Krivelevich, and Dana Ron. Testing triangle-freeness
in general graphs. SIAM J. Discrete Math., 22(2):786–819, 2008.
[2] Heger Arfaoui, Pierre Fraigniaud, David Ilcinkas, and Fabien Mathieu. Distributedly testing cycle-freeness. In 41st Graph-Theoretic Concepts in Computer Science (WG), volume
8747 of LNCS, pages 15–28, 2014.
[3] Heger Arfaoui, Pierre Fraigniaud, and Andrzej Pelc. Local decision and verification with
bounded-size outputs. In 15th Int. Symposium on Stabilization, Safety, and Security of
Distributed Systems (SSS), volume 8255 of LNCS, pages 133–147. Springer, 2013.
[4] Florent Becker, Adrian Kosowski, Martin Matamala, Nicolas Nisse, Ivan Rapaport, Karol
Suchan, and Ioan Todinca. Allowing each node to communicate only once in a distributed
system: shared whiteboard models. Distributed Computing, 28(3):189–200, 2015.
[5] Felix A Behrend. On sets of integers which contain no three terms in arithmetical progression. Proceedings of the National Academy of Sciences of the United States of America,
32(12):331, 1946.
[6] C.E. Bonferroni. Teoria statistica delle classi e calcolo delle probabilità. Pubblicazioni del
R. Istituto superiore di scienze economiche e commerciali di Firenze. Libreria internazionale
Seeber, 1936.
[7] Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. CoRR, abs/1602.03718, Feb. 2016.
[8] Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and
Jukka Suomela. Algebraic methods in the congested clique. In ACM Symposium on Principles of Distributed Computing (PODC), pages 143–152, 2015.
[9] Atish Das-Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal
Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness
of distributed approximation. SIAM J. Comput., 41(5):1235–1265, 2012.
[10] Danny Dolev, Christoph Lenzen, and Shir Peled. “Tri, Tri Again”: Finding triangles and
small subgraphs in a distributed setting. In 26th International Symposium on Distributed
Computing (DISC), volume 7611 of LNCS, pages 195–209, 2012.
[11] Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique
model. In ACM Symposium on Principles of Distributed Computing (PODC), pages 367–
376, 2014.
[12] Michael Elkin. An unconditional lower bound on the time-approximation trade-off for the
distributed minimum spanning tree problem. SIAM Journal on Computing, 36(2):433–456,
2006.
[13] Pierre Fraigniaud, Mika Göös, Amos Korman, and Jukka Suomela. What can be decided
locally without identifiers? In ACM Symposium on Principles of Distributed Computing
(PODC), pages 157–165, 2013.
[14] Pierre Fraigniaud, Amos Korman, and David Peleg. Local distributed decision. In 52nd
IEEE Symp. on Foundations of Computer Science (FOCS), pages 708–717, 2011.
14

[15] Pierre Fraigniaud, Sergio Rajsbaum, and Corentin Travers. Locality and checkability in
wait-free computing. Distributed Computing, 26(4):223–242, 2013.
[16] Pierre Fraigniaud, Sergio Rajsbaum, and Corentin Travers. On the number of opinions
needed for fault-tolerant run-time monitoring in distributed systems. In 5th International
Conference on Runtime Verification (RV), LNCS 8734, pages 92–107. Springer, 2014.
[17] Oded Goldreich, editor. Property Testing - Current Research and Surveys, volume 6390 of
LNCS. Springer, 2010.
[18] Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to
learning and approximation. Journal of the ACM, 45(4):653–750, 1998.
[19] Mika Göös and Jukka Suomela:. Locally checkable proofs. In 30th ACM Symposium on
Principles of Distributed Computing (PODC), pages 159–168, 2011.
[20] James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh,
and Michele Scquizzato. Toward optimal bounds in the congested clique: Graph connectivity and MST. In ACM Symposium on Principles of Distributed Computing (PODC),
pages 91–100, 2015.
[21] James W. Hegeman, Sriram V. Pemmaraju, and Vivek Sardeshmukh. Near-constanttime distributed algorithms on a congested clique. In 28th Int. Symposium on Distributed
Computing (DISC), pages 514–530, 2014.
[22] Jarkko Kari, Martin Matamala, Ivan Rapaport, and Ville Salo. Solving the induced subgraph problem in the randomized multiparty simultaneous messages model. In 22nd Int.
Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 9439 of LNCS, pages 370–384. Springer, 2014.
[23] Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In
ACM Symposium on Principles of Distributed Computing (PODC), pages 42–50, 2013.
[24] Zvi Lotker, Boaz Patt-Shamir, and David Peleg. Distributed MST for constant diameter
graphs. Distributed Computing, 18(6):453–460, 2006.
[25] Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. MST construction in
O(log log n) communication rounds. In 15th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pages 94–100, 2003.
[26] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and
Probabilistic Analysis. Cambridge University Press, 2005.
[27] Boaz Patt-Shamir and Marat Teplitsky. The round complexity of distributed sorting. In
ACM Symposium on Principles of Distributed Computing (PODC), pages 249–256, 2011.
[28] David Peleg. Distributed Computing: A Locality-sensitive Approach. SIAM, Philadelphia,
PA, USA, 2000.
[29] Fabian Reiter. Distributed graph automata. In 30th Annual ACM/IEEE Symposium on
Logic in Computer Science (LICS), pages 192–201, 2015.
[30] Tomasz Schoen and Ilya D. Shkredov. Roth’s theorem in many variables. Israel Journal
of Mathematics, 199(1):287–308, 2014.

15

