Faster and Simpler Distributed Algorithms
for Testing and Correcting Graph
Properties in the CONGEST-Model
arXiv:1705.04898v1 [cs.DC] 13 May 2017

Guy Even∗

Reut Levi†

Moti Medina†

Abstract
In this paper we present distributed testing algorithms of graph properties in the
CONGEST-model [CHFSV16]. Concretely, a distributed one-sided error ε-tester for
a property P meets the following specification: if the network has the property P,
then all of the network’s processors should output YES, and if the network is ε-far
from having the property, according to a predetermined distance measure, then at
least one processor outputs NO with probability at least 2/3.
We present one-sided error testing algorithms in the general graph model.
We first describe a general procedure for converting ε-testers with a number
of rounds f (D), where D denotes the diameter of the graph, to O((log n)/ε) +
f ((log n)/ε) rounds, where n is the number of processors of the network. We
then apply this procedure to obtain an optimal tester, in terms of n, for testing
bipartiteness, whose round complexity is O(ε−1 log n), which improves over the
Poly(ε−1 log n)-round algorithm by Censor-Hillel et al. (DISC 2016). Moreover, for
cycle-freeness, we obtain a corrector of the graph that locally corrects the graph so
that the corrected graph is acyclic. Note that, unlike a tester, a corrector needs to
mend the graph in many places in the case that the graph is far from having the
property.
In the second part of the paper we design algorithms for testing whether the
network is H-free for any connected H of size up to four with round complexity
of O(ε−1 ). This improves over the O(ε−2 )-round algorithms for testing triangle
freeness by Censor-Hillel et al. (DISC 2016) and for testing excluded graphs of size
4 by Fraigniaud et al. (DISC 2016).
In the last part we generalize the global tester by Iwama and Yoshida [IY14] of
testing k-path freeness to testing the exclusion of any tree of order k. We then show
2
how to simulate this algorithm in the CONGEST-model in O(kk +1 · ε−k ) rounds.

Keywords. Property testing, Property correcting, Distributed algorithms, CONGEST
model.
∗

Tel-Aviv University, Israel guy@eng.tau.ac.il
Max Planck Institute for Informatics,
{rlevi,mmedina}@mpi-inf.mpg.de
†

1

Saarland

Informatics

Campus,

Germany

1

Introduction

In graph property testing [GGR98, GR02] the goal is to design a sequential sublinear
algorithm that, given a query access to a graph, decides whether the graph has a given
property or is ε-far from having it. By sublinear we mean that the number of queries that
the algorithm generates is much smaller than the size of the graph. In the general graph
model, a graph, G = (V, E), is ε-far from satisfying a property if at least ε · |E| edges
should be added or removed so that the graph will have the property. Graph property
testing in the distributed CONGEST-model has been initiated recently by Censor-Hillel
et al. [CHFSV16]. In this setting, each processor locally gathers in a parallel and synchronized fashion information from the network while abiding to a logarithmic bandwidth
constraint. When the distributed algorithm terminates, each processor outputs ACCEPT
in case the graph (which acts as the network on which the processors communicate) has
the tested property (for one-sided error testing), and in case the graph is ε-far from the
property, then there is at least one processor that outputs REJECT with probability at
least 2/3. In the distributed setting the goal is to design algorithms with small number
of rounds.
In this paper we present improved testers to various properties, such as: is the graph
bipartite? Acyclic? Does the graph contain a copy of predetermined tree of size k?
or other subgraphs of size at most 4? We obtain these results in three different ways:
(1) we demonstrate a procedure that given an ε-tester in the CONGEST-model with linear
dependency on the network’s diameter reduces it to a logarithmic dependency in the size
of the graph. This technique yields improved algorithm for testing bipartiteness. (2) We
directly design improved algorithms for testing whether the graph does not contain a
copy of a subgraph of size at most 4. An important ingredient of testing whether a copy
of subgraph of size 4 exists is the ability to pick u.a.r. a path of length 2 that emanates
from a specific vertex in the CONGEST-model. (3) In the last part we design an ε-tester
for the property of being free from copies of a specific tree of size k. We then simulate
this ε-tester with the same number of rounds as the number of queries of the sequential
tester.

1.1

Related Work

Property testing in the distributed CONGEST-model was initiated by Censor-Hillel et
al. [CHFSV16]. In [CHFSV16], the distributed testing model was defined as well as
various testing algorithms of whether a graph is: triangle-free, cycle-free, or bipartite
(i.e., free of odd cycles). Additionally, a logarithmic lower bound was proven for testing
bipartiteness and cycle-freeness. Finally, a simulation of sequential (or global) testers for
a certain class of graph properties in the dense model is given. This simulation incurs a
quadratic blow-up w.r.t. the tester’s number of queries.
Fraigniaud et al. [FRST16] studied testing of excluding subgraphs in the CONGESTmodel. In [FRST16] an algorithm for testing whether a graph does not contain a specific
subgraph (or any isomorphic copy of it) of size 4. The number of rounds of this algorithm
does not depend on the size of the graph. Fraigniaud et al. [FRST16] also consider the
problem of testing whether a graph excludes subgraphs of size k ≥ 5 (e.g., C5 or K5 ).
For these properties, they present a “hard” family of graphs for which some “natural”
property testing algorithms have a round complexity that depends on the size of the
2

graph.
Our notion of correction is inspired by work on local reconstruction of graph properties (see for example [CGR13] and [KPS13]). However, we note that our definition of
correction does not assume anything on the input graph. In particular, we do not assume
that it is close to having the required property.

1.2

Our Contributions

We design and analyze distributed testers in the distributed CONGEST-model all of which
work in the general graph model. In this model, a graph G = (V, E) is called ε-far from
having a property P, if one must remove or add at least ε|E| edges from G in order to
obtain the property P.
Diameter dependency reduction and its Applications. In Section 3 we describe a general procedure for converting ε-testers with f (D) rounds, where D denotes
the diameter of the graph to a O((log n)/ε) + f ((log n)/ε) rounds, where n is the number of processors of the network. We then apply this procedure to obtain an ε-tester
for testing whether a graph is bipartite. The improvement of this tester over state
of the art is twofold: (a) the round complexity is O(ε−1 log n), which improves over
the Poly(ε−1 log n)-round algorithm by Censor-Hillel et al. [CHFSV16, Thm. 5.2], and
(b) our tester works in the general model while [CHFSV16] works in the more restrictive
bounded degree model. Moreover, the number of rounds of our bipartiteness tester meets
the Ω(log n) lower bound by [CHFSV16, Thm. 7.3], hence our tester is asymptotically
optimal in terms of n. We then apply this “compiler” to obtain a cycle-free tester with
number of rounds of O(ε−1 · log n), thus revisiting the result by [CHFSV16, Thm. 6.3].
The last application that we consider is “how to obtain a corrector of the graph by using
this machinery?” Namely, how to produce a an algorithm that locally corrects the graph
so that the corrected graph satisfies the property. For cycle-freeness, we are able to obtain
also a corrector. Note that, unlike a tester, a corrector needs to mend the graph in many
places in the case that the graph is far from having the property.
Testers for H-freeness for |V (H)| ≤ 4. In Section 4 we design algorithms for
testing (in the general graph model) whether the network is H-free for any connected H
of size up to four with round complexity of O(ε−1 ). By H-free we mean that there is no
sub-graph H ′ of G such that H is isomorphic to H. This improves over the O(ε−2)-round
algorithms for testing triangle freeness by Censor-Hillel et al. [CHFSV16, Thm. 4.1] and
for testing excluded graphs of size 4 by Fraigniaud et al. [FRST16, Thm. 1].
Testers for tree-freeness. In Section 5 we first generalize the global tester by
Iwama and Yoshida [IY14] of testing k-path freeness to testing the exclusion of any tree,
T , of order k. Note that in this part of the paper we do not make any assumption of the
size of the tree, e.g., k can be larger than 4. Our tester has a one sided error and it works
in the general graph model with random edge queries. We, then, show how to simulate
2
this algorithm in the CONGEST-model in O(k k +1 · ε−k ) rounds.

3

2

Computational Models

Notations. Let G = (V, E) denote a graph, were V is the set of vertices and E is
the set of edges. Let n , |V (G)|, and let m , |E(G)|. For every v ∈ V , let NG (v) , {u ∈
V | {u, v} ∈ E} denote the neighborhood of v in G. For every v ∈ V , let dG (v) , |NG (v)|
denote the degree of v. When the graph at hand is clear from the context we omit the
subscript G.

2.1

Distributed CONGEST-Model

Computation in the distributed CONGEST-model [Pel00] is done as follows. Let G =
(V, E) denote a network where each vertex is a processor and each edge is a communication
link between its two endpoints. Each processor is input a local input. Each processor
v has a distinct ID - for brevity we say that the ID of processor v is simply v.1 The
computation is synchronized and is measured in terms of rounds. In each round (1) each
processor does a local computation, and then (2) sends (different) messages of O(log n)
bits to each of its neighbors (or a possible “empty message”). After the last round all
the processors stop and output a local output.

2.2

(Global) Testing Model

Graph property testing [GGR98, GR02] is defined as follows. Let G = (V, E) denote a
graph. We assume that for each v ∈ V there is an arbitrary order on its set of neighbors.
Let P denote a graph property, e.g., the graph is cycle-free, the graph is bipartite, etc.
We say that a graph G is ε-far (in the general graph model) from having the property
P if at least ε · m edges E ′ should be added or removed from E(G) so as to obtain the
property P.
An algorithm in this model is given a query access to G of the form: (1) what is the
degree of v for v ∈ V ? (2) who is ith neighbor of v ∈ V ?
We say that an algorithm is a ε-tester for property P, one sided, in the general graph
model if given query access to the graph G the algorithm ACCEPTS the graph G if G
has the property P, i.e, completeness, and REJECTS the graph G with probability at
least 2/3 if G is ε-far from having the property P, i.e., soundness.
The complexity measure of this model is the number of queries made to G. Usually,
the goal is to design an ε-tester with o(n) number of queries.
In Section 5 an additional query type is allowed of random edge query where an edge
e is picked u.a.r. from E.

2.3

Distributed Testing in the CONGEST-model

Let G = (V, E) be a graph and let P denote a graph property. We say that a randomized distributed CONGEST algorithm is an ε-tester for property P in the general graph
model [CHFSV16] if when G has the property P then all the processors v ∈ V output
ACCEPT, and if G is ε-far from having the property P, then there is a processor v ∈ V
that outputs REJECT with probability at least 2/3.
1

In this paper we focus on randomized algorithms, hence one can omit the assumption that each
processor has a distinct ID.

4

2.4

Distributed Correcting

In this section we define correction in the distributed setting. We then explain how to
obtain correction for the property of cycle-freeness.
Definition 1. A graph property P is edge-monotone if G ∈ P and if G′ is obtained from
G by the removal of edges, then G′ ∈ P.
Definition 2. In the distributed CONGEST-model, we say that an algorithm is an εcorrector for an edge-monotone property P if the following holds.
1. Let G = (V, E) denote the network’s graph. When the algorithm terminates, each
processor v knows which edges in E, that incident to v, are in the set of deleted
edges E ′ ⊆ E.
2. G(V, E \ E ′ ) is in P.
3. |E ′ | ≤ dist(G, P) + ε|E|, where dist(G, P) denotes the minimum number of edges
that should be removed from G in order to obtain the property P.

3

Reducing the Dependency on the Diameter and
Applications

In this section we present a general technique that reduces the dependency of the round
complexity on the diameter. The technique is based on graph decompositions defined
below.
Definition 3 ([MPX13]). Let G = (V, E) denote an undirected graph. A (β, d)-decomposition
of G is a partition of V into disjoint subsets V1 , . . . , Vk such that (i) For all 1 ≤ i ≤ ℓ,
diam(G[Vi ]) ≤ d, where G[Vi ] is the vertex induced subgraph of G that is induced by Vi .
(ii) The number of edges with endpoints belonging to different subsets is at most ε · |E|.
We refer to these as cut-edges of the decomposition.
Note that the diameter constraint refers to strong diameter, in particular, each induced
subgraph G[Vi ] must be connected.
Algorithms for (ε, (log n)/ε)-decompositions were developed in many contexts (e.g.,
parallel algorithms [ABCP92, BGK+ 14, MPX13]). An implementation in the CONGESTmodel can be derived from the algorithm in [EN17] for constructing spanners. Specifically,
we get the following as a corollary from [EN17].
Corollary 1. A (ε, O(log n/ε))-decomposition can be computed in the randomized CONGESTmodel in O((log n)/ε) rounds with probability at least 1 − 1/ Poly(n).
A nice feature of the algorithm based on random exponential shifts is that at the end
of the algorithm, there is a spanning BFS-like rooted tree Ti for each subset Vi in the
decomposition. Moreover, each vertex v ∈ Vi knows the center of Ti as well as its parent
in Ti . In addition, every vertex knows which of the edges incident to it are cut-edges.
The following definition captures the notion of connected witnesses against a graph
satisfying a property.
5

Definition 4 ([CHFSV16]). A graph property P is non-disjointed if for every witness G′
against G ∈ P, there exists an induced subgraph G′′ of G′ that is connected such that G′′
is also a witness against G ∈ P.
The main result of this section is formulated in the following theorem. We refer to a
distributed algorithm in which all vertices accept iff G ∈ P as a verifier for P.
Theorem 2. Let P be an edge-monotone non-disjointed graph property that can be verified in the CONGEST-model in O(diam(G)) rounds. Then there is an ε-tester for P in
the randomized CONGEST-model with O((log n)/ε) rounds.
Proof. The algorithm tries to “fix” G so that it satisfies P by removing less than ε · m
edges. The algorithm consists of two phases. In the first phase, an (ε′ , O((log n)/ε′ )
decomposition is computed in O((log n)/ε′ ) rounds, for ε′ = ε/2. The algorithm removes
all the cut-edges of the decomposition. (There are at most ε · m/2 such edges.) In the
second phase, in each subgraph G[Vi ], an independent execution of the verifier algorithm
for P is executed. The number of rounds of the verifier in G[Vi ] is O(diam(G[Vi ]) =
O((log n)/ε).
We first prove completeness. Assume that G ∈ P. Since P is an edge-monotone
property, the deletion of the cut-edges does not introduce a witness against P. This
implies that each induced subgraph G[Vi ] does not contain a witness against P, and
hence the verifier do not reject, and every vertex accepts.
We now prove soundness. If G is ε-far from P, then after the removal of the cut-edges
(at most εm/2 edges) property P is still not satisfied. Let G′ be a witness against the
remaining graph satisfying P. Since property P is non-disjointed, there exists a connected
witness G′′ in the remaining graph. This witness is contained in one of the subgraphs
G[Vi ], and therefore, the verifier that is executed in G[Vi ] will reject, hence at least one
vertex rejects, as required.
We remark that if the round complexity of the verifier is f (diam(G), n) (e.g., f (∆, n) =
∆ + log n), then the round complexity of the ε-tester is O((log n)/ε) + f ((log n)/ε, n).
This follows directly from the proof.
Extensions to ε-Testers. The following “bootstrapping” technique can be applied.
If there exists an ε-tester in the CONGEST-model with round complexity O(diam(G)),
then there exists an ε-tester with round complexity O((log n)/ε). The proof is along the
same lines, expect that instead of a verifier, an ε′ -tester is executed in each subgraph
G[Vi ]. Indeed, if G is ε-far from P, then, by an averaging argument, there must exist
a subset Vi such that G[Vi ] is ε′ -far from P. Otherwise, we could “fix” all the parts by
deleting at most ε′ · m edges, and thus “fix” G by deleting at most 2ε′ · m = εm edges, a
contradiction.

3.1

Testing Bipartiteness

Theorem 2 can be used to test whether a graph is bipartite or ε-far from being bipartite.
A verifier for bipartiteness can be obtained by attempting to 2-color the vertices (e.g.,
BFS that assigns alternating colors to layers). In our special case, each subgraph G[Vi ]
has a root which is the only vertex that initiates the BFS. In the general case, one would
need to deal with “collisions” between searches, and how one search “kills” the other
searches initiated by vertices of lower ID.
6

3.2

Testing Cycle-freeness

Theorem 2 can be used to test whether a graph is acyclic or ε-far from being acyclic. As
in the case of bipartiteness, any scan (e.g., DFS, BFS) can be applied. A second visit to
a vertex indicates a cycle, in which case the vertex rejects.
Corollary 3. There exists an ε-tester in the randomized CONGEST-model for bipartiteness and cycle-freeness with round complexity O((log n)/ε).

3.3

Corrector for Cycle-Freeness

Our ε-testers for testing cycle freeness can be easily converted into ε-correctors by removing the following edges: (1) All the cut-edges are removed. (2) In each G[Vi ], all the
edges which are not in the BFS-like spanning tree Ti are removed (in order to maintain
consistency with the same spanning tree one needs to define a consistent way for breaking
ties, e.g., by the ID of the vertices).
Therefore, the total number of edges that we keep is at most |V | + ε|E|.
Theorem 4. There exists an ε-corrector for cycle-freeness in the randomized CONGESTmodel with round complexity O((log n)/ε).

4
4.1

Testing H-freeness in Θ(1/ε) Rounds for |V (H)| ≤ 4
Testing Triangle-freeness

In this section we present an ε-tester for triangle-freeness that works in the CONGESTmodel. The number of rounds is O(1/ε).
Consider a violating edge {A, B} and a corresponding triangle ABC in the graph
G = (V, E). This triangle can be detected if A tells B about a neighbor C ∈ N(A) with
the hope that C is also a neighbor of B. Vertex B checks that C is also its neighbor,
and if it is, then the triangle ABC is detected. Hence, A would like to send to B the
name of a vertex C such that C ∈ N(A) ∩ N(B). Since A can discover N(A) in a single
round, it proceeds by telling B about a neighbor C ∈ N(A) \ {B} chosen uniformly
at random. Let MA→B denote the random neighbor that A reports to B. A listing of
the distributed ε-tester for triangle-freeness appears as Algorithm 1. Note that all the
messages {MA→B }(A,B)∈E are independent, and that the messages are re-chosen for each
iteration.
Claim 5. Let {A, B} be a violating edge, then Pr [MA→B ∈ N(B)] ≥ 1/m.
Proof. Let ABC be a triangle which is a witness for the violation of {A, B}. Since ABC
is a triangle, C ∈ N(A) ∩ N(B), and Pr [MA→B ∈ N(B)] ≥ 1/d(A) ≥ 1/m.
Theorem 6. Algorithm 1 is an ε-tester for triangle-freeness.
Proof. Completeness: If G is triangle free then Line 4 is never satisfied, hence for every
v Algorithm 1 terminates at Line 5.
Soundness: Let G = (V, E) be a graph which is ε-far from being triangle free. Therefore there exist at least ε · m edges, each belonging to at least one triangle. Hence,
7

the probability of not detecting any of these triangles in a single iteration is at most
(1 − 1/m)εm . The reject probability is amplified to 2/3 by setting the number of iterations to be Θ(1/ε).
Algorithm 1: Triangle-free-test(v)

4

Send v to all u ∈ N (v)
// 1st round: each v learns N (v)
for t = Θ(1/ε) times do
For all u ∈ N (v), simultaneously: send u the message Mv→u ∼ U (N (v) \ {u}).
If ∃w ∈ N (v) such that Mw→v ∈ N (v) then return REJECT

5

return ACCEPT

1
2
3

4.2

Testing C4-freeness in Θ(1/ε) Rounds

In this section we present an ε-tester in the CONGEST-model for C4 -freeness that runs
in O(1/ε) rounds.
Uniform Sampling of 2-paths. Let P2 (v) denote the set of all paths of length 2 that
start at v. The algorithm is based on the ability of each vertex v to uniformly sample
a path from P2 (v). How many paths in P2 (v) start with the edge (v, w)? Clearly, there
are (d(w) − 1) such paths. Hence the first edge should be
P chosen according to the degree
v
distribution over N(v) defined by π (w) , (d(w) − 1)/ x∈N (v) (d(x) − 1). Moreover, for
each x ∈ N(w) \ {v}, the (directed) edge (w, x) appears exactly once as the second edge
of a path in P2 (v). Hence, given the first edge, the second edge is chosen uniformly.
This implies that v can pick a random path p ∈ P2 (v) as follows: (1) Each neighbor
w ∈ N(v) sends v a uniformly randomly chosen neighbor Bv (w) ∈ N(w) \ {v}. The
edge (w, Bv (w)) is a candidate edge for the second edge of p. (2) v picks a neighbor
A(v) ∈ N(v) where A(v) ∼ π v . The random path p is p = hv, A(v), Bv (A(v))i, and it is
uniformly distributed over P2 (v).
In the algorithm, vertex v reports a path to each neighbor. We denote by pu (v)
the path in P2 (v) that v reports to u ∈ N(v). This is done by independently picking
neighbors Au (v) ∈ N(v), where each Au (v) ∼ π v . Hence, the path that v reports to u is
pu (v) , hv, Au (v), Bv (Au (v))i Algorithm 2 uses this process for reporting paths of length
2. Interestingly, these paths are not independent, however for the case of edge disjoint
copies of C4 , their “usefulness” in detecting copies of C4 turns out to be independent (see
Lemma 7).
Detecting a Cycle. Consider a copy C = (v, w, x, u) of C4 in G. If the 2-path pu (v)
that v reports to u is pu (v) = (v, w, x), then u can check whether the last vertex x in
pu (v) is also in N(u). If x ∈ N(u), then the copy C in G of C4 is detected. (The vertex
u also needs to verify that w 6= u.)
Description of the Algorithm. The ε-tester for C4 -freeness is listed as Algorithm 2.
In the first round, each vertex v learns its neighborhood N(v) and the degree of each
neighbor. The for-loop repeats t = O(1/ε) times. Each iteration consists of three rounds.
8

In the first round, v independently draws fresh values for Au (v) and Bu (v) for each of
its neighbors u ∈ N(v), and sends Bu (v) to u. In the second round, for each neighbor
u ∈ N(v), v sends the path hv, Au (v), Bv (Au (v))i. In the third round, v checks if it
received a path hw, a, bi for a neighbor w ∈ N(v) where a 6= v and b ∈ N(v). If this
occurs, then (v, w, a, b) is a copy of C4 , and vertex v rejects. If v did not reject in all the
iterations, then it finally accepts.
Analysis of the Algorithm.
Definition 5. We say that pu (v) is a success (wrt C = (v, w, x, u)) if pu (v) = (v, w, x).
Let Iv,u denote the indicator variable of the event that pu (v) is a success.
Lemma 7. Let {C j (vj , wj , xj , uj )}j∈J denote a set of edge-disjoint copies of C4 in G.
Then the random variables Ivj ,uj are independent.
Proof. The event Iv,u = 1 occurs iff Au (v) = w and Bv (w) = x. Both Au (v) and Bv (w) are
random variables assigned to (directed) edges. By construction, all the random variables
{Au (v)}(u,v∈E ∪ {Bv (w)}(v,w)∈E are independent. Since the cycles are edge-disjoint, the
lemma follows.
Claim 8. Pr[Iv,u = 1 | C] ≥ 1/(2m).
Proof. The path pu (v) equals (v, w, x) iff Au (v) = w and Bv (w) = x. As Au (v) and Bv (w)
are independent, we obtain
Pr [Iv,u = 1 | C] = Pr [Au (v) = w|C] · Pr [Bv (w) = x | C]
1
d(w) − 1
1
≥
.
=P
·
2m
x∈N (v) (d(x) − 1) d(w) − 1
Claim 9. If a graph G is ε-far from being C4 -free, then it contains at least ε · m/4
edge-disjoint copies of C4 .
Proof. Consider the following procedure for “covering” all the copies of C4 : while the
graph contains a copy of C4 , delete all four edges of the copy. When the procedure ends,
the remaining graph is C4 -free, hence at least εm edges were removed. The set of deleted
copies of C4 is edge disjoint and hence contains at least εm/4 copies of C4 .
Theorem 10. Algorithm 2 is an ε-tester for C4 -freeness. The round complexity of the
algorithm is Θ(1/ε) and in each round no more than O(log n) bits are communicated
along each edge.
Proof. Completeness: If G is C4 -free then Line 7 is never satisfied, hence for every v
Algorithm 2 terminates at Line 8.
Soundness: Let G = (V, E) be a graph which is ε-far from being C4 -free. Therefore,
there exist ℓ , εm/4 edge disjoint copies of C4 in G. Denote these copies by {C 1 , . . . , C ℓ },
where C j = (vj , wj , wj , uj ). In each iteration, the cycle C j is detected if Ivj ,uj = 1, which
(by Claim 8) occurs with probability at least 1/(2m). The cycles {C j }j are edge-disjoint,
hence, by Lemma 7, the probability that none of these cycles is detected is at most
(1 − 1/(2m))ℓ . The iterations are independent, and hence the probability that all the
iterations fail to detect one of these cycles is at most (1 − 1/(2m))ℓ·t. Since ℓ = εm/4,
setting t = 16/ε reduces the probability of false accept to at most 1/3, as required.
9

Algorithm 2: C4 -free-test(v)

7

Send v and d(v) to all u ∈ N (v)
// v learns N (v) and d(u) for every u ∈ N (v)
v
Define the following distribution π over N (v): For every w ∈ N (v),
P
π v (w) , d(w)/ x∈N (v) d(x) .
for t , (16/ε) times do
For every neighbor u ∈ N (v) independently draw Au (v) ∼ π v and
Bu (v) ∼ U (N (v) \ {u}, send Bu (v) to u.
For every neighbor u ∈ N (v) send the path hv, Au (v), Bv (Au (v))i to u.
if ∃w ∈ N (v) s.t. v received the path hw, a, bi from w, where v 6= a and b ∈ N (v)
then
return REJECT
// A cycle C = (v, w, a, b) was found.

8

return ACCEPT

1
2

3
4

5
6

Extending Algorithm 2. The algorithm can be easily extended to test H-freeness
for any connected H over four nodes. If H is a K1,3 then clearly H-freeness can be
tested in one round. Otherwise, H is Hamiltonian and can be tested by simply sending
an additional bit in the message sent in Line 5 of the algorithm. The additional bit
indicates whether v is connected to Bv (Au (v)). Given this information, u can determine
the subgraph induced on {u, v, Au(v), Bv (Au (v))}, and hence rejects if H is a subgraph
of this induced subgraph. Therefore we obtain the following theorem.
Theorem 11. There is an algorithm which is an ε-tester for H-freeness for any connected
H over 4 vertices. The round complexity of the algorithm is Θ(1/ε) and in each round
no more than O(log n) bits are communicated along each edge.

5

Testing T -freeness for any tree T

In this section we first generalize the tester by Iwama and Yoshida [IY14] of testing kpath freeness to testing the exclusion of any tree, T , of order k. Our tester has a one
sided error and it works in the general graph model with random edge queries. We, then,
2
show how to simulate this algorithm in the CONGEST- model in O(k k +1 · ε−k ) rounds.
We assume that the vertices of T are labeled by v0 , . . . , vk−1 .

5.1

Global Algorithm Description and Analysis

Global Algorithm Description. The algorithm by Iwama and Yoshida [IY14] for
testing k-path freeness proceeds as follows. An edge is picked u.a.r. and an endpoint, v,
of the selected edge,is picked u.a.r. A random walk of length k is performed from v, if a
simple path of length k is found then the algorithm rejects. The analysis in [IY14] shows
that this process has a constant probability (depends only on k and ε) to find a k-path
in an ε-far from k-path freeness graph.
We generalize this tester in the following straightforward manner. We pick a random
vertex v as in the above-mentioned algorithm. The vertex v is a candidate for being the
root of a copy of T . For the sake of brevity we denote the (possible) root of the copy
of T also by v0 . From v we start a “DFS-like” revealing of a tree which is a possible
10

copy of T with the first random vertex acting as its root. DFS-like means that we scan
a subgraph of G starting from v as follows: the algorithm independently and randomly
selects dT (v0 ) neighbors (out of the possible dG (v)) and recursively scans the graph from
each of these randomly chosen neighbors. While scanning, if we encounter any vertex
more than once then we abort the process (we did not find a copy of T ). If the process
terminates, then this implies that the algorithm found a copy of T . In order to obtain
probability of success of 2/3 the above process is repeated t = f (ε, k) times. The listing
of this algorithm appears in Algorithm 3.
Algorithm 3: Global-tree-free-test(T, v)
2

4

for t , Θ(kk /εk ) times do
Pick an edge u.a.r. and an endpoint, v, of the selected edge u.a.r.
Initialize all the vertices in G to be un-labeled.
Call Recursive-tree-exclusion(T, 0, v) and return REJECT if it returned 1.

5

return ACCEPT .

1
2
3

Procedure Recursive-tree-exclusion(T, i, v)
1 If v was already labeled then return 0, otherwise, label v by i. // The recursion
returns 0 if the revealed labeled subgraph is not T .
2 Define ℓ = dT (vi ) − 1 if i > 0 and ℓ = dT (vi ) otherwise.
3 Let vi1 , . . . , viℓ denote the labels of the children of vi in T (in which v0 is the root).
4 Pick u.a.r. ℓ vertices u1 , . . . , uℓ from NG (v) and recursively call
Recursive-tree-exclusion(T, ij , uj ) for each j ∈ [ℓ]
5 If one of the calls returned 0, then return 0, otherwise return 1.

Global Algorithm Analysis.
Theorem 12. Algorithm 3 is a 
global ε-tester,
 one-sided error for T -freenes. The query
k 2 +1
−k
. The algorithm works in the general graph
complexity of the algorithm is O k
·ε
model augmented with random edge samples.
Proof. We closely follow the analysis approach by Iwama and Yoshida [IY14]. If the input
graph G does not contain a copy of T then the ε-tester will not “find” any copy, and will
return ACCEPT.
Let G be ε-far from being T -free. This implies that there are at least ℓ = εm/(k − 1)
edge disjoint copies of T (otherwise contradicting the assumption that G is ε-far being T free). Let α = {T1 , . . . Tℓ } denote such set of edge disjoint copies of T . Note that two trees
in α might intersect in one of their vertices. Recall that T is labeled by v0 , . . . , vk−1. For
the sake of the analysis we consider a labeling of the vertices of G where each vertex has
a label in {vj | j ∈ [k − 1]}. We say that a copy of T in α is labeled correctly if the labeled
T and its labeled copy are the same (note that this is a more restrictive requirement then
asking for an isomorphic mapping between the two objects). We consider a subset of α
which are the copies of T which are labeled correctly, which we denote by αc . Note that
11

from linearity of expectation there exists a labeling such that the size of αc is at least
εm/ (k − 1) · k k - we fix our labeling to this one. Define β , ε/ (k − 1) · k k .
We now “sparsify” our set of trees even more. We proceed in iterations, initially
α0c = αc and define γ , β/4. We continue to the i-th iteration as long as there exists a
c
c
vertex, yi , in αi−1
such that the number of copies of T in αi−1
that yi belongs to, is less
c
c
c
than γ · dG (y). In this case we obtain αi from αi−1 by removing from αi−1
all the trees
that contain yi . Note that this results in a deletion of at most 2γ · |E(G)| copies of T
from αc , as each vertex gets removed at most once. Therefore, at the last iteration, we
obtain in this way the set α∗ which contains at least (β/2) · m, edge-disjoint, correctly
colored, copies of T .
We now focus on the copies of T in α∗ . Fix an iteration of Algorithm 3, and consider
the event that on Line 2, the starting vertex, v, is a vertex in α∗ which is labeled by v0 .
The probability that this event occurs is at least β/4. This follows from the fact that
there are at least (β/2) · m edges in α∗ in which one of their endpoints is labeled by v0 .
Conditioned on this event, the probability that u1 , . . . , uℓ , that are chosen in Line 4 of
Procedure Recursive-tree-exclusion, are in α∗ and their labels are vi1 , . . . , viℓ , respectively,
is at least γ ℓ . Therefore, by an inductive argument, the probability that the algorithm
2
finds T is at least (β/4) · γ k−1 = Ω(εk /(k k )), for each iteration. Since the number of
2
iterations is Θ(k k /εk ), the algorithm rejects G with probability at least 2/3.

5.2

Simulating the Global tester in the CONGEST- model

In order to simulate the above global tester in the CONGEST-model, we first need to
show how to simulate a random choice of the initial vertex. Note, that in the distributed
setting we are interested in the case where |E(G)| ≥ |V (G)| − 1, hence in Line 4 of
Algorithm 3, one can simply pick a vertex uniformly at random.
Distributed CONGEST Simulation. The simulation proceeds in three stages, as follows.
Random ranking assignment. First, each vertex v picks a random rank (independently), denoted by r(v), to be a uniform random number in [n2 ].
Labeling “competition” phase. Let us call the vertex v0 the vertex at level 1, its children
the vertices at level 2 and so on. Now, at the first round: each vertex label itself as v0 ,
picks random neighbors as in Line 4 of Algorithm 3 and sends to each selected vertex its
respective label. At the next round, each vertex v picks the label that was assigned to
it by the vertex with the highest rank, which we refer to as the root. If v’s label is of
level 2 then it continues by simulating Procedure Recursive-tree-exclusion. Specifically, it
selects random neighbors and their respective labels and send to each selected neighbor a
message with the respective label and the rank of its root. And so this process continues
for k rounds.
Labeling verification phase. Now, one needs to report to each root if it succeeded in
finding T . This can be achieved in additional k rounds: in rounds i all the vertices that
were assigned with label from level i send their parent in the revealed tree, whether they
succeeded or not, that is, a leaf reports on success if it was not labeled more than once by
the respective root, and an internal node reports on success if all its children report on
success and if it was not labeled more than once by the respective root. The correctness

12

of the simulations follows from the fact that the messages that are originated from the
vertex with the highest rank always get prioritizes and thus Algorithm 3 is simulated.
Theorem 13. There is an ε-tester in the CONGEST-model that on input T , where T
is a tree, the 
tester tests if the graph is T -free. The rounds complexity of the tester is
k 2 +1
−k
O k
·ε
where k is the order of T .

References
[ABCP92]

Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Lowdiameter graph decomposition is in nc. In Scandinavian Workshop on Algorithm Theory, pages 83–93. Springer, 1992.

[BGK+ 14]

Guy E Blelloch, Anupam Gupta, Ioannis Koutis, Gary L Miller, Richard
Peng, and Kanat Tangwongsan. Nearly-linear work parallel sdd solvers, lowdiameter decomposition, and low-stretch subgraphs. Theory of Computing
Systems, 55(3):521–554, 2014.

[CGR13]

Andrea Campagna, Alan Guo, and Ronitt Rubinfeld. Local reconstructors
and tolerant testers for connectivity and diameter. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings,
pages 411–424, 2013.

[CHFSV16] Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. In International Symposium on Distributed Computing, pages 43–56. Springer, 2016.
[EN17]

Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very
sparse spanners and emulators. In Proceedings of the Twenty-Eighth Annual
ACM-SIAM Symposium on Discrete Algorithms, pages 652–669. SIAM, 2017.

[FRST16]

Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca. Distributed
testing of excluded subgraphs. In International Symposium on Distributed
Computing, pages 342–356. Springer, 2016.

[GGR98]

Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its
connection to learning and approximation. Journal of the ACM (JACM),
45(4):653–750, 1998.

[GR02]

Oded Goldreich and Dana Ron. Property testing in bounded degree graphs.
Algorithmica, 32:302–343, 2002.

[IY14]

Kazuo Iwama and Yuichi Yoshida. Parameterized testability. In Innovations
in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January
12-14, 2014, pages 507–516, 2014.

[KPS13]

Satyen Kale, Yuval Peres, and C. Seshadhri. Noise tolerance of expanders
and sublinear expansion reconstruction. SIAM J. Comput., 42(1):305–323,
2013.
13

[MPX13]

Gary L Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In Proceedings of the twenty-fifth annual ACM
symposium on Parallelism in algorithms and architectures, pages 196–203.
ACM, 2013.

[Pel00]

David Peleg. Distributed computing: a locality-sensitive approach. SIAM,
2000.

14

