CSCI 570 – Summer 2020 – HW 6 Solutions
1 Graded Problems
1. State True/False.
• Assume P . Let A and B be decision problems. If A ∈ NPC and
A ≤p B, then B.
Answer: False. If B were in P , then A ≤p B would imply A ∈ P .
Since A ∈ NPC,∀D ∈ NP,D ≤p A. Since A ≤p B, this implies
∀D ∈ NP,D ∈ P which contradicts P 6= NP .
• If someone proves P = NP , then it would imply that every decision
problem can be solved in polynomial time.
Answer: False. Halting is a counter example.
2. Given an n bit positive integer, the problem is to decide if it is composite.
Here the problem size is n. Is this decision problem in NP?
Answer: Yes. For every “yes” instance (the number is composite), a
factor of the number is a certificate. Verification proceeds by dividing the
number by the factor and making sure that the reminder is zero. The
factor is at most n bits and verification can be done in time polynomial
in n. Thus deciding if a number is composite is in NP .
3. State True/False. Assume you have an algorithm that given a 3-SAT
instance, decides in polynomial time if it has a satisfying assignment.
Then you can build a polynomial time algorithm that finds a satisfying
assignment(if it exists) to a given 3-SAT instance.
Answer: True. Pick the first literal in the first clause (call it x1). Replace
x1 with 1 (or 0) and ¬x1 with 0 (or 1) in every mention of x1 and ¬x1
in the satisfying problem. Run the deciding algorithm. If the problem
is still satisfiable we go to the next literal (if needed in the next clause)
and we do the same process until all the literals are assigned value. If the
problem is not satisfiable, this implies that we have set the literal with a
wrong value. Then we change the value from 1 to 0 (or 0 to 1) and again
we continue with rest of the literals.
4. A variation of the satisfiability problem is the MIN 2-SAT problem. The
goal in the MIN 2-SAT problem is to find a truth assignment that mini-
1
mizes the number of satisfied clauses. Give the best approximation algo-
rithm that you can find for the problem.
Answer: We assume that no clause contains a variable as well as the
complement of the variable. (Such clauses are satisfied regardless of the
truth assignment used.) We give a 2-approximation algorithm as follows:
Let I be an instance of MINSAT consisting of the clause set CI and
variable set XI . Construct an auxiliary graph GI(VI , EI) corresponding
to I as follows. The node set VI is in one-to-one correspondence with the
clause set CI . For any two nodes vi and vj in VI , the edge (vi, vj) is in EI
if and only if the corresponding clauses ci and cj are such that there is a
variable x belongs to XI that appears in un-complemented form in ci and
complemented form in cj , or vice versa. To construct a truth assignment,
we construct an approximate vertex cover V ′ for GI such that |V ′ is at
most twice that of a minimum vertex cover for GI . Then construct a truth
assignment that causes all clauses in VI − V ′ to be false. (For a method
to find an approximate vertex cover, please refer to section 11.4 in the
textbook.)
5. Assume that you are given a polynomial time algorithm that decides if a
directed graph contains a Hamiltonian cycle. Describe a polynomial time
algorithm that given a directed graph that contains a Hamiltonian cycle,
lists a sequence of vertices (in order) that forms a Hamiltonian cycle.
Answer: Let G = (V,E) be the input graph. Let A be an algorithm
that decides if a given directed graph has a Hamiltonian cycle. Hence
A(G) = 1. Pick an edge e ∈ E and remove it from G to get a new graph
G. If A(G) = 1, then there exists a Hamiltonian cycle in G which is a
subgraph of G, set G = G. If A(G) = 0, then every Hamiltonian cycle
in G contains e. Put e back into G. Iterate the above three lines until
we are left with exactly |V | edges. Since after each step we are left with
a subgraph that contains a Hamiltonian cycle, at termination we are left
with the set of edges that forms a Hamiltonian cycle. Starting from an
edge, do a BFS to enumerate the edges of the Hamiltonian cycle in order.
6. State True/False. Let A be NP -complete, and B be NP -hard. Then,
A ≤p B.
Answer: True. A is NP-complete and thus, A ∈ NP . Then, since B is
NP-hard, we have A ≤p B by definition.
7. State True/False. If P = NP , then every NP -hard problem can be solved
in polynomial time.
Answer: False. If P = NP, only the NP-complete problems will be surely
polytime solvable (because they are in NP), but not necessarily all the
NP-hard problems.
2