Independent set of a given size is NP-complete

Statement

Lemma

Independent set of a given size is NP-complete.

Proof

As Independent set of a given size is in NP all we need to show is that Independent set of a given size is NP-hard.

To show this we are going to find a many-one reduction of the 3-SAT problem to Independent set of a given size problem. (We know 3-SAT is NP-complete so this gives us that Independent set of a given size is also NP-complete.) This will involve:

• Taking an instance of the 3-SAT problem and converting it to a Independent set of a given size problem in polynomial time,
• Showing how to transform a solution to the Independent set of a given size problem back to a solution to the 3-SAT problem in polynomial time, and
• Showing that a solution exists to the 3-SAT problem if and only if a solution exists to the Independent set of a given size problem.

Suppose we are given a 3-SAT problem with variables and clauses . We know each clause has at most 3 literals , , and (maybe less). Set be the set of literals in the clauses . We are going to construct a graph where each clauses is a clique and we connect any literals to their inverses. So we will two sets of edges, clause edges and negation edges Then an independent set of size will indicate a set of literals to set to true to get a correct assignment. Define the undirected graph We now apply the solution of Independent set of a given size to and .

To make we need to scan through each clause and make at most 3 vertices, this is . Then to connect the edges we need to first add the which takes again. To find all the negation edges for each variable we need to find all the literals using that, this takes . Therefore this process takes and is polynomial time in the size of the input.

When we have a solution to the Independent set of a given size problem we all the literals in the independent set to true. (This is valid as we know no 2 literals in this independent set can be the negation of one another from the negation edges.) Then for any left over variables we just set them to be true.

This process takes time as we have to check if a variable is in the set of returned literals.

Suppose the 3-SAT problem has an assignment that solves it.

For each clause at least one literal must be correct, define this set .

The set forms the independent set in of size . As is a valid assignment for we have . By definition each literal in belongs to a different clause.

Suppose we have an independent set in of size .

As this is an independent set the negation edges guarantee for we have . Therefore we can define a partial assignment of the original variables where True for . This can be extended to a full assignment of the original variables where if is not assigned we just set True.

As each clause is a clique in from the clause edges every element of belongs to a different clause. As it is of size each clause has an element in . So .

As we have at least one literal in each clause being true, the assignment satisfies the original CNF . Therefore is satisfiable.

This gives the reduction of 3-SAT to the Independent set of a given size problem and makes it NP-complete.