.png){kind=icon}
.png){kind=icon}
Return
Finding Planted Cycles in a Random Graph
.png){kind=icon}
PRE
AI
DOI：10.1002/rsa.70062.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we study the problem of finding a collection of planted cycles in an Erd & ouml;s-R & eacute;nyi random graph G similar to & Gscr; ( n , lambda / n ) , 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.]
Keywords:
branching processes
generating functions
phase transitions
planted cycles
random graphs
Journal
R
IF:
0
Papers:
29
Citations:
0
View more organizations