{"ID":2845177,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.04058","arxiv_id":"2511.04058","title":"Finding Planted Cycles in a Random Graph","abstract":"In this paper, we study the problem of finding a collection of planted cycles in an \\ER random graph $G \\sim \\mathcal{G}(n, λ/n)$, in analogy to the famous Planted Clique Problem. When the cycles are planted on a uniformly random subset of $δn$ vertices, we show that almost-exact recovery (that is, recovering all but a vanishing fraction of planted-cycle edges as $n \\to \\infty$) is information-theoretically possible if $λ\u003c \\frac{1}{(\\sqrt{2 δ} + \\sqrt{1-δ})^2}$ and impossible if $λ\u003e \\frac{1}{(\\sqrt{2 δ} + \\sqrt{1-δ})^2}$. Moreover, despite the worst-case computational hardness of finding long cycles, we design a polynomial-time algorithm that attains almost exact recovery when $λ\u003c \\frac{1}{(\\sqrt{2 δ} + \\sqrt{1-δ})^2}$. This stands in stark contrast to the Planted Clique Problem, where a significant computational-statistical gap is widely conjectured.","short_abstract":"In this paper, we study the problem of finding a collection of planted cycles in an \\ER random graph $G \\sim \\mathcal{G}(n, λ/n)$, in analogy to the famous Planted Clique Problem. When the cycles are planted on a uniformly random subset of $δn$ vertices, we show that almost-exact recovery (that is, recovering all but a...","url_abs":"https://arxiv.org/abs/2511.04058","url_pdf":"https://arxiv.org/pdf/2511.04058v1","authors":"[\"Julia Gaudio\",\"Colin Sandon\",\"Jiaming Xu\",\"Dana Yang\"]","published":"2025-11-06T04:57:48Z","proceeding":"math.ST","tasks":"[\"math.ST\",\"math.PR\"]","methods":"[]","has_code":false}