complexity-theorynpcliqueclique-problem

An algorithm to prove that for a constant K, K-Clique in P?

I am a newbie in theoretical computer and I was asked to do such an algorithm that works in a polynomial time for K-CLIQUE to prove that it belongs to P.

I was thinking about an algorithm that takes a graph of n vertex, and for each vertex , for example S0, I check how many cliques it has for example (s1 , s2 , s5) , then check with S1 if it is having cliques with s2, s5 then I go for s2 and check if it has a clique with s5.

but I think I am complicated my life, right?

Any suggestion on the algorithm? I know it is easy and maybe someone out there would help me with it to understand how finding an algorithm works.

Appreciated

Solution

  • As a hint, if k is a constant, then the number of sets of exactly k nodes is O(nk). What happens if you try every single one of them?