Distributed testing of excluded subgraphs

DOI10.1007/978-3-662-53426-7_25MaRDI QIDQ1660944zbMATH OpenOpenAlexFDO

Authors Pierre Fraigniaud, Ivan Rapaport, Ioan Todinca, Ville Salo

Publication date 16 August 2018

Full work available at URL https://arxiv.org/abs/1605.03719

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Abstract: We study property testing in the context of distributed computing, under the classical CONGEST model. It is known that testing whether a graph is triangle-free can be done in a constant number of rounds, where the constant depends on how far the input graph is from being triangle-free. We show that, for every connected 4-node graph H, testing whether a graph is H-free can be done in a constant number of rounds too. The constant also depends on how far the input graph is from being H-free, and the dependence is identical to the one in the case of testing triangles. Hence, in particular, testing whether a graph is K_4-free, and testing whether a graph is C_4-free can be done in a constant number of rounds (where K_k denotes the k-node clique, and C_k denotes the k-node cycle). On the other hand, we show that testing K_k-freeness and C_k-freeness for k>4 appear to be much harder. Specifically, we investigate two natural types of generic algorithms for testing H-freeness, called DFS tester and BFS tester. The latter captures the previously known algorithm to test the presence of triangles, while the former captures our generic algorithm to test the presence of a 4-node graph pattern H. We prove that both DFS and BFS testers fail to test K_k-freeness and C_k-freeness in a constant number of rounds for k>4.

Recommendations

• Three notes on distributed property testing
• Property testing of planarity in the \textsf{CONGEST} model
• Property testing of planarity in the \textsf{CONGEST} model

Cited in

(11)

• Fooling views: a new lower bound technique for distributed computations under congestion
• Distributed Testing of Distance-k Colorings
• Distributed detection of cliques in dynamic networks
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• A two-sided error distributed property tester for conductance
• Deterministic subgraph detection in broadcast CONGEST
• Property testing of planarity in the \textsf{CONGEST} model
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Deterministic near-optimal distributed listing of cliques
• Distributedly testing cycle-freeness
• Three notes on distributed property testing

This page was built for publication: Distributed testing of excluded subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1660944)