Three notes on distributed property testing

Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, Ioan Todinca

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

23 Scopus citations

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 ϵ-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].

Original languageEnglish
Title of host publication31st International Symposium on Distributed Computing, DISC 2017
EditorsAndrea W. Richa
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770538
DOIs
StatePublished - 1 Oct 2017
Event31st International Symposium on Distributed Computing, DISC 2017 - Vienna, Austria
Duration: 16 Oct 201720 Oct 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume91
ISSN (Print)1868-8969

Conference

Conference31st International Symposium on Distributed Computing, DISC 2017
Country/TerritoryAustria
CityVienna
Period16/10/1720/10/17

Keywords

  • CONGEST model
  • Distributed algorithms
  • Property correcting
  • Property testing

Fingerprint

Dive into the research topics of 'Three notes on distributed property testing'. Together they form a unique fingerprint.

Cite this