Problem 1 (25pts)
Consider the partial satisfiability problem, denoted as 3-Sat(α). We are given a collection of k clauses, each of which contains exactly three literals, and we are asked to determine whether there is an assignment of true/false values to the literals such that at least αk clauses will be true. Note that 3-Sat(1) is exactly the 3-SAT problem from lecture.
Prove that 3-Sat(15/16) is NP-complete.
Hint: If x, y, and z are literals, there are eight possible clauses containing them: (x ∨ y ∨z), (!x ∨y ∨z), (x∨!y ∨z), (x ∨y∨!z), (!x∨!y ∨z), (!x ∨y∨!z), (x∨!y∨!z), (!x∨!y∨!z)
1
Problem 2 (25 pts)
Given a graph G = (V, E) and two integers k, m, the Dense Subgraph Problem is to find a subset V ′ of V , whose size is at most k and are connected by at least m edges. Prove that the Dense Subgraph Problem is NP-Complete.
2
Problem 3 (25 pts)
Consider a modified SAT problem, SAT’ in which given a CNF formula having m clauses and n variables x1, x2, . . . , xn, the output is YES if there is an assignment to the variables such that exactly m − 2 clauses are satisfied, and NO otherwise. Prove that SAT’ is NP-Complete.
3
Problem 4 (25 pts)
Show that Vertex Cover is still NP-complete even when all vertices in the graph are re-stricted to have even degree.
4
Practice Problems
Problem 5 (25 pts)
(Kleinberg and Tardos, Chapter 8, Exercise 5)
Consider a set A = {a1, . . . , an} and a collection B1, B2, . . . , Bm of subsets of A (i.e., Bi ⊆ A for each i).
We say that a set H ⊆ A is a hitting set for the collection B1, B2, . . . , Bm if H contains at least one element from each Bi—that is, if H ∩ Bi is not empty for each i (so H “hits” all the sets Bi).
We now define the Hitting Set Problem as follows. We are given a set A = {a1, . . . , an}, a collection B1, B2, . . . , Bm of subsets of A, and a number k. We are asked: Is there a hitting set H ⊆ A for B1, B2, . . . , Bm so that the size of H is at most k?
Prove that Hitting Set is NP-complete.
5
