Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
Where have you looked, what have you tried? What is your motivation for asking? –  Raphael Feb 2 '13 at 19:27
add comment

2 Answers 2

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.

share|improve this answer
    
The algorithm I outlined can be adapted to your clarified question. –  Yuval Filmus Jan 27 '13 at 19:33
add comment

i think you can count the number of 2-children-parties first, store the structure of the party, and use this to search for the 3-children-parties, etc. Cheers !

share|improve this answer
    
How does this answer the question? It's like saying "In order to drive from A to B, you first find the next intersection to go to, from there the second and so on" -- clearly not an effective method for finding your way. –  Raphael Feb 2 '13 at 19:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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