\documentclass[12pt]{article}
\newcommand{\AND}{\wedge}
\newcommand{\OR}{\vee}
\newcommand{\NOT}[1]{\overline{#1}}

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

\begin{document}
\begin{center}
\bf
Algorithms, Section 2 \\
Spring 2003\\
\rm
Homework 12b \\
Due Tuesday, April 29\\
\end{center}

\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!

\begin{enumerate}

\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:
Millisoft 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 Millisoft
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}illisoft ({\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{[15 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.)

 \item \textbf{[25 Points] 2SAT!}  Recall that 2SAT is just like 3SAT
except that every clause in a 2SAT instance contains the disjunction of
exactly two variables.  While 3SAT is NP-complete, 2SAT can be solved by
efficient algorithms.  In class, we mentioned that the \emph{resolution}
algorithm from CS 80 can be used to solve 2SAT.  In this problem,
we will see that 2SAT can be solved using graph algorithms instead. 
Amazing but true!  (\emph{Note:} We use the notation $\NOT{x}$ to denote
the negation of variable $x$.)

\begin{enumerate}
  \item Consider the following instance of 2SAT:
  \[
     (x_1 \OR x_2) \AND (x_1 \OR \NOT{x_2}) \AND (\NOT{x_1} \OR x_2)
  \]
  Show that this instance is satisfiable by giving a satisfying assignment for the variables.

  \item Now consider the following instance of 2SAT:
  \[
     (x_1 \OR x_2) \AND (x_1 \OR \NOT{x_2}) \AND (\NOT{x_1} \OR x_2) \AND (\NOT{x_1} \OR \NOT{x_2} )
  \]
  Explain briefly why this instance of 2SAT is not satisfiable.

  \item Given an instance of 2SAT, let's construct a corresponding
directed graph as follows:
  For each variable $x_i$ that appears in the 2SAT instance, construct a \emph{pair} of
  vertices, one labeled $x_i$ and the other labeled $\NOT{x_i}$.
  For every clause of the form $(a  \OR b)$ in the 2SAT instance (where $a$ and $b$ are
variables which may or may not be negated), place a directed
 edge from vertex $\NOT{a}$ to vertex $b$ and also a directed edge from 
 vertex $\NOT{b}$ to vertex $a$. 
 For example, if we had a clause $(x_1 \OR \NOT{x_3})$ then $a= x_1$ and $b = \NOT{x_3}$. 
Therefore, we would place a directed edge
 from vertex $\NOT{x_1}$ to vertex $\NOT{x_3}$ as well as a directed edge from 
 vertex $x_3$ to vertex $x_1$.  In this example, you should interpret the edge from vertex
$\NOT{x_1}$ to vertex
 $\NOT{x_3}$ to mean ``if $\NOT{x_1}$ is true (that is, $x_1$ is false) then $\NOT{x_3}$ must be
true.''
 Similarly, the edge from vertex $x_3$ to the vertex $x_1$ is interpreted as ``if $x_3$ is true
then $x_1$ must be true.''

 Construct this directed graph for the 2SAT instance in part (a).  This graph
      should contain 4 vertices 6 edges.  Notice that there is no path from vertex $x_1$ to
      vertex $\NOT{x_1}$.   

   \item Notice that in the graph you constructed there is a path from vertex
$\NOT{x_1}$
      to vertex $x_1$.  Clearly explain why \emph{the existence of this path} implies that a
satisfying assignment
     for this instance of 2SAT cannot have $\NOT{x_1}$ be \textbf{true} (that is, $x_1$ cannot
     be \textbf{false}).  Be very clear and precise about your reasoning here. 
    \item Notice that there does \emph{not} exist a path in this graph from vertex $x_1$ to vertex
   $\NOT{x_1}$.   Notice also that in your satisfying assignment for this instance, $x_1$ was
   set to \textbf{true}.   Clearly explain why this graph tells us that $x_1$ should be assigned
   \textbf{true} if the instance has any hope of being satisfied.

  \item What does the graph tell you about the value that should be assigned to variable $x_2$?  Explain.

  \item Now, construct the graph for the 2SAT problem in part (b).  What property does this
graph have that forces you to conclude that the 2SAT instance is not satisfiable?  Be precise.

  \item Next, write down a conjecture that starts as follows:  ``A 2SAT instance is satisfiable if and only if the corresponding directed graph has the property that blah, blah, blah.''
Fill in the ``blah, blah, blah'' with mathematically precise language.

  \item Now, prove your conjecture.  This is the main part of this problem (it's also worth most
of the points!) and will take a few paragraphs to prove.  Note that it is an ``if and only if''
proof, which means that there are two things to show.  In this proof, the fact that two edges
were introduced for each clause will be absolutely critical.  You'll need to use this fact!

  \item Now, describe an algorithm to determine whether or not a 2SAT instance is satisfiable. 
  What is the running time of your algorithm?  

  \end{enumerate}


\end{enumerate}
\end{document}

