\documentclass{article}
\pagestyle{empty}

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

\noindent
This assignment is due by the end of the day Wed., Nov. 21, 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
In the study of NP-completeness we focus on ``decision problems,'' which differ from standard
search problems in that we are only required to answer a yes/no question about the input.
In practice, of course, we usually want to solve the search variations of these decision
problems.  In this exercise you'll show that the search variations of several decision
problems  are really no harder than
the decision version.  You'll do this by reducing the search problem to the decision problem.
Your reductions should be polynomial-time.


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

\vspace{.1 in}

For each decision problem above do the following:
\begin{enumerate}
\item
Give a yes-instance.
\item
Give a no-instance.
\item
Show the problem is in NP.
\end{enumerate} 


\item 
The Largest Common Subgraph problem is defined as follows. 
\begin{description} 
\item[Input:]   
Graphs $G_1$ and $G_2$ and integer $k$, 
\item[Question:] 
Is there a graph $G$ containing at least $k$ edges that is a subgraph 
of both $G_1$ and $G_2$. 
\end{description} 
\begin{enumerate} 
\item 
Give a Yes-instance of LCS. 
\item 
Give a No-instance of LCS. 
\item 
Cast this problem as a search problem.  Show that the search 
problem is polynomial-time equivalent to the decision problem. 
\item 
Show that LCS is in NP. 
\item 
Show that LCS is NP-complete by giving a reduction from one of 
the NP-complete problems described in problem 1. 
\end{enumerate} 
\item 
Repeat the above exercise for the Minimum Sum of Squares problem defined 
below. 
\begin{description} 
\item[Input:] 
A set $A$ of integers and two additional integers $K$ and $J$. 
\item[Question:] 
Can the elements of $A$ be partitioned into $K$ disjoint sets $A_1, A_2, \ldots, A_K$ 
such that  
$\sum_{i=1}^K (\sum_{s \in A_i} s)^2 \le J$? 
\end{description} 
\item 
Repeat the previous exercise for the Steiner Tree in Graphs problem defined below. 
(Hint:  Reduce from Vertex Cover.) 
\begin{description} 
\item[Input:] 
A graph $G$, a subset $R$ of the vertices of $G$, and an integer $K$. 
\item[Question:] 
Is there a subtree (not necessarily a spanning tree) of $G$ that includes 
the vertices $R$ and at most $K$ edges? 
\end{description}  
 

\end{enumerate}
  

\end{document}
