Planted clique

Short description: Complete subgraph added to a random graph

A 15-vertex planted clique (blue vertices and upper edges) in a 32-vertex random graph (all vertices and lower edges). Every pair of blue vertices is adjacent; the remaining pairs are adjacent randomly with probability 1/2.

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.

## Contents

* 1 Definition
* 1.1 Upper and lower bounds
* 2 Algorithms
* 2.1 Large cliques
* 2.2 Quasipolynomial time
* 3 As a hardness assumption
* 4 References

## 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, 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]

1. Create an Erdős–Rényi random graph on n 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 k of the n vertices and add an edge (if one is not already present) 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 k vertices.

### Upper and lower bounds

There exists a function f(n)∼2log2n such that asymptotically almost surely, the size of the largest clique in an n-vertex random graph is either f(n) or f(n)+1,[2] and there exists some constant c such that the expected number of cliques of size ≥f(n)−c converges to infinity. Consequently, one should expect that the planting a clique of size ∼2log2n 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 n2 and standard deviation n2. Consequently, when k is on the order of 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]

2log2n≪k≪n.

## Algorithms

### Large cliques

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 k=Ω(nlog⁡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) prove for k>10n 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.Cite error: Closing `</ref>` missing for `<ref>` tag

### Quasipolynomial time

It is also possible to solve the planted clique problem, regardless of the choice of k, in quasi-polynomial time.[4] Because the largest clique in a random graph typically has size near 2 log2 n,[5] 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 min⁡(k,3log2n) vertices.
2. For each choice of S, test whether S is a clique. If it is, and |S|=k, return S. Otherwise, find the set T of vertices that are adjacent to all vertices in S. If |T|≥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.

## As a hardness assumption

There are two versions of the planted clique conjecture: one based on finding the clique (search) and one based on determining if a clique exists (decision). The search conjecture states that no polynomial time algorithm can find (with high probability) a clique of size k << n0.5 in a random graph with n nodes and a hidden clique of size k.[6]

The decision conjecture is more subtle. Suppose we are given two n node 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 size k is expected to add Θ(k2) edges. Therefore, we can correctly determine which of the two graphs contains the planted clique with probability 1/2+Θ(k2/n) by simply counting the number of edges in each graph. The 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 1/2+Θ(k2/n).[6][7]

(Hazan Krauthgamer) 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.[4] The planted clique conjecture has also been used as a hardness assumption to show the difficulty of property testing k-independence of random distributions,[8] finding clusters in social networks,[9] and machine learning.[10]

## References

1. ↑ 1.0 1.1 1.2 Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, pp. 362–363, ISBN 9780521424264, https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA362 .
2. ↑ Bollobás, B.; Erdős, P. (November 1976), "Cliques in random graphs" (in en), Mathematical Proceedings of the Cambridge Philosophical Society 80 (3): 419–427, doi:10.1017/S0305004100053056, ISSN 1469-8064, Bibcode: 1976MPCPS..80..419B, https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/abs/cliques-in-random-graphs/27321102B82EDEEF362556BE714FACD9
3. ↑ Kučera, Luděk (1995), "Expected complexity of graph partitioning problems", Discrete Applied Mathematics 57 (2–3): 193–212, doi:10.1016/0166-218X(94)00103-K .
4. ↑ 4.0 4.1 Hazan, Elad; Krauthgamer, Robert (2011), "How hard is it to approximate the best Nash equilibrium?", SIAM Journal on Computing 40 (1): 79–91, doi:10.1137/090766991 .
5. ↑ "On colouring random graphs", Mathematical Proceedings of the Cambridge Philosophical Society 77 (2): 313–324, 1975, doi:10.1017/S0305004100051124, Bibcode: 1975MPCPS..77..313G .
6. ↑ 6.0 6.1 Hirahara, Shuichi; Shimizu, Nobutaka (2024), "Planted Clique Conjectures Are Equivalent", Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 358–366, doi:10.1145/3618260.3649751, ISBN 979-8-4007-0383-6
7. ↑ Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri (2015), ETH hardness for densest-k-subgraph with perfect completeness, Bibcode: 2015arXiv150408352Bk-subgraph+with+perfect+completeness&rft.aulast=Braverman&rft.aufirst=Mark&rft.au=Braverman, Mark&rft.au=Ko, Young+Kun&rft.au=Rubinstein, Aviad&rft.au=Weinstein, Omri&rft.date=2015&rft_id=info:bibcode/2015arXiv150408352B&rfr_id=info:sid/en.wikibooks.org:Planted_clique"> .
8. ↑ "Testing k-wise and almost k-wise independence", STOC'07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, New York: ACM, 2007, pp. 496–505, doi:10.1145/1250790.1250863, ISBN 9781595936318k-wise+and+almost+k-wise+independence&rft.atitle=STOC'07—Proceedings+of+the+39th+Annual+ACM+Symposium+on+Theory+of+Computing&rft.au=Andoni, Alexandr&rft.au=Matulef, Kevin&rft.au=Xie, Ning&rft.date=2007&rft.pages=pp. 496–505&rft.place=New+York&rft.pub=ACM&rft_id=info:doi/10.1145/1250790.1250863&rft.isbn=9781595936318&rfr_id=info:sid/en.wikibooks.org:Planted_clique"> .
9. ↑ "Finding Endogenously Formed Communities", Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '13), SIAM, 2013, pp. 767–783, ISBN 978-1-611972-51-1, http://dl.acm.org/citation.cfm?id=2627817.2627872 .
10. ↑ Berthet, Quentin; Rigollet, Philippe (2013), "Complexity theoretic lower bounds for sparse principal component detection", Journal of Machine Learning Research 30: 1046–1066, http://jmlr.org/proceedings/papers/v30/Berthet13.html .

* v
* t
* e

Computational hardness assumptions

Number theoretic|

* Integer factorization
* Phi-hiding
* RSA problem
* Strong RSA
* Quadratic residuosity
* Decisional composite residuosity
* Higher residuosity

Group theoretic|

* Discrete logarithm
* Diffie-Hellman
* Decisional Diffie–Hellman
* Computational Diffie–Hellman

Pairings|

* External Diffie–Hellman
* Sub-group hiding
* Decision linear

Lattices|

* Shortest vector problem (gap)
* Closest vector problem (gap)
* Learning with errors
* Ring learning with errors
* Short integer solution

Non-cryptographic|

* Exponential time hypothesis
* Unique games conjecture
* Planted clique conjecture

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Planted clique. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Planted_clique&oldid=3985269"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template