CSE 417 Assignment #5
Winter 2001

Due: Friday, March 9, 2001.

1. Skiena's book, Problem 6-1, page 160.

2. Skiena's book, Problem 6-2, page 160.

3. Skiena's book, Problem 6-3, page 160.

4. 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 of determining if G contains a triangle is in P.

5. Use the fact that 3-COLOR is NP-complete to prove that the problem COLOR is NP-complete which asks, given an undirected graph and an integer k, can G be colored with at most k colors.

6. Why is the following not a proof that P is different from NP? We can decide the Satisfiability problem using the following algorithm: Given a formula F in n variables, try all 2ⁿ 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 2ⁿ time in the worst case and since 2ⁿ is not polynomial in n, this is not polynomial time.