0
$\begingroup$

I came across a statement in my book which claims that the problem P1 in NP-C and P2 is P.

P1: Given graph G(V, E), find out whether there exists an independent set of size k in the graph, where k is any positive integer.

P2: Given graph G(V, E), find out whether there exists an independent set of size 5 in the graph.

I cant get my head around this! I believe both should be in polynomial order.

Reason: $\binom{n}{5}=O(n^5)$ and so should $\binom{n}{k}=O(n^k)$.

Can anyone please explain whether I am right? or if not, what am I doing wrong?

Thanks in advance!

$\endgroup$
  • 5
    $\begingroup$ $O(n^k)$ isn't polynomial in $k$... $\endgroup$ – John Dvorak Jan 22 '19 at 3:47
  • 1
    $\begingroup$ @Juho That question is related, but not a duplicate, imo. The basic error is the same, but the approaches in the questions are different. (as well as the problems, although these are also very related. $\endgroup$ – Discrete lizard Jan 22 '19 at 8:04
  • 1
    $\begingroup$ Perhaps it would be clearer to say that for P1, you are given the graph G and any integer k as input. $\endgroup$ – Discrete lizard Jan 22 '19 at 8:05
  • $\begingroup$ Hi @Discretelizard, I have made the changes. I hope it's better now $\endgroup$ – Abhilash Mishra Jan 22 '19 at 9:09
  • $\begingroup$ Well, I meant that it may be clearer for you to note that k is part of the input. Try to think about it $\endgroup$ – Discrete lizard Jan 22 '19 at 15:37