# CSEP 590TU Assignment #6Autumn 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.