I always read that finding an independent set of size $k$ in a graph is $\mathsf{NP}$-complete. However, this only requires looking for all combinations of $k$ vertices and this is a polynomial procedure of order $k$.

I know that we can reduce directly SAT to independent set, with $k$ the number of clauses.

The problem is that I can't grasp correctly, as in 3-COLORING or 3-SAT, the required format to study the complexity of INDEPENDENT SET.

What is the decision version of independent set? And why isn't $k$-independent set in $\mathsf P$?

migrated from cstheory.stackexchange.com Jan 31 '13 at 19:06

This question came from our site for theoretical computer scientists and researchers in related fields.

up vote 14 down vote accepted

The definition of the decision version of independent set is the following:

Given as input a graph $G = (V,E)$ and an integer $k \in \mathbb{N}$, does there exist a set of pairwise non-adjacent vertices $I \subseteq V$ of size $|I| \geq k$?

The problem is polynomial time solvable if you consider $k$ to be constant, i.e., you can solve the problem in time $\mathcal{O}(n^k)$ but we usually take $k$ to be a part of the input. If you reduce an NP-complete problem to this problem, you will see that the $k$ is indeed unbounded.

  • But I don't think this definition is complete. What is the size of the input in this case? the number of vertices? It is possible to have a non-deterministic algorithm that for input graph G and k generates the combinations k,n an this is polynomial. Also, the same can be used to generate a polynomial certificate of the non-existence of an independent set of size k. All the combinations showing that there is at least an edge on each one. – Jose Antonio Martin H Jan 31 '13 at 19:45
  • In 3-coloeing we measure by the size of the graph. In 3-sat by the number of vertices or clauses etc... But here is different... – Jose Antonio Martin H Jan 31 '13 at 19:50
  • 1
    We measure the complexity in both size of the graph $G$ and the size of $k$. We always measure the complexity in the entire input. In $3$-SAT we measure the size of the encoding of the formula. – Pål GD Jan 31 '13 at 19:55
  • Ok, but the definition you write only claims that you are given an integer k. It does not say anymore, for instance k=f(n) or so... – Jose Antonio Martin H Jan 31 '13 at 19:58
  • 2
    @Jose: the point is that if $k$ is not a fixed constant but instead can be any positive integer, then there is no fixed polynomial which is an upper bound for the run-time of the brute-force algorithm of checking all $\binom{n}k$ collections of size $k$. No poly-time upper bound means no containment in P. – Niel de Beaudrap Feb 1 '13 at 2:25

The problem is $k$ might be very big, say as big as about $n$. Then $n^k$ would be exponentially large.

  • I think this is missing the point a bit. The problem isn't that $k$ is "very big", the problem is that it can't be bounded by a constant. – Huck Bennett Jan 31 '13 at 19:36
  • 1
    @Huck: he does say "as big as $n$". Bigness is as bigness does, and it doesn't take much for an exponent in a run-time to be "big". – Niel de Beaudrap Feb 1 '13 at 2:16

You should distinguish the following two things.

Independent Set (what Pål GD described in his answer)
Instance: A graph G and an integer k∈ℕ.
Question: Does G have an independent set of size k?

k-Independent Set (k∈ℕ)
Instance: A graph G.
Question: Does G have an independent set of size k?

Note that the latter is not a single problem. Rather, it is an infinite family of problems: 1-Independent Set, 2-Independent Set, 3-Independent Set, 4-Independent Set, and so on.

Independent Set is NP-complete. k-Independent Set is in P for every k∈ℕ. They are completely different.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.