# What is the decision version of independent set?

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$?

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. Jan 31, 2013 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... Jan 31, 2013 at 19:50
• 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. Jan 31, 2013 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... Jan 31, 2013 at 19:58
• @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. Feb 1, 2013 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. Jan 31, 2013 at 19:36
• @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". Feb 1, 2013 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.