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 planted clique problem can be formalized as a decision problem over a random distribution on graphs, parameterized by two numbers, n (the number of vertices), and k (the size of the clique).These parameters may be used to generate a graph, by the following random process:[1] The problem is then to determine algorithmically whether one of the graphs resulting from this process contains a clique of at least k vertices.such that asymptotically almost surely, the size of the largest clique in an n-vertex random graph is eitherNamely, if you plot out the vertex degree distribution, it would look like a deformed bell curve.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.a planted clique can be found with high probability by the following method: 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 log2 n,[8] a planted clique of size k (if it exists) can be found with high probability by the following method: 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.The search conjecture states that no polynomial time algorithm can find (with high probability) a hidden clique of sizenode random graphs, exactly one of which has a planted clique, but we don't know which.On average, a random graph with a planted clique will have more edges than a purely random graph, since the act of planting a clique of sizeTherefore, we can correctly determine which of the two graphs contains the planted clique with probabilityThe decision planted clique conjecture states that this is essentially optimal: it postulates that no polynomial time algorithm can distinguish between the two graphs with probability higher than[7] The planted clique conjecture has also been used as a hardness assumption to show the difficulty of property testing k-independence of random distributions,[11] finding clusters in social networks,[12] and machine learning.