Max independent set problem is NP-hard

Statement

Lemma

Max independent set problem is NP-hard.

Proof

We know the Independent set of a given size is NP-complete, therefore it is NP-hard. We can reduce the Independent set of a given size to max independent set problem using the straight forward Many-one reduction.

Suppose we have a graph and integer . Pass this graph to the max independent set problem. This step is as we need to do no manipulation.

The solution provides a max independent set. If then return , otherwise return no. This step takes so it is polynomial in the input size.

If the graph has an independent set of size at least then its max independent set is of size , so we return true in the case.

If the graph has a max independent set of size greater than then it has an independent set of size by definition.