Planted clique

There exists a function ${\displaystyle f(n)\sim 2\log _{2}n}$ such that asymptotically almost surely, the size of the largest clique in an n-vertex random graph is either ${\displaystyle f(n)}$ or ${\displaystyle f(n)+1}$,[2] and there exists some constant ${\displaystyle c}$ such that the expected number of cliques of size ${\displaystyle \geq f(n)-c}$ converges to infinity. Consequently, one should expect that the planting a clique of size ${\displaystyle \sim 2\log _{2}n}$ cannot be detected with high probability.

By the central limit theorem, the vertex degrees of the random graph would be distributed close to a standard normal distribution with mean ${\displaystyle {\frac {n}{2}}}$ and standard deviation ${\displaystyle {\frac {\sqrt {n}}{2}}}$. Consequently, when ${\displaystyle k}$ is on the order of ${\displaystyle {\sqrt {n}}}$ it would create a detectable change in the shape of the distribution. Namely, if you plot out the vertex degree distribution, it would look like a deformed bell curve. Therefore, the most interesting range of values for the parameter k is between these two values,[1]

${\displaystyle 2\log _{2}n\ll k\ll {\sqrt {n}}.}$

For sufficiently large values of the parameter k, the planted clique problem can be solved (with high probability) in polynomial time.[1]

Kučera (1995) observes that, when ${\displaystyle k=\Omega ({\sqrt {n\log n}})}$ then almost surely all vertices of the planted clique have higher degree than all vertices outside the clique, making the clique very easy to find. He describes a modification to the random process for generating planted clique instances, that makes the vertex degrees more uniform even for large values of k, but shows that despite this modification the planted clique may still be found quickly.[3]

Alon, Krivelevich & Sudakov (1998) prove for ${\displaystyle k>10{\sqrt {n}}}$ a planted clique can be found with high probability by the following method:

1. Compute the eigenvector of the adjacency matrix corresponding to its second highest eigenvalue.
2. Select the k vertices whose coordinates in this eigenvector have the largest absolute values.
3. Return the set of vertices that are adjacent to at least 3/4 of the selected vertices.

They show how to modify this technique so that it continues to work whenever k is at least proportional to some multiple of the square root of the number of vertices.[4] Large planted cliques can also be found using semidefinite programming.[5] A combinatorial technique based on randomly sampling vertices can achieve the same bound on k and runs in linear time.[6]

It is also possible to solve the planted clique problem, regardless of the choice of k, in quasi-polynomial time.[7] Because the largest clique in a random graph typically has size near 2 log₂ n,[8] a planted clique of size k (if it exists) can be found with high probability by the following method:

1. Loop through all sets S of ${\displaystyle \min(k,3\log _{2}n)}$ vertices.
2. For each choice of S, test whether S is a clique. If it is, and ${\displaystyle |S|=k}$, return S. Otherwise, find the set T of vertices that are adjacent to all vertices in S. If ${\displaystyle |T|\geq k}$, return T.

The running time of this algorithm is quasipolynomial, because there are quasipolynomially many choices of S to loop over. This method is guaranteed to try a set S that is a subset of the planted clique; with high probability, the set T will consist only of other members of the planted clique.