Distributed Testing of Excluded Subgraphs

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 triangle-freeness. Hence, in particular, testing whether a graph is K4-free, and testing whether a graph is C4-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 ≥ 5 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 ≥ 5.
Type de document :
Communication dans un congrès
Cyril Gavoille; David Ilcinkas 30th International Symposium on Distributed Computing (DISC 2016), Sep 2016, Paris, France. Springer, LNCS 9888, pp.342 - 356, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-662-53426-7_25〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01423633
Contributeur : Pierre Fraigniaud <>
Soumis le : vendredi 30 décembre 2016 - 17:41:18
Dernière modification le : jeudi 13 décembre 2018 - 15:26:38
Document(s) archivé(s) le : lundi 20 mars 2017 - 16:44:55

Fichier

camera-DISC2016.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre Fraigniaud, Ivan Rapaport, Ville Salo, Ioan Todinca. Distributed Testing of Excluded Subgraphs. Cyril Gavoille; David Ilcinkas 30th International Symposium on Distributed Computing (DISC 2016), Sep 2016, Paris, France. Springer, LNCS 9888, pp.342 - 356, 2016, Lecture Notes in Computer Science. 〈10.1007/978-3-662-53426-7_25〉. 〈hal-01423633〉

Partager

Métriques

Consultations de la notice

386

Téléchargements de fichiers

39