Clique problem is a well known $NP$-complete problem where the size of the required clique is part of the input. However, k-clique problem has a trivial polynomial time algorithm ($O(n^k)$ when $k$ is constant). I'm interested in the best known upper bounds when k is constant.

Is there an algorithm with run time $O(n^{k-1})$? A $o(n^k)$-time algorithm is also acceptable. Also, Is there any complexity-theoretic consequence for the existence of such algorithms?

up vote 19 down vote accepted

A 3-clique can be found in an $n$-vertex graph $G$ in time $O(n^\omega)$, where $\omega < 2.376$ is the matrix multiplication exponent, and in $O(n^2)$ space by a result of Itai and Rodeh [1]. Basically, they show that $G$ contains a triangle if and only if $(A(G))^3$ has a non-zero entry on its main diagonal. Because a triangle is also a cycle $C_3$, one can use general cycle finding methods for detecting triangles. Alon, Yuster and Zwick show how triangles can be detected on an $m$-edge graph in $O(m^{2\omega/(\omega+1)}) = O(m^{1.41})$ time [6].

For a long time, the result of Nesetril and Poljak [2] was the best known; they showed the number of cliques of size $3k$ can be found in time $O(n^{\omega k})$ and $O(n^{2k})$ space. Finally, Eisenbrand and Grandoni [3] improved on the result of Nesetril and Poljak for a $(3k+1)$-clique and a $(3k+2)$-clique for small values of $k$. Specifically, they gave algorithms for finding cliques of size 4, 5, and 7 in time $O(n^{3.334})$, $O(n^{4.220})$, and $O(n^{5.714})$, respectively.

As far as I know, for general $k$, the problem of designing better algorithms is open. For possible consequences or complexity theoretic considerations, Downey and Fellows (see e.g. [4]) showed $k$-clique with parameter $k$ is $W[1]$-hard. The class $W[1]$ denotes the class of parameterized decision problems reducible to CLIQUE with parameterized reductions. It is believed that CLIQUE is not fixed-parameter tractable. There are hundreds of other problems known to be equivalent to CLIQUE under parameterized reductions. Furthermore, Feige and Kilian [5, Section 2] have a result saying that when $k$ is part of the input and $k \approx \log n$, then a polytime algorithm is not likely to exist.

If you consider some restricted graph classes, you can solve the problem in linear time on chordal graphs. Simply compute a clique tree of a chordal graph $G$ in $O(n+m)$ time, and then check if any clique is of size exactly $k$. On planar graphs, one can also find triangles in $O(n)$ time using the methods of [6].


[1] Itai, Alon, and Michael Rodeh. "Finding a minimum circuit in a graph." SIAM Journal on Computing 7.4 (1978): 413-423.

[2] Nešetřil, Jaroslav, and Svatopluk Poljak. "On the complexity of the subgraph problem." Commentationes Mathematicae Universitatis Carolinae 26.2 (1985): 415-419.

[3] Eisenbrand, Friedrich, and Fabrizio Grandoni. "On the complexity of fixed parameter clique and dominating set." Theoretical Computer Science 326.1 (2004): 57-67.

[4] Downey, R. G., and Michael R. Fellows. "Fundamentals of Parameterized complexity." Undegraduate Texts in Computer Science, Springer-Verlag (2012).

[5] Feige, Uriel, and Kilian, Joe. "On Limited versus Polynomial Nondeterminism". Chicago Journal of Theoretical Computer Science. (1997)

[6] Alon, Noga, Raphael Yuster, and Uri Zwick. "Finding and counting given length cycles." Algorithmica 17.3 (1997): 209-223.

Your Answer

 
discard

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.