Even-Cycle Detection in the Randomized and Quantum CONGEST Model
Pierre Fraigniaud, Maël Luce, Frédéric Magniez, Ioan Todinca · 2024
We show that, for every k ≥ 2, C2k-freeness can be decided in O(n1--1/k) rounds in the CONGEST model by a randomized Monte-Carlo distributed algorithm with one-sided error probability 1/3. This matches the best round-complexities of previously known algorithms for k ∈ {2, 3, 4, 5} by Drucker et al. [PODC'14] and Censor-Hillel et al. [DISC'20], but improves the complexities of the known algorithms for k > 5 by Eden et al. [DISC'19], which were essentially of the form Õ (n1--2/k2). Our algorithm uses colored BFS-explorations with threshold, but with an original global approach that enables to overcome a recent impossibility result by Fraigniaud et al. [SIROCCO'23] about using colored BFS-exploration with local threshold for detecting cycles.