As you know finding maximum independent set is NP. Is there an algorithm to find out whether a given graph has an Independent set of at least k vertices? Note that we don't want to find it. We just want to find out if such thing exists.
+1
A:
Quoting Wikipedia:
In the independent set decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph contains an independent set of size k, and false otherwise.
This problem is NP-complete. Your problem asks the same question, just differently phrased, because a graph has an independent set of at least k vertices if and only if it has an independent set of exactly k vertices.
That means your problem is NP-complete too.
svick
2010-08-22 11:06:00
Thanks! I didn't know this.
AKGMA
2010-08-22 11:26:20
IMO to be precise, a graph has an independent set of at least k vertices if it has at least an independent set of n vertices with n greater equal to k. Anyway I think it's NP-Complete as well.
digEmAll
2010-08-22 12:02:06