\documentclass{article}
\pagestyle{empty}

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

\noindent
This assignment is due by the start of class on Thursday, April 12.  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 100 points (65 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[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
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} 



\end{enumerate}
  

\end{document}
