\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Spring 2004\\
\rm
Homework 12a\\
Due on 4/22/04 (beginning of class)\\
\end{center}
\begin{enumerate}
\item {\bf [20 Points] HITTING SET!}

First, the gratuitous story: The Computer Science
Department at The Western Institute of Technology
(T.W.I.T.) has 5 faculty members, Dr. I. ``Theo'' Rize,
Dr. I. Dutu, Dr. Sam E. Heer, Dr. Mia Thue, and Dr. Juan
More.  Each professor serves on a number of committees.
The Polynomial Time Algorithms Committee consists of
Professors Rize, Dutu, and More.  The NP-Completeness
Committee consists of Professors Dutu, Heer, and Thue.
Finally, the Other Stuff Committee consists of Professors
Thue and More.  The Dean would like to convene a meeting
in which the number of computer scientists invited is
minimized (she can't stand their bad CS jokes!) but each
committee is represented by at least one of its members.
For example, inviting Professors Thue and More would be a
solution in this case.

The Dean has formulated this problem as the following
general problem (known to computer scientists as the
Hitting Set Problem): We are given a set $S$ (the set of
professors) and a collection, $C$, of subsets of $S$ (the
set of committees).  A hitting set for $C$ is a subset
$S'\subseteq S$ such that $S'$ contains at least one
element from each subset in $C$.  The Hitting Set
optimization problem is to find the smallest hitting set.


\begin{enumerate}
\item 
Formulate the Hitting Set decision problem corresponding
to the optimization problem described above.



\item 
In this part of the problem, you will prove that the
Hitting Set decision problem is NP-complete.

\begin{enumerate}
\item 
The first part of proving NP-completeness is to show that
Hitting Set is in the class NP.  Briefly explain why this
is true.
		


\item
Next, we need to give a reduction from some known
NP-complete problem to the Hitting Set (HS) Problem.
Describe a reduction from the Vertex Cover (VC) Problem.
			


\item 
Next, explain why this reduction can be performed in
polynomial time.
			

			
\item
Finally, prove that your reduction is correct.  That is,
you need to show that the answer to an instance of VC is
true if and only if (that requires two separate proofs!)
the answer to the constructed HS problem is true.
			




\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{document}
