License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.15
URN: urn:nbn:de:0030-drops-79847
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7984/
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 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 epsilon-far from having it, meaning that epsilon|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/epsilon) 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 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_s-freeness can be tested in O(m^(1/2-1/(s-2)) epsilon^(-1/2-1/(s-2))) rounds, where m is the number of edges in the network graph.
- We describe a general procedure for converting epsilon-testers 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 epsilon-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].
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:1--15:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-053-8},
ISSN = {1868-8969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7984},
URN = {urn:nbn:de:0030-drops-79847},
doi = {10.4230/LIPIcs.DISC.2017.15},
annote = {Keywords: Property testing, Property correcting, Distributed algorithms, CONGEST model}
}
|
Keywords: |
|
Property testing, Property correcting, Distributed algorithms, CONGEST model |
|
Collection: |
|
31st International Symposium on Distributed Computing (DISC 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
12.10.2017 |
