Planted clique


In computational complexity theory, a planted clique or hidden clique in an undirected graph is a clique formed from another graph by selecting a subset of vertices and adding edges between each pair of vertices in the subset. The planted clique problem is the algorithmic problem of distinguishing random graphs from graphs that have a planted clique. This is a variation of the clique problem; it may be solved in quasi-polynomial time but is conjectured not to be solvable in polynomial time for intermediate values of the clique size. The conjecture that no polynomial time solution exists is called the planted clique conjecture; it has been used as a computational hardness assumption.

Definition

A clique in a graph is a subset of vertices, all of which are adjacent to each other. A planted clique is a clique created from another graph by adding edges between all pairs of a selected subset of vertices.
The planted clique problem can be formalized as a decision problem over a random distribution on graphs, parameterized by two numbers, , and .
These parameters may be used to generate a graph, by the following random process:
  1. Create an Erdős–Rényi random graph on vertices by choosing independently for each pair of vertices whether to include an edge connecting that pair, with probability 1/2 for each pair.
  2. Decide whether or not to add a clique to the graph, with probability 1/2; if not, return the graph formed in step 1.
  3. Choose randomly a subset of of the vertices and add an edge between each pair of the selected vertices.
The problem is then to determine algorithmically whether one of the graphs resulting from this process contains a clique of at least vertices.
With high probability, the size of the largest clique in an -vertex random graph is close to. And when is larger than the square root of, the vertices of a planted clique can be recognized as having unusually large degrees, making a planted clique easy to find. Therefore, the most interesting range of values for the parameter is between these two values,

Algorithms

Large cliques

For sufficiently large values of the parameter, the planted clique problem can be solved in polynomial time.
observes that, when 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 , but shows that despite this modification the planted clique may still be found quickly.
prove for 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 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 is at least proportional to some multiple of the square root of the number of vertices. Large planted cliques can also be found using semidefinite programming.
A combinatorial technique based on randomly sampling vertices can achieve the same bound on and runs in linear time.

Quasipolynomial time

It is also possible to solve the planted clique problem, regardless of the choice of, in quasi-polynomial time.
Because the largest clique in a random graph typically has size near, a planted clique of size can be found with high probability by the following method:
  1. Loop through all sets of vertices.
  2. For each choice of, test whether is a clique. If it is, and, return. Otherwise, find the set of vertices that are adjacent to all vertices in. If, return.
The running time of this algorithm is quasipolynomial, because there are quasipolynomially many choices of to loop over. This method is guaranteed to try a set that is a subset of the planted clique; with high probability, the set will consist only of other members of the planted clique.

As a hardness assumption

The planted clique conjecture is the conjecture that there is no polynomial time algorithm that takes as input graphs produced by the planted clique process and distinguishes the ones with planted cliques from the ones that don't have planted cliques with probability significantly better than random chance.
used the assumption that finding planted cliques is hard as a computational hardness assumption to prove that, if so, it is also hard to approximate the best Nash equilibrium in a two-player game. The planted clique conjecture has also been used as a hardness assumption to show the difficulty of property testing -independence of random distributions, finding clusters in social networks, and machine learning.