Distributed Detection of Cycles

Pierre Fraigniaud 1, 2 Olivetti Dennis 2, 1
1 GANG - Networks, Graphs and Algorithms
IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale, Inria de Paris
Abstract : Distributed property testing in networks has been introduced by Brakerski and Patt-Shamir (2011), with the objective of detecting the presence of large dense sub-networks in a distributed manner. Recently, Censor-Hillel et al. (2016) have shown how to detect 3-cycles in a constant number of rounds by a distributed algorithm. In a follow up work, Fraigniaud et al. (2016) have shown how to detect 4-cycles in a constant number of rounds as well. However, the techniques in these latter works were shown not to generalize to larger cycles Ck with k ≥ 5. In this paper, we completely settle the problem of cycle detection, by establishing the following result. For every k ≥ 3, there exists a distributed property testing algorithm for Ck-freeness, performing in a constant number of rounds. All these results hold in the classical congest/ model for distributed network computing. Our algorithm is 1-sided error. Its round-complexity is O(1/ε) where ε ∈(0,1) is the property testing parameter measuring the gap between legal and illegal instances.
Complete list of metadatas

https://hal.inria.fr/hal-01674646
Contributor : Pierre Fraigniaud <>
Submitted on : Wednesday, January 3, 2018 - 12:07:50 PM
Last modification on : Friday, December 13, 2019 - 11:18:02 AM

Links full text

Identifiers

Collections

Citation

Pierre Fraigniaud, Olivetti Dennis. Distributed Detection of Cycles. SPAA 2017 - 29th ACM Symposium on Parallelism in Algorithms and Architectures, Jul 2017, Washington, United States. pp.153-162, ⟨10.1145/3087556.3087571⟩. ⟨hal-01674646⟩

Share

Metrics

Record views

121