Even-Cycle Detection in the Randomized and Quantum CONGEST Model

Pierre Fraigniaud, Mael Luce, Frederic Magniez +1

We show that, for every $k\ge 2$, $C_{2k}$-freeness can be decided in $O(n^{1-1/k})$ rounds in the \CONGEST{} model by a randomized Monte-Carlo distributed algorithm with one-side…