\documentclass{article}
\input{6045preamble}
\newcommand{\spacechar}{\sqcup}
\newcommand{\length}[1]{\left \vert #1 \right \vert}

\begin{document}
\homework{9}{Prof. Ron Rivest}{Due: 8 May 2002}{}

\begin{problem}
 Consider the \emph{firehouse} problem: Given a graph $G$, a distance
 $d$, and a limit $f$ on the number of firehouses, can you find $f$ or
 less nodes in $G$ on which to put firehouses such that every node in
 $G$ is distance $d$ or less from some firehouse? (The distance, in
 this context, is the number of edges in the shortest path.) More
 formally:
 $$\mathit{FIREHOUSE} = \cset{\rep{G,d,f}}{\parbox{3in}{there exist
     $f$ nodes in $G$ so that every node in $G$ is distance $d$ from one}}$$
 Show that $\mathit{FIREHOUSE}$ is $\NP$-complete.
\end{problem}

\begin{problem}
  Consider the language
  $$\mathit{HALFCLIQUE} = \cset{\rep{G}}{G \mbox{ has a
      $\frac{\length{G}}{2}$-clique}}$$ 
  Show that $\mathit{HALFCLIQUE}$ is $\NP$-complete.
\end{problem}

\begin{problem}
  \textbf{(Note: this problem is worth 20 points.)} A $k$-coloring of
  an undirected graph $G=(V, E)$ is a function $c: V \rightarrow
  \set{1,2,\ldots k}$ such that $c(u) \not = c(v)$ for every $(u,v)
  \in E$. That is, it is a way to color the nodes of $G$ one of $k$
  different colors, so that no edge touches two nodes of the same
  color. Consider the language:
  $$\mbox{\emph{3-}}\mathit{COLOR} = \cset{\rep{G}}{G \mbox{ has a
      3-coloring}}$$
  In this problem, you will show that this language
  is $\NP$-complete.  (This is also Problem 7.34.) This reduction is
  tricker than those we've asked you to do before, so we are providing
  some guidance:

  To prove that $\mbox{\emph{3-}}\mathit{COLOR}$ is $\NP$-complete, we use a
  reduction from $\mbox{\emph{3-}}\mathit{SAT}$. Given a formula $\phi$ of $m$
  clauses on $n$ variables $x_1$, $x_2$, \ldots $x_n$, we construct a
  graphs $G=(V,E)$ as follows. The set of nodes $V$ consists of a
  vertex for each variable, a vertex for the negation of each
  variable, 5 vertices for each clause, and 3 special vertices:
  $\mathit{TRUE}$, $\mathit{FALSE}$, and $\mathit{RED}$. The edges of
  the graph are of two types: ``literal'' edges that are independent
  of the clauses, and ``clause'' edges that depend on the clauses. The
  literal edges form a triangle on the special vertices and also form
  a triangle on $x_1$, $\overline{x_i}$, and $\mathit{RED}$ for $i =
  1$, $2$, \ldots $n$.
  \begin{enumerate}
  \item Argue that in any 3-coloring $c$ of a graph containing the
    literal edges, exactly one of a variable and its negation colored
    $c(\mathit{TRUE})$ and the other is colored
    $c(\mathit{FALSE})$. Argue that for any truth assignment for
    $\phi$, there is a 3-coloring of the graph containing just the
    literal edges.
  \end{enumerate}
  The widget shown in Figure \ref{fig:widget} is used to force the
  condition corresponding to a clause $(x \vee y \vee z)$. Each clause
  requires a unique copy of the 5 vertices that are blank in the
  figure; they connect as shown to the literals of the clause and the
  special vertex $\mathit{TRUE}$.
  \begin{enumerate}
    \stepcounter{enumi}
  \item Argue that if each of $x$, $y$ and $z$ is colored
    $c(\mathit{TRUE})$ or $c(\mathit{FALSE})$, then the widget is
    3-colorable iff one of $x$, $y$, and $z$ is colored
    $c(\mathit{TRUE})$. 
  \item Prove that $\mbox{\emph{3-}}\mathit{COLOR}$ is $\NP$-complete. 
  \end{enumerate}

  \begin{figure}[tb]
    \begin{center}
      \input{hw9-fig.tex}
      \caption{A widget}
      \label{fig:widget}
    \end{center}
  \end{figure}


\end{problem}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
% LocalWords:  Undecidability
