\documentclass{article}
%\usepackage{}

\begin{document}


\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Fall 2000}\\
\vspace{.3 in}
{\large Assignment 13}
\end{center}

\vspace{.2 in}
This assignment is due by the start of class on Wed., Nov. 29.  
You should work in a group of 2-3 in which at least one person is
taking TheoComp and one person is not.
You should submit one solution for your group.  Be sure to include
the names of all group members.


\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 search problems.
For each of the problems described below give a polynomial-time reduction
from the search problem to the decision problem.

\begin{description}

\item[Vertex Cover:]
A vertex cover of a graph $G$ is a subset of vertices $W$ such that
every edge of $G$ is incident to some vertex in $W$.

\noindent {\bf Input:}  A graph $G$ and integer $k$\\
\noindent {\bf Question:}  Does $G$ have a vertex cover of size at most $k$?

\noindent {\bf Input:} A graph $G$ \\
\noindent {\bf Search Output:}  A smallest vertex cover 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-SAT:]
A 3-CNF formula is a boolean formula in conjunctive normal form (the ``and'' of
several ``or'' clauses) in which
each clause has 3 or fewer literals.  
A 3-CNF formula is ``satisfiable'' if there is a truth assignment for the
underlying variables that causes the formula to evaluate to true.

\noindent {\bf Input:}  A boolean formula ${\cal F}$\\
\noindent {\bf Question:}  Is ${\cal F}$ satisfiable?

\noindent {\bf Input:}  A boolean formula ${\cal F}$\\
\noindent {\bf Search Output:}  A satisfying assignment if
${\cal F}$ is satisfiable and otherwise "Not satisfiable"



\end{description}

\item 

Show that 3-coloring is NP-complete by showing (a) it is in NP and
(b) it is NP-hard.  For part (b) give a reduction from the NP-complete
problem 4-coloring,
which is described as follows.

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

Note that a 4-coloring is the obvious extension of 3-coloring;  can
we assign colors from the set $\{$red, blue, green, yellow $\}$ so that
the endpoints of each edge are colored differently.

\item

Let $G$ be a digraph.  A Grundy numbering of $G$ is a labeling of
the vertices of $G$ as follows.
The label of vertex $v$ must be the smallest non-negative integer that
is not used as a label for a vertex pointed to by $v$.  In other words,
$v$'s label must be the smallest integer in
the set $\{0,1,\ldots \} -L$, where  
if $L$ is the set of labels of vertices that have
in-edges from $v$.  Not all digraphs have valid Grundy numbering.


\noindent {\bf Input:}  A digraph $G$ \\
\noindent {\bf Question:}  Does $G$ have a Grundy numbering?

\begin{enumerate}
\item
Show that Grundy numbering is in NP.
\item
Suppose $G$ is a simple cycle.  Give necessary and sufficient conditions
for $G$ to have a Grundy numbering.
\item
Suppose $G$ is a simple cycle that does not have a Grundy numbering.
Show how to add one and one edges to $G$ to yield a 
graph $G'$ that does have a valid Grundy numbering. 
(Do not change any existing edges.  The result will not
be a simple cycle.)
\item
Show that Grundy numbering is NP-complete by giving a reduction from 3-SAT.
(Parts (b) and (c) should be helpful.)
\end{enumerate}
 



\end{enumerate}
  

\end{document}
