171 Question V (20 points; 1,1,18 points): NP-Completeness Consider the 3-SAT decision problem, which is defined as follows: Input: A Boolean formula f, where each clause consists of exactly 3 literals. Question: Is fsatisfiable? b) Find a satisfying truth assignment for the following instance of the 3-SAT problem: c) Consider the following graph G. Note that some of the edges are purposely emphasized 4. 4. Find an independent set of size 3 for G (by marking the vertices on the same graph) d) Given that the 3-SAT problem is NP-Complete, show that the Independent Set problem is NP-Complete. Note that part b is very useful 171 Question V (20 points; 1,1,18 points): NP-Completeness Consider the 3-SAT decision problem, which is defined as follows: Input: A Boolean formula f, where each clause consists of exactly 3 literals. Question: Is fsatisfiable? b) Find a satisfying truth assignment for the following instance of the 3-SAT problem: c) Consider the following graph G. Note that some of the edges are purposely emphasized 4. 4. Find an independent set of size 3 for G (by marking the vertices on the same graph) d) Given that the 3-SAT problem is NP-Complete, show that the Independent Set problem is NP-Complete. Note that part b is very useful