CSCI 570 HW 10

Description

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)

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.

Problem 3 (25 pts)

Consider a modified SAT problem, SAT’ in which given a CNF formula having m clauses and n variables x₁, x₂, . . . , x_n, 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.

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.

Practice Problems

Problem 5 (25 pts)

(Kleinberg and Tardos, Chapter 8, Exercise 5)

Consider a set A = {a₁, . . . , a_n} and a collection B₁, B₂, . . . , B_m of subsets of A (i.e., B_i ⊆ A for each i).

We say that a set H ⊆ A is a hitting set for the collection B₁, B₂, . . . , B_m if H contains at least one element from each B_i—that is, if H ∩ B_i is not empty for each i (so H “hits” all the sets B_i).

We now define the Hitting Set Problem as follows. We are given a set A = {a₁, . . . , a_n}, a collection B₁, B₂, . . . , B_m of subsets of A, and a number k. We are asked: Is there a hitting set H ⊆ A for B₁, B₂, . . . , B_m so that the size of H is at most k?

Prove that Hitting Set is NP-complete.

5