CSEP 590TU Assignment #6
Autumn 2003

Due: Wednesday, Nov 12, 2003.

Read sections 7.4-5 and 9.3 of Sipser's text. We will use section 9.3 for the proof of the Cook-Levin theorem rather than the proof in section 7.4 Next week we start Chapter 8.

Problems

  1. Consider a set A={a1,...,am} and a collection B1,...,Bn of subsets of A. (That is each Bi is a subset of A.) We say that a subset H of A is a hitting set for the collection B1,...,Bn if H contains at least one element from each Bi. (So H "hits" all the sets Bi.)
    Define HITTING-SET={<A,B1,...,Bn,k> | There is a hitting set in A of size k for B1,...,Bn}.
    Prove that HITTING-SET is NP-complete.

  2. For any k, define DEG-k-SPAN-TREE={<G> | G has a spanning tree with maximum degree at most k}.

    1. Show that DEG-2-SPAN-TREE is NP-complete.

    2. Use a reduction from DEG-2-SPAN-TREE to show that DEG-3-SPAN-TREE is also NP-complete.

    3. Generalize part (b) to show that DEG-k-SPAN-TREE is NP-complete for any integer of k>1.

  3. A dominating set of an undirected graph G is a subset D of vertices of G such that every vertex v of G is either in D or adjacent to a vertex in D. Define DOMINATING-SET={<G,k> | G is an undirected graph that has a dominating set of size at most k}.
    Prove that the DOMINATING-SET is NP-complete.
    HINT: Use a reduction based on Vertex Cover that replaces edges by triangles.

  4. Sipser's text problem 7.30 page 274. (Hint: If P=NP then there is a polynomial time algorithm for CLIQUE. Call this subroutine repeatedly with different inputs.)

  5. (Bonus) Sipser's text problem 7.22 page 273.

  6. (Bonus) Sipser's text problem 7.23 page 273.