Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
add comment

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.

3 Answers

up vote 13 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.

share|improve this answer
    
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
show 2 more comments

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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