Even, Guy ;
Fischer, Orr ;
Fraigniaud, Pierre ;
Gonen, Tzlil ;
Levi, Reut ;
Medina, Moti ;
Montealegre, Pedro ;
Olivetti, Dennis ;
Oshman, Rotem ;
Rapaport, Ivan ;
Todinca, Ioan
Three Notes on Distributed Property Testing
Abstract
In this paper we present distributed propertytesting algorithms for graph properties in the CONGEST model, with emphasis on testing subgraphfreeness. Testing a graph property P means distinguishing graphs G = (V,E) having property P from graphs that are epsilonfar from having it, meaning that epsilonE edges must be added or removed from G to obtain a graph satisfying P.
We present a series of results, including:
 Testing Hfreeness in O(1/epsilon) rounds, for any constantsized 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 K_5. For triangles, we can do even better when epsilon is not too small.
 A deterministic CONGEST protocol determining whether a graph contains a given tree as a subgraph in constant time.
 For cliques K_s with s >= 5, we show that K_sfreeness can be tested in O(m^(1/21/(s2)) epsilon^(1/21/(s2))) rounds, where m is the number of edges in the network graph.
 We describe a general procedure for converting epsilontesters with f(D) rounds, where D denotes the diameter of the graph, to work in O((log n)/epsilon)+f((log n)/epsilon) rounds, where n is the number of processors of the network. We then apply this procedure to obtain an epsilontester for testing whether a graph is bipartite and testing whether a graph is cyclefree. Moreover, for cyclefreeness, 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 [CensorHillel et al. 2016] and [Fraigniaud et al. 2016].
BibTeX  Entry
@InProceedings{even_et_al:LIPIcs:2017:7984,
author = {Guy Even and Orr Fischer and Pierre Fraigniaud and Tzlil Gonen and Reut Levi and Moti Medina and Pedro Montealegre and Dennis Olivetti and Rotem Oshman and Ivan Rapaport and Ioan Todinca},
title = {{Three Notes on Distributed Property Testing}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {15:115:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770538},
ISSN = {18688969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7984},
URN = {urn:nbn:de:0030drops79847},
doi = {10.4230/LIPIcs.DISC.2017.15},
annote = {Keywords: Property testing, Property correcting, Distributed algorithms, CONGEST model}
}
2017
Keywords: 

Property testing, Property correcting, Distributed algorithms, CONGEST model 
Seminar: 

31st International Symposium on Distributed Computing (DISC 2017)

Issue date: 

2017 
Date of publication: 

2017 