\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi
\HomeworkStart%
{11} % Homework number
{15} % Week of semester submitted
{1.1} % Version
\HWInstructionsStd{}
\begin{questions}[start=31]
\RestoreIndent%
\item \OLDHWProblem{100}{Walk with me}{
\begin{questions}
\RestoreIndent%
\item \points{50} We are given a \emph{directed} graph
$\Graph$ with $n$ vertices and $m$ edges $(m\ge n)$, where
each vertex $v$ has a height $h(v)$. The \emph{cost} of
traversing an edge $(u,v)$ is $c(u,v) =|h(v) - h(u)|$. The
cost of a walk in $\Graph$ is the sum of the costs of edges
in the walk. Prove that finding the minimum cost walk that
visits all the vertices om $\Graph$ is \NPHard. (In a
walk, vertices and edges may be repeated, and the start and
end vertices may be different.)
\item \points{50} We are given a directed graph $\Graph$
with $n$ vertices and $m$ edges $(m\ge n)$, where each edge
$e$ has a set of colors $C(e) \subseteq \{1,...,k\}$. Prove
that deciding whether there exists a walk that uses all $k$
colors (i.e. the union of the sets of colors of the edges
of walk covers all colors.) is \NPHard. (Hint: Reduce from
Set Cover.)
% (You have seen this
% before. It was not \NPHard back then. It is now!)
% \item \points{50} We are given a undirected graph
% $\Graph$ with $n$ vertices
% and $m$ edges $(m\ge n)$, where each edge $e$ has a set
% of colors $C(e) \subseteq
% \{1,...,L\}$. Prove that deciding whether there exists
% a walk of at most $k$ edges that uses all $L$ colors is
% \NPHard.
\end{questions}
\HWInstructions{%
}% \medskip%
}{}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \OLDHWProblem{100}{Things are hard.}{%
\RestoreIndent%
\begin{questions}
\RestoreIndent%
\item \points{20} %
Suppose we have $n$ prisoners $P_1, \ldots, P_n$ that we
want to place in some disconnected blocks of a
prison. Each prisoner is assigned to one block, and
he/she will not be able to access other blocks. However,
some prisoners are bitter enemies (going all the way back
to kindergarten) and cannot be placed in the same block.
Given integers $n$ and $k$ and a list of enemies for each
of the $n$ prisoners, we want to determine whether $k$
blocks are sufficient to house all the prisoners? Prove
that this problem is \NPHard. You can safely assume that
every block has unbounded capacity.
\item \points{40} %
Let $\Graph$ be an arbitrary directed weighted graph with
$n$ vertices and $m$ edges such that no edge weight is
zero (weights can be positive or negative). Prove that
finding a {\it zero-length} (i.e., zero weight)
Hamiltonian cycle in $\Graph$ is \NPComplete.
\item \points{40} %
Consider the following {\bf X{}O} puzzle. You are given
an $n\times m$ grid of squares where each square has an
{\bf X}, an {\bf O} or is empty. Your goal is to erase
some of the {\bf X}s and {\bf O}s so that \smallskip%
\begin{compactenumi}[itemindent=0.5cm]
\item every row
contains at least one {\bf X} or one {\bf O}, and
\smallskip%
\item no
column contains both {\bf X} and {\bf O}.
\end{compactenumi}
\smallskip%
For some input grids, it is impossible to solve the
puzzle. The figure below shows two examples: a grid that
is solvable and a grid that is impossible to solve. Prove
that, given a grid, it is \NPHard to determine whether
the puzzle is solvable. (Hint: Reduce from 3SAT.)
\vskip 0.3in \centerline{\includegraphics[width=
0.9\linewidth]{figs/XO}} \vskip 1in
\end{questions}
}{}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \OLDHWProblem{100}{Fan, fan, fan.}%
{%
An undirected graph a \emphi{3-blade-fan} if it consists of
three cycles $C_1, C_2,$ and $C_3$ of $k$ nodes each and they
all share exactly one node. Hence, the graph has $3k-2$
nodes. The figure below shows a \emphi{3-blade-fan} of 16
nodes.
\centerline{\includegraphics{figs/fan_undirected}}
Given an undirected graph $\Graph$ with $n$ vertices and $m$
edges and an integer $k$, the FAN problem asks whether or not
there exists a subgraph of $\Graph$ which is a
\emphi{3-blade-fan}. Prove that FAN is \NPComplete.
}{}{}{}
\end{questions}
\HomeworkEnd{}