Homework 6 (assigned February 14, due February 20)

Reading: CLRS chapter 34.

Written assignment: Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.

"Do" Exercises (not to be handed in):

1. Exercise 34.4-1, page 1085.

2. Describe a polynomial-time reduction from CIRCUIT-SAT to SAT.

3. Exercise 34.4-2, page 1085.

4. Describe a polynomial-time reduction from SAT to 3SAT.

5. Exercise 34.4-3, page 1085.

6. A clique in an undirected graph G = (V, E) is a subset V ′ ⊆ V of vertices, each pair of which is connected by an edge in E; i.e., a clique is a complete subgraph of G. The CLIQUE problem is: given an undirected graph G and an integer g, find a set of ≥ g vertices such that all possible edges between them are present, or report that none exists.
   Prove that CLIQUE is NP-complete.
   • Show that CLIQUE ∈ NP.
   • Describe a polynomial-time reduction from INDEPENDENT-SET to CLIQUE.

7. A vertex cover of an undirected graph G = (V, E) is a subset V ′ ⊆ V such that if (u, v) ∈ E, then u ∈ V ′ and/or v ∈ V ′. The VERTEX COVER problem is: given an undirected graph G and an integer b, find a set of ≤ b vertices that cover every edge, or report that none exists.
   Prove that VERTEX-COVER is NP-complete.
   • Show that VERTEX-COVER ∈ NP.
   • Describe a polynomial-time reduction from INDEPENDENT-SET to VERTEX-COVER.

8. In the MAX-CUT problem, we are given an unweighted undirected graph G = (V, E). We define a cut (S, V − S) of G as a partition of V, and the weight of a cut as the number of edges crossing the cut. The goal is to find a cut of maximum weight. Prove that MAX-CUT is NP-complete.

9. Exercise 34.5-2, page 1101.

10. Problem 34-3, parts d, e, f, page 1103.

Problems (to be handed in):

1. The traveling salesman problem is the following:
   TSP
   Input: n vertices 1, …, n, a matrix of distances between the vertices; a buget b.
   Output: A tour (cycle) which passes through each vertex exactly once and has length ≤ b, if such a tour exists.
   The optimization version of this problem asks directly for the shortest tour.
   TSP-OPT
   Input: n vertices 1, …, n, a matrix of distances between the vertices.
   Output: The shortest tour (cycle) which passes through each vertex exactly once.
   Show that if TSP can be solved in polynomial time, then so can TSP-OPT. (5 points)

2. STINGY-SAT is the following problem: given a set of clauses in n variables x₁, …, x_n (each clause is a disjunction of literals x_i, ¬x_i), and an integer k, find a satisfying assignment in which at most k variables are true, if such an assignment exists. Prove that STINGY-SAT is NP-complete. (5 points)

3. Consider the CLIQUE problem restricted to graphs in which every vertex has degree at most 3. Call this problem CLIQUE-3.
   • Prove that CLIQUE-3 is in NP. (2 points)
   • It is true that the VERTEX COVER problem remains NP-complete even when restriced to graphs in which every vertex has degree at most 3. Call this problem VC-3. What is wrong with the following proof of NP-completeness for CLIQUE-3?
     We present a reduction from VC-3 to CLIQUE-3. Given a graph G = (V, E) with vertex degrees bounded by 3, and a parameter b, we create an instance of CLIQUE-3 by leaving the graph unchanged and switching the parameter to |V| − b. Now a subset C ⊆ V is a vertex cover in G if and only if the complementary set V − C is a clique in G. Therefore G has a vertex cover of size ≤ b if and only if it has a clique of size ≥ |V| − b. This proves the correctness of the reduction and, consequently, the NP-completeness of CLIQUE-3.
     (3 points)

4. In the EXACT 4SAT problem, the input is a set of clauses in n variables x₁, …, x_n, where each clause is a disjunction of exactly four literals, and such that each variable occurs at most once in each clause. The goal is to find a satisfying assignment, if one exists. Prove that EXACT 4SAT is NP-complete. (5 points)

5. We know that the shortest-path problem can be solved very efficiently, but what about the longest-path problem? In the LONGEST-PATH problem we are given a graph G = (V, E) with nonnegative edge weights and two distinguished vertices s and t, along with a goal g. We are asked to find a path from s to t with total weight at least g. We require the path to be simple, containing no repeated vertices.
   • Prove that LONGEST-PATH is NP-complete. (7 points)
   • Show that LONGEST-PATH is in P for DAGs. (3 points)

6. A boolean formula is in disjunctive normal form (or DNF) if it consists of a disjunction of several clauses, each of which is the conjunction of one or more literals. For example, the formula
   (¬x ∧ y ∧ ¬z) ∨ (y ∧ z) ∨ (x ∧ ¬y ∧ ¬z)
   is in disjunctive normal form. The DNF-SAT problem asks, given a boolean formula in disjunctive normal form, whether that formula is satisfiable.
   • Describe a polynomial-time algorithm to solve DNF-SAT. (5 points)
   • What is the error in the following argument that P = NP?
     Suppose we are given a boolean formula in conjunctive normal form with at most three literals per clause, and we want to know if it is satisfiable. We can use the distributive law to construct an equivalent formula in disjunctive normal form. For example,
               (x ∨ y ∨ ¬z) ∧ (¬x ∨ ¬y) ⇔ (x ∧ ¬y) ∨ (¬x ∧ y) ∨ (¬x ∧ ¬z) ∨ (¬y ∧ ¬z).
     Now we can use the algorithm from the first part of this problem to determine, in polynomial time, whether the resulting DNF formula is satisfiable. We have just solved 3SAT in polynomial time. Since 3SAT is NP-complete, we must conclude that P = NP.
     (5 points)