Independent set in a graph

Question

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.

Answer 1

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.

Answer 2

There is a nice lower bound on the size of maximum independent set ("graph independence number" denoted by alpha),

where d(v) is the degree of the vertex v and the sum is over all the vertices of a simple graph G. It was discovered independently by Wei and Caro (I found it in "Lower bounds on the independence number in terms of the degrees" by JR Griggs) and there are other lower bounds for different types of graphs.

What this means is that a maximum independent set will have at least k vertices with k given by this lower bound.