CSEP 590TU Assignment #6
Autumn 2003
Due: Wednesday, Nov 12, 2003.
Read sections 7.45 and 9.3 of Sipser's text. We will use section 9.3 for
the proof of the CookLevin theorem rather than the proof in section 7.4
Next week we start Chapter 8.
Problems
 Consider a set A={a_{1},...,a_{m}} and a collection
B_{1},...,B_{n} of subsets of A. (That is each B_{i} is
a subset of A.)
We say that a subset H of A is a hitting set for the collection
B_{1},...,B_{n} if H contains at least one element from each
B_{i}. (So H "hits" all the sets B_{i}.)
Define
HITTINGSET={<A,B_{1},...,B_{n},k>  There is a hitting set in A of size k for B_{1},...,B_{n}}.
Prove that HITTINGSET is NPcomplete.
 For any k, define
DEGkSPANTREE={<G>  G has a spanning tree with maximum degree at most k}.
 Show that DEG2SPANTREE is NPcomplete.
 Use a reduction from DEG2SPANTREE to show that DEG3SPANTREE is
also NPcomplete.
 Generalize part (b) to show that DEGkSPANTREE is NPcomplete for
any integer of k>1.

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
DOMINATINGSET={<G,k>  G is an undirected graph that has a dominating set
of size at most k}.
Prove that the DOMINATINGSET is NPcomplete.
HINT: Use a reduction based on Vertex Cover that replaces edges by triangles.
 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.)
 (Bonus) Sipser's text problem 7.22 page 273.
 (Bonus) Sipser's text problem 7.23 page 273.