TY - GEN

T1 - Three notes on distributed property testing

AU - Even, Guy

AU - Fischer, Orr

AU - Fraigniaud, Pierre

AU - Gonen, Tzlil

AU - Levi, Reut

AU - Medina, Moti

AU - Montealegre, Pedro

AU - Olivetti, Dennis

AU - Oshman, Rotem

AU - Rapaport, Ivan

AU - Todinca, Ioan

N1 - Funding Information:
∗ Full versions related to the paper are available at https://arxiv.org/abs/1705.04898 and http: //arxiv.org/abs/1705.04033 [16, 17]. † Work done while visiting Max Planck Institute for Informatics. ‡ Additional support from ANR Project DESCARTES, and from INRIA Project GANG. § This work was partially supported by CONICYT via Basal in Applied Mathematics. ¶ Orr Fischer, Tzlil Gonen and Rotem Oshman are supported by the Israeli Centers of Research Excellence (I-CORE) program, (Center No. 4/11) and by BSF Grant No. 2014256. ‖ This work was partially supported by Fondecyt 1170021, Núcleo Milenio Información y Coordinación en Redes ICM/FIC RC130003.
Publisher Copyright:
© Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre.

PY - 2017/10/1

Y1 - 2017/10/1

N2 - In this paper we present distributed property-testing algorithms for graph properties in the congest model, with emphasis on testing subgraph-freeness. Testing a graph property P means distinguishing graphs G = (V, E) having property P from graphs that are ϵ-far from having it, meaning that ϵ|E| edges must be added or removed from G to obtain a graph satisfying P. We present a series of results, including: Testing H-freeness in O(1/ϵ) rounds, for any constant-sized graph H containing an edge (u, v) such that any cycle in H contain either u or v (or both). This includes all connected graphs over five vertices except K5. For triangles, we can do even better when ϵ is not too small. A deterministic congest protocol determining whether a graph contains a given tree as a subgraph in constant time. For cliques Ks with s 5, we show that Ks-freeness can be tested in O(m 1/2-1/s-2 · ϵ-1/2-1/s-2 ) rounds, where m is the number of edges in the network graph. We describe a general procedure for converting ϵ-testers with f(D) rounds, where D denotes the diameter of the graph, to work in 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 and testing whether a graph is cycle-free. 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. These protocols extend and improve previous results of [Censor-Hillel et al. 2016] and [Fraigniaud et al. 2016].

AB - In this paper we present distributed property-testing algorithms for graph properties in the congest model, with emphasis on testing subgraph-freeness. Testing a graph property P means distinguishing graphs G = (V, E) having property P from graphs that are ϵ-far from having it, meaning that ϵ|E| edges must be added or removed from G to obtain a graph satisfying P. We present a series of results, including: Testing H-freeness in O(1/ϵ) rounds, for any constant-sized graph H containing an edge (u, v) such that any cycle in H contain either u or v (or both). This includes all connected graphs over five vertices except K5. For triangles, we can do even better when ϵ is not too small. A deterministic congest protocol determining whether a graph contains a given tree as a subgraph in constant time. For cliques Ks with s 5, we show that Ks-freeness can be tested in O(m 1/2-1/s-2 · ϵ-1/2-1/s-2 ) rounds, where m is the number of edges in the network graph. We describe a general procedure for converting ϵ-testers with f(D) rounds, where D denotes the diameter of the graph, to work in 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 and testing whether a graph is cycle-free. 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. These protocols extend and improve previous results of [Censor-Hillel et al. 2016] and [Fraigniaud et al. 2016].

KW - CONGEST model

KW - Distributed algorithms

KW - Property correcting

KW - Property testing

UR - http://www.scopus.com/inward/record.url?scp=85032363165&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.DISC.2017.15

DO - 10.4230/LIPIcs.DISC.2017.15

M3 - Conference contribution

AN - SCOPUS:85032363165

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 31st International Symposium on Distributed Computing, DISC 2017

A2 - Richa, Andrea W.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 31st International Symposium on Distributed Computing, DISC 2017

Y2 - 16 October 2017 through 20 October 2017

ER -