Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have a graph $G$, where each node in there has a degree of at most $d$. I need to show that it is possible to determine if $G$ has a clique of size $k$ in time of at most $n^c \cdot d^k$ steps where $c$ is some constant.

Any help will be great.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

For each vertex $v$, denote by $\Gamma(v)$ the set of neighbors of $v$. For each vertex $v$, set $A_1:=\Gamma(v)$ and $C_1:=\{v\}$. In the following recursion, $A_i$ denotes the set of possible candidates to enter the clique and $C_i$ is the largest clique containing $v$ which we have already found:

For each $w\in A_i$, check whether $C_i\subseteq\Gamma(w)$. If so, then we have found a larger clique $C_{i+1}:=C_i\cup\{w\}$. Also, we can set $A_{i+1}:=\Gamma(w)\cap A_i$ since any vertex in an even larger clique will have to be a neighbor of all vertices in $C_{i+1}$. For performance reasons, we would stop as soon as $|A_i\cup C_i|<k$, of course.

If at some point you reach $i=k$, then $C_k$ is a clique of size $k$. On the other hand, if there is a clique of size $k$, then this procedure will find it by starting at any of its vertices. The running time is $nd^k$.

share|improve this answer
    
Great thanks :) –  DanielY May 29 '13 at 7:09

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.