CS 325 - Homework 7

CS 325 - Homework 7
1. (6 pts) Let X and Y be two decision problems. Suppose we know that X reduces to Y in polynomial
time. Which of the following can we infer? Give a YES/NO answer.
a. If Y is NP-complete then so is X.
b. If X is NP-complete then so is Y.
c. If Y is NP-complete and X is in NP then X is NP-complete.
d. If X is NP-complete and Y is in NP then Y is NP-complete.
e. If X is in P, then Y is in P.
f. If Y is in P, then X is in P.
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:
a. SUBSET-SUM ≤p COMPOSITE.
b. If there is an O(n
3
) algorithm for SUBSET-SUM, then there is a polynomial time algorithm for
COMPOSITE.
c. If there is a polynomial algorithm for COMPOSITE, then P = NP.
d. If P  NP, then no problem in NP can be solved in polynomial time.
3. (8 pts) A Hamiltonian path in a graph is a simple path that visits every vertex exactly once. 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.
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 colors. The decision problem K-COLOR asks if a graph can be colored with
at most K colors.
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?
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.