CSC 491

We finished talking about the theory of NP-completeness; if you like that material, check out CSC 489 Theory of Computation, which Dr. Kanj is teaching next quarter..

Submission: you can submit the homework to me either by hardcopy in class or email it to me.

1. [k-colorability, 25pt] Assuming that 3-colorability is NP-complete, show that k-colorability
is NP-complete for any k >= 3. **Also** show that 2-colorability is in P.

2. [2CNF, 15pt] 2CNF-SAT is the problem of deciding whether a formula in 2CNF is satisfiable; 2CNF means, the formula is in conjunctive normal form, and each
clause contains at most two literals. Show that 2CNF-SAT can be solved in
polynomial time. *Hint:* clauses with one literal are easy; if you have a
clause with two literals, such as (x v y) think of it as an implication, that
is, (not-x -> y). Now rephrase the problem as a problem on graphs.

3. [Hamiltonian Path, 15pt] Show that the Hamiltonian Path problem is NP-complete. HP = {(G,u,v): there is a Hamiltonian Path from u to v}.

4. [Longest Path, 15pt] Show that the Longest Path Problem is NP-complete, where LP = {(G,u,v,k): there is a path of length at least k from u to v in G}.

5. [Extra Credit] Show that the coin changing problem is NP-complete, that
is: CC = {(d_{1}, d_{2}, ..., d_{n}, v, k): can you make
change for amount v using at most k coins chosen from denominations {d_{1},
d_{2}, ..., d_{n}})?}. *Hint*: reduce from subset-sum.

Marcus Schaefer

Last updated: October 20th, 2006.