Explain the following text.



Independent Set is in NP: our certificate is a set V′ of vertices.
1. If |V ′| ̸⊆ V , reject If they aren’t all vertices in the graph, they aren’t an Independent Set 2. If |V ′ < k, reject If we don’t have k of them, it doesn’t fulfill the requirements
3. Foreachedgee=(u,v),ifu∈V′ andv∈V′,rejectIfitisn’tanindependentset,reject 4. If all requirements thus far pass, accept.
The idea of the reduction is to build a graph that has an independent set of size k if and only if the 3-Sat instance we are trying to solve has a satisfying truth assignment. The time must be a polynomial function of the size of the 3-Sat instance we are given. In lecture, we did this in two phases: we first started with a graph that will have an independent set that guides us to select one term in each clause to set to true. If we can then set these k terms to true, we will have satisfied every clause. We then amended the graph to ensure that no variable was set to both true and false.
3-Sat(n variables, k clauses) for each clause A∨B∨C do
Create 3 vertices // one each A, B, C
Add edges (A, B), (B, C), (A, C) for each variable xi do
Connect any “xi” node to all xi nodes return Independent Set(G,k)
Explanation: The idea is that each clause forms a clique, from which at most one vertex can be chosen by the Independent Set solver. Because there are k clauses and k cliques, at most one in each will be chosen. The chosen vertex represents a literal to set to be true or false to satisfy the clause. We add edges between literals and their negations so prohibit them from both being chosen. Note how general this is: it took us a lot more thought process to come up with the proof, but we want to give a concise explanation when writing it as a homework. Yes, I am aware of the irony of saying that in this document.
No false positives: Here, we show that if Independent Set returns true at the end, then this is the correct answer to the 3-Sat instance we are given. a return value of true indicates that there are k vertices that are chosen. Because at most one can be chosen from each clique, and there are k cliques, there must have been exactly one chosen in each. By construction, no literal and its negation was chosen. This means we can set the chosen vertices’ associated variables to be the truth value for that literal, satisfying each clause.
No false negatives: Here, we show that if the 3-Sat instance has a satisfying assignment, the graph we create will cause Independent Set to return true; thus, if there is a return value of “false,” we know it’s right. Suppose the 3-Sat instance has a satisfying assignment. Then each clause is satisfied in the 3-Sat instance, given that truth value assignment. We can choose arbitrarily one of the set-to-true literals in each clause and select its vertex in the corresponding clause. No such chosen vertices have an edge to a chosen vertex in any other clique (because the truth value assignment would not set a variable to both true and false). Thus, the graph has a valid independent set, and it is of size k because one was chosen in each of the k independent cliques. Therefore, Independent Set will return true for that graph with the parameter k.