% ---------
% Compile with “pdflatex hw0”.
% --------
%!TEX TS-program = pdflatex
%!TEX encoding = UTF-8 Unicode
\documentclass[11pt]{article}
\usepackage{jeffe,handout,graphicx,mathtools}
\usepackage[mathletters]{ucs} % define text Greek letters; load BEFORE inputenc
\usepackage[utf8]{inputenc} % Allow some non-ASCII Unicode in source
\usepackage{fourier-orns}
\usepackage{eucal,wasysym}
\usepackage{enumerate}
\usepackage{stmaryrd}
\usepackage{CJKutf8}
\def\Japanese#1{\begin{CJK*}{UTF8}{min}#1\end{CJK*}}
\hidesolutions
% ======================================================
\begin{document}
\headers{CS 473}{Homework 9 (due April 19)}{Spring 2016}
\thispagestyle{empty}
\begin{center}
\Large\textbf{CS 473 \,\decosix\, Spring 2016}%
\\
\LARGE \textbf{\decothreeleft~ Homework 9 ~\decothreeright}
\\[0.5ex]
\large Due Tuesday, April 19, 2016, at 8pm
\end{center}
\hrule
\medskip\noindent
For problems that ask to prove that a given problem $X$ is NP-hard, a full-credit solution requires the following components:
\begin{itemize}\itemsep0pt
\item
Specify a known {NP}-hard problem $Y$, taken from the problems listed in the notes.
\item
Describe a polynomial-time algorithm for $Y$, using a black-box polynomial-time algorithm for $X$ as a subroutine. Most {NP}-hardness reductions have the following form: Given an arbitrary instance of $Y$, describe how to transform it into an instance of $X$, pass this instance to a black-box algorithm for $X$, and finally, describe how to transform the output of the black-box subroutine to the final output. A cartoon with boxes may be helpful.
\item
Prove that your reduction is correct. As usual, correctness proofs for {NP}-hardness reductions usually have two components (“one for each f”).
\end{itemize}
\hrule
\bigskip
\begin{enumerate}
\parindent 1.5em \itemsep 3ex plus 0.1fil
%----------------------------------------------------------------------
\item
Consider the following solitaire game. The puzzle consists of an $n\times m$ grid of squares, where each square may be empty, occupied by a red stone, or occupied by a blue stone. The goal of the puzzle is to remove some of the given stones so that the remaining stones satisfy two conditions: (1) every row contains at least one stone, and (2) no column contains stones of both colors. For some initial configurations of stones, reaching this goal is impossible.
\begin{center}\footnotesize\sffamily
\begin{tabular}{c@{\qquad\qquad}c}
\includegraphics[scale=0.4]{../notes/Fig/solitaire}
&
\includegraphics[scale=0.4]{../notes/Fig/solitaire2}
\\[-1ex]
A solvable puzzle and one of its many solutions. & An unsolvable puzzle.
\end{tabular}
\end{center}
Prove that it is NP-hard to determine, given an initial configuration of red and blue stones, whether the puzzle can be solved.
%----------------------------------------------------------------------
\item
Everyone’s having a wonderful time at the party you’re throwing, but now it's time to line up for \href{https://www.youtube.com/watch?v=M8xtOinmByo}{\EMPH{The Algorithm March (\Japanese{アルゴリズムこうしん}})}! This dance was originally developed by the Japanese comedy duo Itsumo Kokokara (\hbox{\Japanese{いつもここから}}) for the children's television show \href{http://www.nhk.or.jp/kids/program/pitagora.html}{Pythagora\-Switch (\hbox{\Japanese{ピタゴラスイッチ}})}. The Algorithm March is performed by a line of people; each person in line starts a specific sequence of movements one measure later than the person directly in front of them. Thus, the march is the dance equivalent of a musical round or canon, like “Row Row Row Your Boat”.\footnote{\Japanese{そろそろおわりかな。そろそろおわりかな。そろそろおわりかな。}} Proper etiquette dictates that each marcher must know the person directly in front of them in line, lest a minor mistake during lead to horrible embarrassment between strangers.
Suppose you are given a complete list of which people at your party know each other. Prove that it is {NP}-hard to determine the largest number of party-goers that can participate in the Algorithm March. You may assume without loss of generality that there are no ninjas at your party.
\end{enumerate}
\end{document}