Does graph G contain a 100-node clique as a subgraph? Is it in P?

270 Views Asked by At

Although the clique problem is NP-complete, is this restricted version also considered to be NP-complete or is it actually in P?

I would imagine since you are still trying to solve the clique problem then this problem would still be NP-complete but maybe I'm missing something.

1

There are 1 best solutions below

4
On BEST ANSWER

Enumerate all possible ways to make a 100 node subgraph. (If there are $n$ nodes, it can take $O(n^{100})$ time.) Check if it is complete. Clearly this is in P.