<p>Check out this paper:</p>
<p><a href="https://arxiv.org/abs/2011.08447" rel="nofollow noreferrer">Exact recovery of Planted Cliques in Semi-random graphs</a>, it gives a SDP based algorithm for solving the planted clique problem, where a clique of size <span class="math-container">$k$</span> is planted in <span class="math-container">$G(n, p)$</span> and recovers the planted clique with high probability when <span class="math-container">$p = \Omega\left(\dfrac{\log n}{n}\right)$</span> and <span class="math-container">$k = \Omega((np)^{1/2})$</span>.</p>
<p>Note that this paper solves the planted clique in a more general semi-random model, check out the introduction section for more details.</p>

CC BY-SA 4.0
2023-03-24T03:25:17.580Z
2023-03-24T05:59:22.913Z
2023-03-24T05:59:22.913Z
avocado
<p>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 &amp; it includes related refs. (2015)</p>

<blockquote>
  <p>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.</p>
</blockquote>

<ul>
<li><a href="http://arxiv.org/abs/1504.08352" rel="nofollow">ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness</a> / Braverman, Ko, Rubinstein, Weinstein</li>
</ul>

CC BY-SA 3.0
2015-05-01T01:40:54.840Z
2015-05-01T01:40:54.840Z
vzn
<p>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.</p>

<p><a href="http://arxiv.org/pdf/1404.3918v1.pdf" rel="nofollow">A SIMPLE SVD ALGORITHM FOR FINDING HIDDEN PARTITIONS</a> Van Vu</p>

<blockquote>
  <p>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.</p>
</blockquote>

CC BY-SA 3.0
2014-04-16T08:48:23.987Z
It works for $p=1/2$ also, but not for arbitrary $p$. Note also that for $p$ constant, the hidden clique must still be of size $\Omega(\sqrt{n})$.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-04-16T15:48:31.723Z
not saying its the exact/definitive answer, only some improvement over other $p=½$ only limits of other papers. it analyzes a wide range of $p$ values subj to misc constraints (incl clique size), details in the paper. the question seems not so strict about what the exact/simultaneous clique size/$p$ combination constraint is. (doesnt the paper indeed cover some of the case $p≠½, k=n^\alpha$ asked for? or are you interpreting the question as strictly restricting $\alpha$?)
vzn
CC BY-SA 3.0
2014-04-16T02:45:20.280Z
2014-04-16T02:45:20.280Z
vzn
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<ul>
<li>Béla Bollobás, <em>Random Graphs</em> (2nd edition), Cambridge University Press, 2001.</li>
<li>Ferenc Juhász, <em>The asymptotic behaviour of Lovász' $\vartheta$ function for random graphs</em>, Combinatorica <strong>2</strong>(2) 153–155, 1982.  doi:<a href="http://dx.doi.org/10.1007/BF02579314">10.1007/BF02579314</a></li>
<li>Uriel Feige and Robert Krauthgamer, <em>Finding and certifying a large hidden clique in a semirandom graph</em>, Random Structures &amp; Algorithms <strong>16</strong>(2) 195–208, 2000.  doi:10.1002/(SICI)1098-2418(200003)16:2&lt;195::AID-RSA5>3.0.CO;2-A</li>
</ul>

CC BY-SA 3.0
2014-04-20T01:11:23.897Z
Thanks. This seems to summarize the state of the art, and confirm that nothing too definitive is known. The best evidence that the problem behaves similarly seems to be the value of the Lovasz theta function, as you point out.
sd234
CC BY-SA 3.0
2014-04-16T11:00:27.043Z
2014-04-16T11:00:27.043Z
András Salamon
<p>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 &gt; \sqrt{n}$ and conjectured hard for $k&lt; \sqrt{n}$. </p>

<p>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?</p>

<p>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}$.</p>

CC BY-SA 3.0
2014-03-26T03:38:45.163Z
yes it is hard for some parameters based on the NP complete transition point phenomenon which is more studied for SAT but holds for the clique problem also & has been studied some/less so there. this is closely related to finding lower bounds on monotone circuits for the clique problem and slice functions. there are a few related questions on the site, may dig them up. the recent paper by Rossman on clique function hardness is relevant. etc ... might work into answer later depending on whether others show up ...
vzn
CC BY-SA 3.0
2014-03-26T18:28:33.953Z
this Q/A [hardness of parameterized clique](http://cstheory.stackexchange.com/questions/1441/hardness-of-parameterized-clique) tcs.se should answer your question directly. reply in [chat] for more discussion
vzn
CC BY-SA 3.0
2014-03-26T21:48:35.663Z
Thanks. I was mostly concerned with the planted version though, and not the worst-case version (which, as you say, is NP complete for constant p).
sd234
CC BY-SA 3.0
2014-03-26T22:19:40.897Z
ok, it appears "planted clique" is generally limited to G(n,½) as you state as in this recent paper [Statistical Algorithms and a Lower Bound for Detecting Planted Clique](http://arxiv.org/abs/1201.1214) by Feldman et al which considers it & cites related refs but again doesnt consider p≠½. the overall problem seems to be "close" to finding cliques of some size in a G(n,p) graph for some choices of parameters (the later is apparently much more studied as in the linked tcs.se pg) but havent seen that connection pointed out or elaborated/detailed elsewhere.
vzn
<cc.complexity-theory><approximation-algorithms><approximation-hardness>
Planted Clique in G(n,p), varying p
sd234
# Planted Clique in G(n,p), varying p

(Asked by: username_0 on 2014-03-26)

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}$.

**Tags:** cc.complexity-theory, approximation-algorithms, approximation-hardness
> **Comments:**
> **username_1**: yes it is hard for some parameters based on the NP complete transition point phenomenon which is more studied for SAT but holds for the clique problem also & has been studied some/less so there. this is closely related to finding lower bounds on monotone circuits for the clique problem and slice functions. there are a few related questions on the site, may dig them up. the recent paper by Rossman on clique function hardness is relevant. etc ... might work into answer later depending on whether others show up ...  
> **username_1**: this Q/A [hardness of parameterized clique](http://cstheory.stackexchange.com/questions/1441/hardness-of-parameterized-clique) tcs.se should answer your question directly. reply in [chat] for more discussion  
> **username_0**: Thanks. I was mostly concerned with the planted version though, and not the worst-case version (which, as you say, is NP complete for constant p).  
> **username_1**: ok, it appears "planted clique" is generally limited to G(n,½) as you state as in this recent paper [Statistical Algorithms and a Lower Bound for Detecting Planted Clique](http://arxiv.org/abs/1201.1214) by Feldman et al which considers it & cites related refs but again doesnt consider p≠½. the overall problem seems to be "close" to finding cliques of some size in a G(n,p) graph for some choices of parameters (the later is apparently much more studied as in the linked tcs.se pg) but havent seen that connection pointed out or elaborated/detailed elsewhere.  

---

## 4 answers

### Answer by username_4 on 2014-04-16. Score: 11 | Accepted answer

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](http://dx.doi.org/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

> **Comments:**
> **username_0**: Thanks. This seems to summarize the state of the art, and confirm that nothing too definitive is known. The best evidence that the problem behaves similarly seems to be the value of the Lovasz theta function, as you point out.  

---

### Answer by username_2 on 2023-03-24. Score: 1

Check out this paper:

[Exact recovery of Planted Cliques in Semi-random graphs](https://arxiv.org/abs/2011.08447), it gives a SDP based algorithm for solving the planted clique problem, where a clique of size $k$ is planted in $G(n, p)$ and recovers the planted clique with high probability when $p = \Omega\left(\dfrac{\log n}{n}\right)$ and $k = \Omega((np)^{1/2})$.

Note that this paper solves the planted clique in a more general semi-random model, check out the introduction section for more details.


---

### Answer by username_1 on 2015-05-01. Score: 0

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](http://arxiv.org/abs/1504.08352) / Braverman, Ko, Rubinstein, Weinstein


---

### Answer by username_1 on 2014-04-16. Score: 0

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](http://arxiv.org/pdf/1404.3918v1.pdf) 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.

> **Comments:**
> **username_3**: It works for $p=1/2$ also, but not for arbitrary $p$. Note also that for $p$ constant, the hidden clique must still be of size $\Omega(\sqrt{n})$.  
> **username_1**: not saying its the exact/definitive answer, only some improvement over other $p=½$ only limits of other papers. it analyzes a wide range of $p$ values subj to misc constraints (incl clique size), details in the paper. the question seems not so strict about what the exact/simultaneous clique size/$p$ combination constraint is. (doesnt the paper indeed cover some of the case $p≠½, k=n^\alpha$ asked for? or are you interpreting the question as strictly restricting $\alpha$?)  

---

