2024/12/15 by Fraigniaud, Pierre, Luce, Maël, Magniez, Frédéric +1
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2412.11195
We show that, for every k≥ 2, C2k-freeness can be decided in O(n1-1/k) rounds in the Broadcast CONGEST model, by a deterministic algorithm. This (deterministic) round-complexity is optimal for k=2 up to logarithmic factors thanks to the lower bound for C4-freeness by Drucker et al. [PODC 2014], which holds even for randomized algorithms. Moreover it matches the round-complexity of the best known randomized algorithms by Censor-Hillel et al. [DISC 2020] for k∈\3,4,5\, and by Fraigniaud et al. [PODC 2024] for k≥ 6. Our algorithm uses parallel BFS-explorations with deterministic selections of the set of paths that are forwarded at each round, in a way similar to what was done for the detection of odd-length cycles, by Korhonen and Rybicki [OPODIS 2017]. However, the key element in the design and analysis of our algorithm is a new combinatorial result bounding the "local density" of graphs without 2k-cycles, which we believe is interesting on its own.