https://hal.inria.fr/hal-02433486Fraigniaud, PierrePierreFraigniaudIRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale - UPD7 - Université Paris Diderot - Paris 7 - CNRS - Centre National de la Recherche ScientifiqueGANG - Networks, Graphs and Algorithms - IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale - UPD7 - Université Paris Diderot - Paris 7 - CNRS - Centre National de la Recherche Scientifique - Inria de Paris - Inria - Institut National de Recherche en Informatique et en AutomatiqueOlivetti, DennisDennisOlivettiIRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale - UPD7 - Université Paris Diderot - Paris 7 - CNRS - Centre National de la Recherche ScientifiqueDistributed Detection of CyclesHAL CCSD2019Theory of computationDesign and analysis of algorithmsDistributed algorithmsGraph algorithms analysisTheory of computation[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]Fraigniaud, Pierre2020-01-09 10:37:562023-03-24 14:53:142020-01-09 10:37:56enJournal articles10.1145/33228111Distributed property testing in networks has been introduced by Brakerski and Patt-Shamir [6], with the objective of detecting the presence of large dense sub-networks in a distributed manner. Recently, Censor-Hillel et al. [7] have revisited this notion and formalized it in a broader context. In particular, they 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. [21] 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 article, 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.