Three notes on distributed property testing

Abstract

In this paper we present distributed property-testing algorithms for graph properties in thecongestmodel, with emphasis on testing subgraph-freeness. Testing a graph propertyPmeansdistinguishing graphsG= (V,E)having propertyPfrom graphs that areε-far from having it,meaning thatε|E|edges must be added or removed fromGto obtain a graph satisfyingP.We present a series of results, including:TestingH-freeness inO(1/ε)rounds, for any constant-sized graphHcontaining an edge(u,v)such that any cycle inHcontain eitheruorv(or both). This includes all connected graphsover five vertices exceptK5. For triangles, we can do even better whenεis not too small.A deterministiccongestprotocol determining whether a graph contains a given tree as asubgraph in constant time.For cliquesKswiths≥5, we show thatKs-freeness can be tested inO(m12−1s−2·ε−12−1s−2)rounds, wheremis the number of edges in the network graph.We describe a general procedure for convertingε-testers withf(D)rounds, whereDdenotesthe diameter of the graph, to work inO((logn)/ε) +f((logn)/ε)rounds, wherenis thenumber of processors of the network. We then apply this procedure to obtain anε-tester fortesting whether a graph is bipartite and testing whether a graph is cycle-free. Moreover, forcycle-freeness, we obtain acorrectorof the graph that locally corrects the graph so that thecorrected graph is acyclic. Note that, unlike a tester, a corrector needs to mend the graph inmany 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 [Fraigniaudet al. 2016]