Independent Set

Let be a graph. An independent set is a subset of nodes in which have no common edges. The language for the decision problem of finding a size independent set is as follows.

Info

is NP-complete

Given an set of nodes, we can check if it is of size and is an independent set in polynomial time. Thus .

To show completeness, we reduce from Clique. Let be some graph, and construct the complementary graph , where and . A -clique of corresponds to a independent set of . Thus we have a polytime reduction and is NP-complete.