Name
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 u003e= 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]. |
Year | Venue | Field |
|---|---|---|
2017 | DISC | Graph,Binary logarithm,Combinatorics,Property testing,Vertex (geometry),Graph property,Computer science,Bipartite graph,Distributed computing |
DocType | Citations | PageRank |
Conference | 2 | 0.37 |
References | Authors | |
0 | 11 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guy Even | 1 | 1194 | 136.90 |
| Orr Fischer | 2 | 30 | 4.97 |
| Pierre Fraigniaud | 3 | 2849 | 220.78 |
| Tzlil Gonen | 4 | 3 | 1.41 |
| Reut Levi | 5 | 81 | 10.54 |
| Moti Medina | 6 | 106 | 14.42 |
| Pedro Montealegre | 7 | 28 | 11.47 |
| Dennis Olivetti | 8 | 31 | 10.51 |
| Rotem Oshman | 9 | 456 | 22.52 |
| Ivan Rapaport | 10 | 2 | 1.72 |
| Ioan Todinca | 11 | 328 | 27.33 |