EUVIMEDEUVIMED entdecken
Crossref

Finding Planted Cycles in a Random Graph

Julia Gaudio, Colin Sandon, Jiaming Xu, Dana Yang

Random Structures & Algorithms · 2026-05 · 68 (3)

DOI: 10.1002/rsa.70062 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 10.04.2026. Verfasst von Julia Gaudio und 3 weiteren Autor:innen. Die Arbeit nennt 26 Literaturangaben. Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper, we study the problem of finding a collection of planted cycles in an Erdös‐Rényi random graph , in analogy to the famous Planted Clique Problem. When the cycles are planted on a uniformly random subset of vertices, we show that almost‐exact recovery (i.e., recovering all but a vanishing fraction of planted‐cycle edges as ) is information‐theoretically possible if and impossible if . Moreover, despite the worst‐case computational hardness of finding long cycles, we design a polynomial‐time algorithm that attains almost exact recovery when . This stands in stark contrast to the Planted Clique Problem, where a significant computational‐statistical gap is widely conjectured. [A key technical contribution is a novel generating‐function approach for counting imbalanced circuits that arise in decompositions of the symmetric difference between the planted cycles and alternative feasible solutions.]

Förderung

  • National Science Foundation

Zitieren

APA

Gaudio, J., Sandon, C., Xu, J., & Yang, D. (2026). Finding Planted Cycles in a Random Graph. Random Structures & Algorithms, 68(3). https://doi.org/10.1002/rsa.70062

Vancouver

Gaudio J, Sandon C, Xu J, Yang D. Finding Planted Cycles in a Random Graph. Random Structures & Algorithms. 2026;68(3). doi:10.1002/rsa.70062

BibTeX
@article{Gaudio2026,
  author = {Gaudio, Julia and Sandon, Colin and Xu, Jiaming and Yang, Dana},
  title = {Finding Planted Cycles in a Random Graph},
  journal = {Random Structures & Algorithms},
  year = {2026},
  volume = {68},
  number = {3},
  doi = {10.1002/rsa.70062}
}
Kostenlos starten →