6
$\begingroup$

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

$\endgroup$
0

3 Answers 3

15
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ Jan 31, 2013 at 19:45
  • $\begingroup$ 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... $\endgroup$ Jan 31, 2013 at 19:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Pål GD
    Jan 31, 2013 at 19:55
  • $\begingroup$ 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... $\endgroup$ Jan 31, 2013 at 19:58
  • 2
    $\begingroup$ @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. $\endgroup$ Feb 1, 2013 at 2:25
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 31, 2013 at 19:36
  • 1
    $\begingroup$ @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". $\endgroup$ Feb 1, 2013 at 2:16
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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