\documentclass{article}
\pagestyle{empty}

\begin{document}
\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Fall 2001}\\
\vspace{.3 in}
{\large Assignment 11}
\end{center}

\noindent
This assignment is due by the end of the day Wed., Dec. 5, 2001.  You may collaborate
with your classmates to complete this assignment but you must reference your collaborators.  In addition,
you must do your own write-up.  This assignment is worth 200 points (100 points if handwritten).  
\begin{enumerate}

\item
For each of the following problems give a polynomial-time reduction from the
search variant to the decision problem.


\begin{description}
\item[Dominating Set:]
A dominating set of a graph $G$ is a subset of vertices $W$ such that
every vertex of $G$ is either in $W$ or is adjacent to a vertex in $W$.
 
\noindent {\bf Input:}  A graph $G$ and integer $k$\\
\noindent {\bf Question:} Does $G$ have a dominating set of size at most $k$/

\noindent {\bf Input:}  A graph $G$ \\
\noindent {\bf Search Output:} A smallest dominating set of $G$

\item[Partition:]
AKA the grocery bag problem.  You might ask yourself whether or not
our algorithm for the grocery bag problem means we've proven $P=NP$?
 
\noindent {\bf Input:}  A set of integers $S$\\
\noindent {\bf Question:} Can $S$ be partitioned into two sets,
$S_1$ and $S_2$, such that $\sum_{s \in S_1} s = \sum_{s \in S_2} s$?

\noindent {\bf Input:}  A set of integers $S$\\
\noindent {\bf Search Output:} A partition of $S$ into two sets, $S_1$ and
$S_2$, such that $| \sum_{s \in S_1} s - \sum_{s \in S_2} s|$ is minimized.


\item[Clique:]
A clique in a graph $G$ is a subset of vertices $W$ such that
each pair of vertices in $W$ is connected by an edge in $G$.

\noindent{\bf Input:} A graph $G$ and an integer $k$ \\
\noindent {\bf Question:}  Does $G$ have a clique of size at least $k$?

\noindent{\bf Input:} A graph $G$\\
\noindent {\bf Search Output:} A largest clique of $G$

\item[Hamiltonian Cycle:]
A Hamiltonian cycle of a graph $G$ is a simple cycle that includes
every vertex.

\noindent{\bf Input:}  A graph $G$\\
\noindent{\bf Question:}  Does $G$ contain a Hamiltonian cycle?

\noindent{\bf Input:}  A graph $G$\\
\noindent{\bf Search Output:} A Hamiltonian cycle of $G$ if one exists and otherwise "No Hamiltonian cycle"

\item[3-coloring:]
A 3-coloring of graph $G$ is an assignment of a unique color in
$\{$red, blue, green $\}$ to each vertex of $G$ so that the endpoints of each edge are colored
differently.

\noindent {\bf Input:}  A graph $G$ \\
\noindent {\bf Question:}  Can $G$ be 3-colored?

\noindent {\bf Input:}  A graph $G$ \\
\noindent {\bf Search Output:} A 3-coloring of $G$ if one exists and otherwise "No 3-coloring"


\item[3 Dimensional Matching:]
Let $U, V,$ and $W$ be disjoint sets such that $||U||=||V||=||W||=q$. 
Let $C$ be a subset of $U \times V \times W$;  in other words $C$
is a collection of triples $(u,v,w)$, where $u \in U$, $v \in V$, $w\in W$.
A 3 dimensional matching is a subset of $C$ such that each element of
$U, V$ and $W$ occurs in exactly one triple of $C$.


\noindent {\bf Input:}  Disjoint sets $U$, $V$, and $W$, where $||U||=||V||=||W||=q$ and a subset $C$ of $U \times V \times W$.\\
\noindent {\bf Question:}  Does $C$ contain a three-dimensional matching?

\noindent {\bf Input:}  Disjoint sets $U$, $V$, and $W$, where $||U||=||V||=||W||=q$ and a subset $C$ of $U \times V \times W$.\\
\noindent {\bf Search Output:} A three-dimensional matching from $C$, if one exists,
and otherwise a statement that one does not exit.




\end{description}
 
\item 
The Isomorphic Subtree problem is defined as follows. 
 
\begin{description} 
\item[Input:] 
A graph $G$ and a tree $T$. 
\item[Question:] 
Is there a subset $W$ of vertices of $G$ such that the subgraph of $G$ 
induced by $W$ is exactly $T$? 
\end{description} 
\begin{enumerate} 
\item 
Show that the Isomorphic Subtree problem is in NP. 
\item 
Give a yes-instance of the problem. 
\item 
Give a no-instance of the problem. 
\item 
Show that the Isomorphic Subtree problem is NP-hard by giving a polynomial-time 
reduction from one of the standard NP-hard problems we've used in class.
\begin{enumerate} 
\item 
Which NP-hard problem will you use? 
\item 
Given an input X of the selected problem, how do you construct the input $G, T$ for 
the Isomorphic Subtree problem?  Show that the reduction can be done in polynomial-time. 
\item 
Suppose the input X of the selected problem is a yes-instance.  Prove that the instance 
$G,T$ of Isomorphic Subtree created by your reduction is also a yes-instance. 
\item 
Suppose that the instance $G,T$ of Isomorphic Subtree created by your reduction is a yes-instance. 
Prove that the original instance $X$ of the selected problem is also a yes-instance. 
\end{enumerate} 
\end{enumerate} 
 
\item 
The Bipartite Cover Problem is defined as follows. 
\begin{description} 
\item[Input:] 
A bipartite graph $G=(U,V,E)$ and an integer $K$. 
\item[Question:] 
Is there a subset $W \subseteq U$ such that $||W|| \le K$ and 
every vertex in $V$ is adjacent to some vertex in $W$? 
\end{description} 
\begin{enumerate} 
\item 
Show that the Bipartite Cover problem is in NP. 
\item 
A search version of this problem takes as input a bipartite graph $G=(U,V)$ and outputs 
a smallest subset $W\subset U$ such that every vertex in $V$ is adjacent to some vertex in 
$U$.  Give a polynomial-time reduction from this search problem to the decision problem. 
\item 
Show that the Bipartite Cover problem is NP-hard by giving a polynomial-time 
reduction from one of the standard NP-hard problems we've used in class.
\begin{enumerate} 
\item 
Which NP-hard problem will you use? 
\item 
Given an input X of the selected problem, how do you construct the input $G, K$ for 
the Bipartite Cover problem?  Show that the reduction can be done in polynomial-time. 
\item 
Suppose the input X of the selected problem is a yes-instance.  Prove that the instance 
$G,K$ of Bipartite Cover created by your reduction is also a yes-instance. 
\item 
Suppose that the instance $G,T$ of Bipartite Cover created by your reduction is a yes-instance. 
Prove that the original instance $X$ of the selected problem is also a yes-instance. 
\end{enumerate} 
\end{enumerate} 
\item 
The Shortest Common Supersequence  problem is defined as follows. 
\begin{description} 
\item[Input:] 
A set of strings $S=\{s_1, s_2, \ldots, s_n\}$ over an alphabet $\Sigma$ and an integer $K$. 
\item[Question:] 
Is there a string of length at most $K$ that contains each $s \in S$ as a subsequence? 
\end{description} 
For example $abcd$ is a shortest string that contains $ac$ and $bd$ as subsequences.   
(Other strings work as well.) 
\begin{enumerate} 
\item 
Find a shortest string that contains $aba$, $cb$, and $caa$ as subsequences. 
\item 
Show that the Shortest Common Supersequence problem is in NP. 
\item 
Show that the Shortest Common Supersequence problem is NP-hard by giving a reduction 
from Vertex Cover. 
\begin{enumerate} 
\item 
Given an instance $G=(V,E),K$ of Vertex Cover, show how to create the instance $S,K'$ of 
Shortest Common Supersequence. 
\item 
Suppose that $G,K$ is a yes-instance of Vertex Cover.  Prove that the instance $S,K'$ 
of Shortest Common Supersequence created by your reduction is also a yes-instance. 
\item 
Suppose that the instance $S,K'$ of Shortest Common Supersequence produced by your reduction 
is a yes-instance.  Prove that the input $G,K$ is a yes-instance of Vertex Cover. 
\end{enumerate} 
\end{enumerate} 
\end{enumerate} 
 
\end{document} 

\end{enumerate}
  

\end{document}
