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,\hat{I}»/n)$, in analogy to the famous Planted Clique Problem. When the cycles are planted on a uniformly random subset of $\hat{I}´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 $\hat{I}»<\frac{1}{(\sqrt{2\hat{I}´}+\sqrt{1-\hat{I}´}{)}^2}$ and impossible if $\hat{I}»>\frac{1}{(\sqrt{2\hat{I}´}+\sqrt{1-\hat{I}´}{)}^2}$. Moreover, despite the worst-case computational hardness of finding long cycles, we design a polynomial-time algorithm that attains almost exact recovery when $\hat{I}»<\frac{1}{(\sqrt{2\hat{I}´}+\sqrt{1-\hat{I}´}{)}^2}$. This stands in stark contrast to the Planted Clique Problem, where a significant computational-statistical gap is widely conjectured.