Planted Clique in G(n,p), varying p

Question

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 > \sqrt{n}$ and conjectured hard for $k< \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}$.

Answer 1

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 & Algorithms 16(2) 195–208, 2000. doi:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A

Answer 2

planted clique for $p \neq \frac{1}{2}$ is a special case of this problem and new results (lower bounds) as stated on p2 etc & it includes related refs. (2015)

We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all $k$-subgraphs have density at most $1 −\varepsilon$, requires $n^{\tilde{\Omega}(\log n)}$ time.

• ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness / Braverman, Ko, Rubinstein, Weinstein

Answer 3

heres a new paper that has an algorithm for arbitrary p≠½ based on an SVD algorithm. see p.4 for analysis of hidden (planted) clique.

A SIMPLE SVD ALGORITHM FOR FINDING HIDDEN PARTITIONS Van Vu

Abstract. Finding a hidden partition in a random environment is a general and important problem, which contains as subproblems many famous questions, such as finding a hidden clique, finding a hidden coloring, finding a hidden bipartition etc. In this paper, we provide a simple SVD algorithm for this purpose, answering a question of McSherry. This algorithm is very easy to implement and works for sparse graphs with optimal density.