9
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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 ... $\endgroup$ – vzn Mar 26 '14 at 3:38
  • $\begingroup$ this Q/A hardness of parameterized clique tcs.se should answer your question directly. reply in Theoretical Computer Science Chat for more discussion $\endgroup$ – vzn Mar 26 '14 at 18:28
  • 1
    $\begingroup$ 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). $\endgroup$ – sd234 Mar 26 '14 at 21:48
  • $\begingroup$ 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 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. $\endgroup$ – vzn Mar 26 '14 at 22:19
9
$\begingroup$

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
  • 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
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – sd234 Apr 20 '14 at 1:11
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ 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})$. $\endgroup$ – Kristoffer Arnsfelt Hansen Apr 16 '14 at 8:48
  • $\begingroup$ 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$?) $\endgroup$ – vzn Apr 16 '14 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.