CS6515 EXAM 3 STUDY GUIDE
2026/2027 ACTUAL QUESTIONS WITH
VERIFIED ANSWERS.
How to prove S is an independent set? - correct answer --S has
exactly 1 vertex per clause
-Both x₁ and x₁' are not in S.
-|S| = m = g
What are the claims of 3SAT reduction to Independent Set? -
correct answer -- 3SAT input, f, has a satisfying assignment <==>
G has an independent set of size ≥ g
- g = m = # of clauses
For the above implication, what is the forward proof? - correct
answer -Given the 3SAT input and a satisfying assignment, show
that G has an independent set of size ≥ g.
-For each clause C, take 1 of the satisfied literals and add to the
set S
-S has 1 vertex per clause.
, For the above implication, what is the reverse proof? - correct
answer -Given an independent set of size ≥ g, show that f has a
satisfying assignment.
-IS has 1 vertex per clause. Each vertex is satisfying assignment.
-Set that vertex to true.
-Every clause is now satisfied
What problems are known NP-Hard? - correct answer -1. Max-
Independent-Set problem.
What problems are known NP-Complete? - correct answer -1.
Max-Independent-Set
2. Clique
3. Vertex Cover
4. SAT
5. 3SAT
6. Independent Set
What problems are known NP? - correct answer -
2026/2027 ACTUAL QUESTIONS WITH
VERIFIED ANSWERS.
How to prove S is an independent set? - correct answer --S has
exactly 1 vertex per clause
-Both x₁ and x₁' are not in S.
-|S| = m = g
What are the claims of 3SAT reduction to Independent Set? -
correct answer -- 3SAT input, f, has a satisfying assignment <==>
G has an independent set of size ≥ g
- g = m = # of clauses
For the above implication, what is the forward proof? - correct
answer -Given the 3SAT input and a satisfying assignment, show
that G has an independent set of size ≥ g.
-For each clause C, take 1 of the satisfied literals and add to the
set S
-S has 1 vertex per clause.
, For the above implication, what is the reverse proof? - correct
answer -Given an independent set of size ≥ g, show that f has a
satisfying assignment.
-IS has 1 vertex per clause. Each vertex is satisfying assignment.
-Set that vertex to true.
-Every clause is now satisfied
What problems are known NP-Hard? - correct answer -1. Max-
Independent-Set problem.
What problems are known NP-Complete? - correct answer -1.
Max-Independent-Set
2. Clique
3. Vertex Cover
4. SAT
5. 3SAT
6. Independent Set
What problems are known NP? - correct answer -
