Detection-Recovery Gap for Planted Dense Cycles

Planted dense cycles are a type of latent structure that appears in many applications, such as small-world networks in social sciences and sequence assembly in computational biology. We consider a model where a dense cycle with expected bandwidth $n\tau$ and edge density $p$ is planted in an Erdős-Rényi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree polynomial algorithms. In particular, a gap exists between the two thresholds in a certain regime of parameters. For example, if $n^{-3\mathrm{/}4}\ll \tau \ll n^{-1\mathrm{/}2}$ and $p=Cq=\mathrm{\Theta }(1)$ for a constant $C>1$, the detection problem is computationally easy while the recovery problem is hard for low-degree algorithms.