Homework #7 Solution


Category: Tag:


  1. 1. (6 pts) Let X and Y be two decision problem Suppose  we know that X reduces to Y in polynomial time. Which of the following can we infer? Give a YES/NO answer.


  1. a. If Y is NP-complete then so is X. b.    If X is NP-complete then so is Y.
  2. c. If Y is NP-complete and X is in NP then X is NP-compl


  1. d. If X is NP-complete and Y is in NP then Y is NP-compl e.    If X is in P, then Y is in P.
  2. f. If Y is in P, then X is in P.


  1. 2. (4 pts) Consider the problem  COMPOSITE: given an integer y, does y have any factors other than one and itself? For this exercise, you may assume that COMPOSITE is in NP, and you will be comparing  it to the well-known NP-complete problem SUBSET-SUM: given a set S of n integers  and an integer target t, is there a subset of S whose sum is exactly t?  Clearly explain whether or not each of the following statements  follows from that fact that COMPOSITE  is in NP and SUBSET -SUM is NP-complete:




  1. b. If there is an O(n3) algorithm for SUBSET-SUM, then there is a polynomial time algorithm  f or



  1. c. If there is a polynomial algorithm  for COMPOSITE, then P = NP.


  1. d. If P ¹ NP, then no problem  in NP can be solved in polynomial tim


  1. 3. (8 pts) A Hamiltonian path in a graph is a simple path that visits every vertex exactly onc  Prove that HAM-PATH  = { (G, u, v ): there is a Hamiltonian  path from u to v in G }  is NP-complete.  You may use the fact that HAM-CYCLE is NP-complete.


  1. 4. (12 pts) K-COLOR. Given a graph G = (V,E), a k-coloring is a function c: V -> {1, 2, … , k} such that c(u) ¹ c(v) for every edge (u,v) Î E. In other words the number  1, 2, .., k represent  the k colors and adjacent vertices must have different color  The decision problem K-COLOR asks if a graph can be colored with

at most K colors.


  1. a. The 2-COLOR decision problem is in P.  Describe  an efficient algorithm  to determine  if a graph has a 2-coloring.  What is the running  time of your algorithm?



  1. b. It is known that the 3-COLOR decision problem is NP-complete by using a reduction from SAT.

Use the fact that 3-COLOR is NP-complete to prove that 4-COLOR is NP-complete.

error: Content is protected !!