Description
1. Let X and Y be two decision problems. Suppose we know that X reduces to Y. Which of the following
can we infer? Explain
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. X and Y can’t both be NP-complete.
f. If X is in P, then Y is in P.
g. If Y is in P, then X is in P.
2. 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. Two well-known NP-complete problems are 3-SAT and TSP, the traveling salesman problem. The
2-SAT problem is a SAT variant in which each clause contains at most two literals. 2-SAT is known to
have a polynomial-time algorithm. Is each of the following statements true or false? Justify your
answer.
a. 3-SAT ≤p TSP.
b. If P NP, then 3-SAT ≤p 2-SAT.
c. If P NP, then no NP-complete problem can be solved in polynomial time.
4. LONG-PATH is the problem of, given (G, u, v, k) where G is a graph, u and v vertices and k an integer,
determining if there is a simple path in G from u to v of length at least k. Show that LONG-PATH is NPcomplete.
CS 325 – Homework 4
5. Graph-Coloring. Mapmakers try to use as few colors as possible when coloring countries on a map, as
long as no two countries that share a border have the same color. We can model this problem with an
undirected graph G = (V,E) in which each vertex represents a country and vertices whose respective
countries share a border are adjacent. 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 graph-coloring problem is to determine the minimum number
of colors needed to color a given graph.
a. State the graph-coloring problem as a decision problem K-COLOR. Show that your decision
problem is solvable in polynomial time if and only of the graph-coloring problem is solvable
in polynomial time.
b. It has been proven that 3-COLOR 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.