DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.80

Deterministic Even-Cycle Detection in Broadcast CONGEST

Authors: Pierre Fraigniaud, Maël Luce, Frédéric Magniez, and Ioan Todinca

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

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.

Cite as

Pierre Fraigniaud, Maël Luce, Frédéric Magniez, and Ioan Todinca. Deterministic Even-Cycle Detection in Broadcast CONGEST. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 80:1-80:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.ICALP.2025.80,
  author =	{Fraigniaud, Pierre and Luce, Ma\"{e}l and Magniez, Fr\'{e}d\'{e}ric and Todinca, Ioan},
  title =	{{Deterministic Even-Cycle Detection in Broadcast CONGEST}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{80:1--80:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.80},
  URN =		{urn:nbn:de:0030-drops-234573},
  doi =		{10.4230/LIPIcs.ICALP.2025.80},
  annote =	{Keywords: local computing, CONGEST model}
}

Search Results

Documents authored by Luce, Maël

Deterministic Even-Cycle Detection in Broadcast CONGEST

Abstract

Cite as

Thanks for your feedback!

Could not send message