7
$\begingroup$

I am trying to find results on the best known time complexity for finding $(1+\epsilon) \log n$ sized cliques in $G(n,1/2)$. More general results would be great, i.e. if $C_p$ is the constant such that the obvious greedy algorithm finds a clique of size $C_p \log n$ in $G(n,p)$ almost surely, then any results on finding a clique of size $(C_p + \epsilon ) \log n$ would be even better.

In particular, I am interested in whether we know how to find a $(C_p +\epsilon)\log n$ clique in $G(n,p)$ using $O(n^{\epsilon^2\log n})$ time and $O(n^{\epsilon^2\log n})$ space. Would a randomized algorithm that finds a $(C_p +\epsilon)\log n$ vertex clique with high probability under these time and space constraints constitute a publishable result? Any pointers to relevant literature would be greatly appreciated.

$\endgroup$
3
+50
$\begingroup$

Feldman et al. [1] give several references to methods for e.g., finding cliques of size $k = \Omega(\sqrt{n})$, including spectral methods, SDPs, combinatorial methods, nuclear norm minimization, and belief propagation. They also say the quasipolynomial-time algorithm is the fastest one known for planted $k$-clique detection for any $k=O(n^{1/2−\delta})$, where $\delta > 0$.


[1] Feldman, Vitaly, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao. "Statistical algorithms and a lower bound for detecting planted cliques." In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 655-664. ACM, 2013.

$\endgroup$
3
$\begingroup$

To answer the first part of your question, a conjecture in Karp'76 states that there is no efficient algorithm to find cliques of size $(1+ \epsilon)\log(n)$ for $G(n, 1/2)$. This conjecture is still open.

$\endgroup$
  • 5
    $\begingroup$ But the OP is asking for algorithms even running in quasi-polynomial time ($n^{\varepsilon^2\log n}$), so the fact that the conjecture of Karp is still unresolved does not give tha much information about this specific question. $\endgroup$ – Clement C. Dec 5 '17 at 5:51
  • 1
    $\begingroup$ @AineshBakshi I am familiar with this result, and I also know of some quasi-polynomial time results based off of repeatedly running the greedy algorithm for finding maximal cliques. The best result I found was based off of this and has expected running time $O(n^{ \frac{(1+\epsilon) \log n}{4}+O(1)})$. This was discovered a few decades ago, and I doubt it's still "state of the art." I am hard-pressed to find an algorithm with expected running time of even $O(n^{ \epsilon \log n})$ instead of $O(n^{ \epsilon^{2} \log n})$. $\endgroup$ – mm8511 Dec 5 '17 at 15:16
  • 3
    $\begingroup$ @ClementC. Thank you for helping clarify my intent. Much appreciated :). $\endgroup$ – mm8511 Dec 5 '17 at 15:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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