Graded
1. (20 pts) Consider the partial satisfiability problem, denoted as 3-Sat(α). We are given a collection of k clauses, each of which contains exactly three lit-erals, 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)
2. (20 pts) Consider modified SAT problem, SAT’ in which given a CNF formula having m clauses in 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 also NP-Complete.
3. (20 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.
Ungraded
4. (20 pts) (Modified from Textbook 8.16) Consider the problem of reasoning about the identity of a set from the size of its intersections with other sets. You are given a finite set U of size n, and a collection A1…Am of subsets of U. You are also given numbers c1 ..... cm, and numbers d1 ..… dm. The question is:
Does there exist a set X ⊂ U so that for each i = 1…m, the cardinality of X ∩ A is larger than ci but smaller than di? We will call this an instance of the Intersection Inference Problem, with input U, {Ai}, and {ci}, {di}. Prove that Intersection Inference is NP-complete.
1
5. (20 pts) (Textbook 8.28) The following is a version of the independent Set Problem. you are given a graph G = (V, E) and an integer k. For this problem,
we will call a set I ⊂ V strongly independent if, for any two nodes v, u ∈ I, the edge (v, u) does not belong to E, and there is also no path of two edges from u to v, that is, there is no node w such that both (u, w) ∈ E and (w, v) ∈ E. The Strongly independent Set Problem is to decide whether G has a strongly independent set of size at least k.
Prove that the Strongly independent Set Problem is NP-complete.
2
