Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2511.04058 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- 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 $λ< \frac{1}{(\sqrt{2 δ} + \sqrt{1-δ})^2}$ and impossible if $λ> \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 $λ< \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.