-1

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.

sanic
  • 447
  • Just out of curiosity, why did you ask about $100$-cliques instead of $2$-cliques or $3$-cliques? Is it because $x^2$ and $x^3$ are polynomials, but you aren't sure if $x^{100}$ is a polynomial? – bof Apr 10 '16 at 01:07
  • Just a different number (but still common) number I suppose. – sanic Apr 10 '16 at 01:11
  • So you think determining whether a graph contains a $3$-node clique might be an NP-complete problem? – bof Apr 10 '16 at 01:14

1 Answers1

1

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.

Element118
  • 3,753
  • How is this in P? Enumerating all possible 100 node subgraphs would take non-poly wouldn't it? – sanic Apr 10 '16 at 01:08
  • It would take $O(n^{100})$ time, so still polynomial. – Element118 Apr 10 '16 at 01:14
  • so you are just checking every possible 100 node subgraph for it being a clique and once we find one we stop? It would be np-complete if you had to search through the graph finding a clique though right? – sanic Apr 10 '16 at 01:20
  • 1
    @sanic If there is no 100-node clique, or if there is only one such clique and it's the last one we check,then we have to look at every 100-node subgraph. So what, the number of 100-node subgraphs is less than $n^{100}.$ – bof Apr 10 '16 at 01:52