\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{url}


\setlength{\parindent}{0pt}
\setlength{\parskip}{8pt}

\title{CS140 - Assignment 11\\\small{Due: Sunday,  Apr. 30th at 8pm}}
\author{}
\date{}

\begin{document}

\maketitle

\begin{center}
\includegraphics[scale=0.7]{figures/npc.jpg}
\footnotesize{http://asfarian.wordpress.com/2011/01/11/np-completeness/}
\end{center}


\noindent For any NP-completeness reduction you need to:
  \begin{itemize}
  \item Show that the decision problem is in NP
  \item Describe a reduction, making sure to
    \begin{itemize}
    \item Argue that the reduction can be done in polynomial time.
    \item Explain why the reduction ``works'' (ie, why a ``yes'' $\rightarrow$ ``yes'' and a ``no''  $\rightarrow$ ``no'' or, more often, why a ``yes'' $\rightarrow$ ``yes'' and a ``yes'' $\leftarrow$ ``yes'')
    \end{itemize}
  \end{itemize}
  
\begin{enumerate}
	
\item \textbf{[4 points]} Most of the NP-Complete problems we looked at in class were \emph{decision} problems, in that we were trying to decide if a condition was true or not (e.g. ``does the graph have a clique of size $k$?'').  However, for real problems we often would want to solve the max/min problem (often called the \emph{search} problem), for example ``what is the size of the largest clique in the graph?''.

I claim that in most situations if you can solve the decision problem in polynomial time then you can solve the search problem in polynomial time.  Prove that this is true for the \textsc{CLIQUE} problem, i.e., assume you have a polynomial-time solver for the decision problem and show how you can use this to solve the search problem.

\item \textbf{[10 points]} Zero sum

ZERO-SUM is the following problem:  Given a set of integers $S$ is there a subset that sums to 0?  

Prove that ZERO-SUM is \textbf{NP-Complete}.

\begin{enumerate}
\item Show ZERO-SUM is in NP.
\item Prove that ZERO-SUM is NP-complete.
\end{enumerate}

\item \textbf{[10 points]} Getting along

In this problem you are given a set $E = \{e_1, \dots, e_n \}$ of $n$
employees and a set $H$ which consists of pairs of employees $(e_{i},
e_{j})$ such that employees $e_i$ and $e_j$ do not get along.  Does a subset $S \subseteq
E$ where $|S| = m$ such that for every pair of employees $e_{k}, e_{\ell} \in S$,
$(e_k, e_{\ell}) \not \in H$.

\begin{enumerate}
\item Show that this problem is in NP.
\item Use {\sc Clique} to prove that the problem is
  NP-complete.
\end{enumerate}

\item \textbf{[11 points]} Hitting Set

Assume you are given a
set $S$, and a collection $C$ of subsets of $S$.  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 optimization problem asks
for the size of the smallest hitting set.  

\vspace*{.1cm}

You can think of $S$ as being a set of students, and of the $C$ as a
collection of subsets of $S$ where all the students in a subset share
some skill (eg, ``good writer'', ``entertaining'', ``can code for 3
days straight'', ``has access to free pizza'', and so on).  The
hitting set, then, would be a study group whose members collectively
possess every skill.  The search problem asks how to minimize
the size of the group.

\begin{enumerate}
\item Formulate the {\sc Hitting-Set} decision problem corresponding
  to the search problem described above.
\item Show that {\sc Hitting-Set} is in NP.
\item Prove that {\sc Hitting-Set} is NP-complete.  
\end{enumerate}




\end{enumerate}

\end{document}
