Distributedly Testing Cycle-Freeness

Heger Arfaoui (1) , Pierre Fraigniaud (2, 1) , David Ilcinkas (3) , Fabien Mathieu (4, 5)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 GANG - Networks, Graphs and Algorithms
3 LaBRI - Laboratoire Bordelais de Recherche en Informatique
4 LINCS - Laboratory of Information, Network and Communication Sciences
5 Alcatel Lucent Bell Labs

We tackle \emph{local distributed testing} of graph properties. This framework is well suited to contexts in which data dispersed among the nodes of a network can be collected by some central authority (like in, e.g., sensor networks). In local distributed testing, each node can provide the central authority with just a few information about what it perceives from its neighboring environment, and, based on the collected information, the central authority is aiming at deciding whether or not the network satisfies some property. We analyze in depth the prominent example of checking \emph{cycle-freeness}, and establish tight bounds on the amount of information to be transferred by each node to the central authority for deciding cycle-freeness. In particular, we show that distributedly testing cycle-freeness requires at least $\lceil{\log d}\rceil-1$ bits of information per node in graphs with maximum degree~$d$, even for connected graphs. Our proof is based on a novel version of the seminal result by Naor and Stockmeyer (1995) enabling to reduce the study of certain kinds of algorithms to order-invariant algorithms, and on an appropriate use of the known fact that every free group can be linearly ordered.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]; Complexité [cs.CC]

Heger Arfaoui, Pierre Fraigniaud, David Ilcinkas, Fabien Mathieu. Distributedly Testing Cycle-Freeness. Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2014, Nouan-le-Fuzelier, France. pp.15 - 28, ⟨10.1007/978-3-319-12340-0_2⟩. ⟨hal-01084297⟩