## 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.