4
$\begingroup$

Given a graph with $n \leq 50 $ vertices. Count all $k$-cliques of this graph, where $k = 1, \ldots , n$.

I need the most efficient algorithm.

$\endgroup$
1
  • $\begingroup$ Where have you looked, what have you tried? What is your motivation for asking? $\endgroup$
    – Raphael
    Feb 2, 2013 at 19:27

1 Answer 1

9
$\begingroup$

Your problem (assuming I understand your English correctly) is counting the number of cliques in a graph of size $n = 50$. Counting the number of cliques in a graph is #P-complete (see this paper, which shows that counting the number of independent sets in a graph is #P-complete even for bipartite graphs).

Several efficient exponential time algorithms for the problem (efficient in the sense that their running time is $O(c^n)$ for $c<2$) are described in Jeff Erickson's lecture notes - see section 4.2 on page 4. The simplest algorithm, whose running time is $O(\phi^n)$ (where $\phi$ is the golden ratio), is as follows. For an arbitrary vertex $v \in G$ with neighborhood $N(v)$, we have the following recurrence for the number $I(G)$ of independent sets in $G$ (to get the number of cliques, complement $G$): $$ I(G) = \begin{cases} 2I(G-v), & N(v) = \emptyset, \\ I(G-v) + I(G\setminus(N(v)+v)), & \text{otherwise}. \end{cases} $$

This algorithm might be practical for $n=50$. If it isn't, you can try the other algorithms described in the lecture notes. Some of them require some modification for your case, and therefore the running times listed there might not hold in your case.

$\endgroup$
5
  • $\begingroup$ The algorithm I outlined can be adapted to your clarified question. $\endgroup$ Jan 27, 2013 at 19:33
  • $\begingroup$ Your first link is broken. Can you please fix it and also include the paper title in the post (so we can google it up next time)? $\endgroup$
    – Szabolcs
    Oct 23, 2015 at 16:54
  • $\begingroup$ @Szabolcs Judging from the link it's not a published paper. $\endgroup$ Oct 23, 2015 at 20:07
  • $\begingroup$ It seems I can download it with curl, even though my browser wouldn't open the link. It's this paper. Could you please edit that into the question somehow? E.g. add the DOI or some other permanent identifier in case the link goes fully dead? $\endgroup$
    – Szabolcs
    Oct 23, 2015 at 20:10
  • $\begingroup$ @Szabolcs You can also edit my answer. Someone will have to approve your edit, that's all. $\endgroup$ Oct 23, 2015 at 20:12

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.