\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2003\\
\rm
Homework 12b\\
Due on 12/9/03 (in class)\\
\end{center}
\begin{enumerate}
\item \emph{This homework set is quite challenging.  Please start early and please come
to office hours.}
In this homework set  you will prove that several problems are NP-complete.
Recall that proving NP-completeness has several parts:  
First you will need to prove that the
problem is in NP (which is usually easy).  
Next, you must describe a reduction from a known
NP-complete problem to this problem and explain why the reduction can be
performed in polynomial time.  
Finally, you must show that the answer to the problem on the
left-hand side of the reduction operator $\leq_{p}$ is true if
and only if the answer to the
problem on the right-hand side of the reduction
operator is true.  Be sure to write out your NP-completeness
proofs carefully and precisely!
\item \textbf {[20 Points] More on ILP!}  
In class we proved that Integer Linear Programming
(ILP) is NP-complete.  Our reduction was from 3SAT.  In this
problem you will prove that ILP is NP-complete using two different
reductions.  You do not need to show that ILP is in NP (we
already argued that in class).  You need only give a reduction, 
prove its correctness (remember, this is an ``if and only if'' proof), 
and explain why the reduction can be done in polynomial time.
\begin{enumerate}
\item Show that ILP is NP-complete using a reduction from Vertex Cover.



\item Show that ILP is NP-complete using a reduction from Subset Sum. 



\end{enumerate}

\item {\bf [20 Points] SPAM is NP-Complete!}
It's true!  Here's the story:
My-I'm-Soft has just released it's new product ``Portholes 1987'' and
Gill Bates has decided to celebrate by throwing a big party for his employees.
Unfortunately, many of the employees at My-I'm-Soft
do not get along with one another\footnote{The famous social satirist 
Tom Lehrer once said ``There are people in this world who do not love
one another and I {\bf HATE} people like that!''}.  
Gill would like to invite as many employees to the party as possible
such that no two partygoers dislike one another.
This is known as the {\bf S}electing {\bf P}artygoers {\bf A}t 
{\bf M}y-I'm-Soft ({\bf SPAM}) Problem.

Given is 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.  In the optimization problem, we wish to find the largest subset $S \subseteq E$
such that for every pair of employees $e_{k}, e_{\ell} \in S$, $(e_k, e_{\ell}) \not \in H$. 

\begin{enumerate}
\item Formulate the SPAM problem as a decision problem.



\item Prove that the SPAM decision problem is NP-complete. ({\em Note:}  
Use one of 3SAT, Vertex Cover, Independent Set, or Clique in your reduction.)  



\end{enumerate}
\item \textbf{[25 Points] The Kernel!}
Consider a directed graph $G=(V,E)$.  A \emph{kernel} for graph $G$
is a subset $K$ of the vertices such that:
        \begin{enumerate}
                \item Every vertex in $V$ is either in the kernel $K$
                or has an incoming edge from some vertex in the
                kernel.  (Formally, ``$\forall v \in V$, $v \in K$ or
                $\exists u \in K$ s.t. $(u,v) \in E$.'')

                \item There do not exist two vertices in the kernel $K$ with
                a directed edge between them.  
                (Formally, ``$\forall u, v \in K$, $(u,v) \notin E$
                and $(v,u) \notin E$.'')
                
        \end{enumerate}
Observe that the graph below has a kernel. (A set containing 
just one of the two vertices is a kernel.)

        \begin{figure}[htbp]
        \begin{center}
        %\includegraphics[height=0.5in]{hw11fig1.pdf}
        \epsfig{file=hw11fig1.eps,height=0.5in}
        \caption{This directed cycle has a kernel.}
        \end{center}
        \end{figure}

On the other hand, the graph in Figure~2 has no kernel.  (Take a look at the
definition of the kernel to make sure you see why.)

        \begin{figure}[htbp]
        \begin{center}
  	%\includegraphics[height=1in]{hw11fig2.pdf}
        \epsfig{file=hw11fig2.eps,height=0.5in}
        \caption{This directed cycle has no kernel.}
        \end{center}
        \end{figure}

The \textbf{Kernel Problem} is the following:  Given a directed
graph $G=(V,E)$, does $G$ have a kernel?  Prove that the Kernel
Problem is NP-complete.  (Hint:  Perform a reduction from 3SAT 
and use the graphs in Figures 1 and 2 as the gadgets.)











\end{enumerate}
\end{document}
