\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{graphics,epsfig}

\begin{document}
\begin{center}
\bf
Algorithms, Section 2\\
Spring 2003\\
\rm
Homework 12a\\
Due Thursday, April 24\\
\end{center}

\begin{enumerate}

\item {\bf [10 Points] Professor Lai and $NP$!}
        \begin{enumerate}
                \item Professor I. Lai from P.I.T. claims that if
                $P_{1}$ and $P_{2}$ are any two problems in $NP$
                such that $P_{1} \leq_{p} P_{2}$, then $P_{2} \leq_{p} P_{1}$.
                Prove that this would imply that $P = NP$.

                \item Professor Lai is studying an interesting
                problem called the Polygon Intersection Testing problem
                (PIT).  He claims to have proved that PIT is NP-complete
                by showing that PIT is in $NP$ and that 
                $\mbox{PIT} \leq_{p} \mbox{VC}$ (VC is the Vertex Cover
                problem).  Is this a valid approach for proving
                that PIT is NP-complete?  Explain.
        \end{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 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 problem.  Describe a 
			reduction from the Vertex Cover 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 VERTEX COVER is
			true if and only if (that requires two
			separate proofs!) the answer to the constructed
			HITTING SET problem is true.  
			\end{enumerate}
 \end{enumerate}


\end{enumerate}
\end{document}

