Finding Planted Cycles in a Random Graph

ABSTRACT 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.]