Planted Clique in G(n,p), varying p In the planted clique problem, one must recover a $k$-clique planted in an Erdos-Renyi random graph $G(n,p)$. This has mostly been looked at for $p=\frac{1}{2}$, in which case it is known to be polynomial-time solvable if $k &gt; \sqrt{n}$ and conjectured hard for $k&lt; \sqrt{n}$. 

My question is: what is known/believed about other values of $p$? Specifically, when $p$ is a constant in $[0,1]$? Is there evidence that, for every such value of $p$, there exists some $k=n^{\alpha}$ for which the problem is computationally hard?

References would be particularly helpful, as I haven't succeeded in finding any literature which looks at the problem for values other than $p=\frac{1}{2}$.
If $p$ is constant, then the size of the maximum clique in the $G(n,p)$ model is almost everywhere a constant multiple of $\log n$, with the constant proportional to $\log (1/p)$.  (See Bollobás, p.283 and Corollary 11.2.)  Changing $p$ should therefore not affect the hardness of planting a clique with $\omega(\log n)$ vertices as long as the clique is too small for an existing algorithmic approach to work.  I therefore expect that with constant $p \ne 1/2$ the hardness of Planted Clique should behave just like the $p=1/2$ case, although it is possible that the case of $p$ very close to 0 or 1 might behave differently.

In particular, for $p\ne 1/2$ the same threshold of $\Omega(n^{\alpha})$ for $\alpha = 1/2$ for the size of the planted clique applies, above which the problem becomes polynomial-time.
The value of $\alpha$ here is $1/2$ (and not some other value) because the Lovász theta function of $G(n,p)$ is almost surely between $0.5\sqrt{(1-p)/p}\sqrt{n}$ and $2\sqrt{(1-p)/p}\sqrt{n}$, by a result of Juhász.
The algorithm of Feige and Krauthgamer uses the Lovász theta function to find and certify a largest clique, so it relies on this threshold size for the planted clique.

Of course, there may be a different algorithm that does not use the Lovász theta function, and that for values of $p$ far from $1/2$ can find a planted clique with say $n^{1/3}$ vertices.  As far as I can tell this is still open.

Feige and Krauthgamer also discuss when $p$ is not constant but depends on $n$, and is either close to 0 or close to 1.  In these cases other approaches exist to find planted cliques, and the threshold size is different.


Béla Bollobás, Random Graphs (2nd edition), Cambridge University Press, 2001.
Ferenc Juhász, The asymptotic behaviour of Lovász' $\vartheta$ function for random graphs, Combinatorica 2(2) 153–155, 1982.  doi:10.1007/BF02579314
Uriel Feige and Robert Krauthgamer, Finding and certifying a large hidden clique in a semirandom graph, Random Structures &amp; Algorithms 16(2) 195–208, 2000.  doi:10.1002/(SICI)1098-2418(200003)16:2&lt;195::AID-RSA5>3.0.CO;2-A