algorithmmathgraphindependent-set

Independent set in a graph


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.


Solution

  • 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.