CS 341, Fall 2020
A. Lubiw, A. Storjohann
ASSIGNMENT 9
DUE: Wednesday November 25, 5 PM. DO NOT COPY. ACKNOWLEDGE YOUR SOURCES. Please read http://www.student.cs.uwaterloo.ca/~cs341 for general instructions and policies.
Exercises. The following exercises are for practice only. You may ask about them in office hours. Do not hand them in.
1. Let X, Y, Z be decision problems. Show that if there is a polynomial time many-one reduction from X to Y , and from Y to Z, then there is a polynomial time many-one reduction from X to Z.
Problems. To be handed in.
1. [10 marks] P and NP. A Boolean formula is in disjunctive normal form (DNF) if the formula
is an OR of terms, where each term is an AND of literals. For example, (x1 ∧¬x2 ∧x3)∨(¬x1 ∧x4).
The DNF-SAT problem is to decide whether a DNF formula is satisfiable, i.e., whether there is an assignment of True/False to the variables that makes the formula True.
(a) [4 marks] Give a polynomial time algorithm for DNF-SAT. You may just describe your algorithm in English (no pseudocode required), and briefly say why it is correct and polynomial time. Suppose that the input DNF formula has m terms and n variables. Assume that no literal is repeated in a term, so each term has at most 2n literals.
(b) [6 marks] What is wrong with the following argument that P = NP?
Given a 3-SAT formula, use the distributive law to convert it to disjunctive normal form. (Recall that you saw the distributive law in CS 245, or remind yourself of it here: https: //en.wikipedia.org/wiki/Distributive_property#Propositional_logic.) For ex- ample:
(x1 ∧¬x2 ∧x3)∨(¬x1 ∧x2)≡(x1 ∨x2)∧(¬x2 ∨¬x1)∧(x3 ∨¬x1)∧(x3 ∨x2)
Then run the algorithm from part (a) to decide, in polynomial time, whether the DNF formula is satisfiable. This is a polynomial time algorithm to solve 3-SAT. Since 3-SAT is NP-complete, therefore P = NP.
2. [10 marks] NP-completeness “proofs”. Consider the following degree-bounded indepen- dent set problem:
2d-IND-SET
Input: An undirected graph G = (V, E) where every vertex has degree ≤ 2, and a number k.
Output: Does G have an independent set of size ≥ k? (YES or NO)
1
(a) [4 marks] What is wrong with the following proof that 2d-IND-SET is NP-complete? It is easy to show that 2d-IND-SET lies in NP. (More details should be given here, but this is not what’s wrong with the proof.) Next, we will show that 2d-IND-SET ≤P IND-SET using a many-one reduction.
Assume we have a polynomial time algorithm for IND-SET. We make an algorithm for 2d-IND-SET as follows. Given inputs G = (V,E) and k for 2d-IND-SET, we leave the inputs unchanged, and run the IND-SET algorithm on G, k, and return the answer. This algorithm correctly decides if G has an independent set of size ≥ k, and it runs in polynomial time. Since IND-SET is NP-complete, this proves that 2d-IND-SET is NP-complete.
(b) [3 marks] Prove that 2d-IND-SET lies in P. Hint: Draw some example graphs that have maximum degree 2.
(c) [3 marks] The 3d-IND-SET problem is defined in a similar way, but now every vertex has degree ≤ 3. It is a fact that 3d-IND-SET is NP-complete. Now consider the 3d-CLIQUE problem:
3d-CLIQUE
Input: An undirected graph G = (V, E) where every vertex has degree ≤ 3, and a number k.
Output: Does G have a clique of size ≥ k? (YES or NO)
What is wrong with the following proof that 3d-CLIQUE is NP-complete?
First of all, it’s easy to show that 3d-CLIQUE is in NP. (More details should be given
here, but this is not what’s wrong with the proof.) Next, we will show that 3d-IND-
SET ≤P 3d-CLIQUE. Suppose we have a polynomial time algorithm for 3d-CLIQUE.
Then to solve 3d-IND-SET on an input graph G and number k, we construct Gc, the
complement of G, and we run the 3d-CLIQUE algorithm on Gc and k and return its
answer. Observe that G has an independent set of size ≥ k iff Gc has a clique of size
≥ k. Thus, the algorithm is correct. Furthermore, it runs in polynomial time because
we can construct Gc in polynomial time, and Gc has at most n edges so an algorithm 2
that runs in time polynomial in the size of Gc is polynomial in the size of G.
Since 3d-IND-SET is NP-complete (a given fact) therefore 3d-CLIQUE is NP-complete.
Challenge Questions. This is for fun and enrichment only. Do not hand it in. 1. Prove that 3d-CLIQUE lies in P.
2