CSE 417 Assignment #5
Winter 2000

Due: Friday, March 10, 2000.

Read the Manber text, sections 10.1 and chapter 11.

  1. A triangle in a undirected graph G is a triple of vertices {u,v,w} of G such that all three of (u,v), (v,w), (u,w) are edges in G. Show that the problem TRIANGLE={< G > | G contains a triangle} is in P.

  2. Manber's text: page 370, problem 11.1

  3. Here you will show that 4-SAT is NP-complete

    1. Show that the problem 4-SAT is in NP.

    2. Show a polynomial-time mapping reduction from 3-SAT to 4-SAT.

  4. Use the fact that 3-color is NP-complete to prove that the following problem: COLOR={< G,k >| G is k-colorable} is NP-complete.

  5. Why is the following not a proof that P is different from NP? We can decide the SAT problem using the following algorithm: Given a formula F in n variables, try all 2n truth assignments and see if there is any assignment that makes F true. If there is one, then accept, else reject. This algorithm takes at least 2n time in the worst case and since 2n is not polynomial in n, this is not polynomial time.

  6. (Bonus) Manber's text: page 371, problem 11.13