2026-08-01T05:57:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23457 2025-10-02T12:55:41Z ddc:004 open_access

Deterministic Even-Cycle Detection in Broadcast CONGEST Fraigniaud, Pierre Luce, Maël Magniez, Frédéric Todinca, Ioan local computing CONGEST model We show that, for every k ≥ 2, C_{2k}-freeness can be decided in O(n^{1-(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 C₄-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Fraigniaud and Maël Luce and Frédéric Magniez and Ioan Todinca 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.80 urn:nbn:de:0030-drops-234573 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.80 eng https://creativecommons.org/licenses/by/4.0/legalcode