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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
3
  • 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, 2017 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, 2017 at 15:16
  • 3
    $\begingroup$ @ClementC. Thank you for helping clarify my intent. Much appreciated :). $\endgroup$
    – mm8511
    Dec 5, 2017 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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