PDF of Eric’s handwritten notes are here.
In this last lecture we took for granted that SAT is NP-Complete, and then we used this fact to show that 3-SAT is NP-Complete. Now we’ll build on the NP-completeness of 3-SAT to prove that a few graph problems, namely, Independent Set, Clique, and Vertex Cover, are NP-Complete.
The first problem we’ll consider is the independent set problem. Let’s first recall the definition of an independent set.
Definition: Independent Set:
For an undirected graph , is an independent set if for all , we have .
In other words, no edge is contained in .
Small independent sets are trivial to find, e.g., the empty set or a single vertex. The challenge is to find a large independent set. For the Max-Independent-Set problem in which we find an independent set of maximum size, we can’t show that’s in NP, unless P=NP, because we can’t verify that a set is of maximum size. Hence we have an extra input parameter and we look for an independent set of size .
Definition: Independent-set Problem:
- Input: Undirected graph and goal .
- Output: Independent Set where if one exists;
Claim: Independent-set problem is NP-Complete.
a) Independent-set NP: Given input and solution , we
consider all pairs and check that . This takes time to consider all pairs in and time for each pair to check that it is not an edge. Finally, in time we check that .
b) 3-SAT Independent-set
Assume there is a poly-time algorithm for the independent-set problem, and we’ll use this algorithm as a black-box to create an algorithm for the 3-SAT problem.
Consider 3-SAT input with variables
and clauses , where each clause has size .
We will create a graph based on . Formula has clauses so we will set .
The vertices of will correspond to literals of , though there will potentially be many vertices corresponding to the same literal. If all clauses are of size exactly 3 then we will have vertices in . Let us define it precisely.
For a clause for literals , create 3 vertices corresponding to and put all 3 edges between them to make them a triangle. In general, if clause has size then add vertices corresponding to the literals in and add the complete graph between these vertices.
Note, any independent set of can include at most one of the vertices for each clause . And hence to obtain an independent set of size where it will need to include exactly one per clause “gadget”.
For each variable , add an edge between all vertices corresponding to and all vertices corresponding to . These edges ensure that an independent-set does not include both and , and hence corresponds to a valid assignment for .
Combining these two properties, we know that to get , we need exactly one vertex per clause, and hence a solution to the independent-set problem on the graph corresponds to a satisfying assignment of . Let us formalize this.
Claim: has a satisfying assignment has an independent set of size .
(): Consider a satisfying assignment for . For each clause , at least one of the literals in is satisfied. Choose one of these satisfied literals and include its corresponding vertex in . Hence, .
By construction, includes exactly one vertex per clause so no edges within a clause’s gadget are covered by . Moreover, since we started from an assignment for the variables then does not include opposing literals, so no edges between opposite literals are covered. Hence, is an independent set.
(): Take an independent set of size . For each vertex in set the corresponding literal to , we will prove this gives a satisfying assignment. Since there are edges between vertices corresponding to opposite literals, does not contain vertices corresponding to opposite literals and so this assignment from will not set both literals and to ; hence, it is a valid assignment. Moreover, since and since there is a complete graph for each clause’s gadget, the set has exactly one vertex per clause’s gadget. This gives at least one satisfied literal per clause and hence we have a valid assignment that satisfies .
Next we’ll consider the clique problem. Here is the definition of a clique.
Clique: For an undirected graph , is a clique if for all , we have .
In other words, is a fully connected subgraph.
The challenge is to find a large clique.
Definition: Clique Problem:
- Input: Undirected graph and goal .
- Output: Clique where if one exists;
Claim: The Clique problem is NP-Complete.
a) Clique NP: Given input and solution , check for all pairs that ; this takes time. Then, check which takes time.
b) Independent Set Clique
Key idea: Clique is opposite of independent set.
For a graph , denote its “opposite” graph by: where . In other words, .
Observe that: is an independent set in G is a clique in .
Now we can show Independent set Clique:
Given and as input for the independent set problem, let and be the input to the clique problem.
If we get a solution for Clique then return the same as the solution to the original independent set problem. If we get NO, then we return NO for the independent set problem.
Definition: Vertex Cover:
For an undirected graph , is a vertex cover if it covers every edge in the following sense: for all , either and/or .
The set is a trivial vertex cover, and hence the challenge is to find a small vertex cover.
Definition: Vertex Cover Problem:
- Input: Undirected graph and goal
- Output: VC where if one exists; NO otherwise
Claim: The Vertex Cover problem is NP-Complete.
a) Vertex Cover NP: Given input and solution , for every edge of , check that at least one of $u$ and $v$ are in ; this takes time. We then check that which takes time.
b) Independent Set Vertex Cover.
Claim: For any undirected graph , is a vertex cover is an independent set.
(): Consider a vertex cover where . For each , and/or . Hence, at most one of is in . So no edge has both endpoints in , which means is an independent set.
(): Take an independent set . For , at most one of is in . So at least one of is in , which means covers every edge, and hence is a vertex cover.
Independent Set problem Vertex Cover problem:
Consider input for independent set problem. Let be the input for the vertex cover problem. We know that has an independent set of size has a vertex cover of size .
If we get solution for vertex cover, then wen return as the solution to the original independent set problem.
If we get NO solution for VC, then we return NO for IS.