Problem Set #1

CS 255
due February 21, 2001

  1. Find the 3SAT instance constructed by the reduction algorithm from SAT for the SAT instance
    {{x}, {x'y}, {xy'z'}, {wxyz}, {v'w'xyz'}, {uvwxyz'}}

  2. Exercise 36.4-5, p946 of the text.

  3. Show carefully that the Integer Knapsack Problem is in NP.

  4. An instance of the Degree Constrained Spanning Tree problem is an undirected graph G and a positive integer k. The question is whether there is a spanning tree T for G such that the degree of each vertex in the tree is no greater than k. Show that this problem is NP-complete. You may use any problem stated in class to be NP-complete for your transformation.