\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref,graphicx,xcolor}
\newcommand{\eps}{\varepsilon}
\newcommand{\fig}[2]{\begin{center}\includegraphics[scale=#2]{#1.pdf}\end{center}}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2020)\\
{\Large Homework 11} (due Apr 30 Thursday at 10am)
\end{center}
\medskip\noindent
{\bf Instructions:} As in previous homeworks.
See \href{http://courses.grainger.illinois.edu/cs374/sp2020/secure/A/old_hw11.pdf}{Old HW 11} for tips and examples on how to write NP-completeness proofs.
\begin{description}
\bigskip
\item[Problem 11.1:]
Given an undirected graph $G$, we want to decide whether $G$
contains a spanning tree where every node has degree at most 4.
Prove that this problem is NP-complete.
[Hint: you may assume that the {\sc Hamiltonian Path} problem is NP-complete.]
\bigskip
\item[Problem 11.2:]
We need to schedule final exams for $N$ classes. We want to minimize the number of days, but don't want any students to take more than 2 exams on a single day.
One way to formulate this problem is as follows:
There are $M$ students, and
for each $j=1,\ldots,M$, we are given a set $S_j\subseteq \{1,\ldots,N\}$ of the classes that student $j$ is taking. %, with $|S_j|\le 5$.
We are also given an integer $D$.
We want to decide whether there exists a function $f:\{1,\ldots,N\}\rightarrow \{1,\ldots,D\}$ such that
for every $j$ and $k$, the number of elements in $\{x\in S_j\mid
f(x)=k\}$ is at most 2.
Prove that this problem is NP-complete.
[Hint: you may assume that {\sc 3-Coloring} is NP-complete.
Observe that if we create 4 copies of a vertex $v$ and $D=3$, then two copies of $v$ must have
the same $f$ value. For each edge $uv$, create a constant number of sets (of size 3 or 4)\ldots]
\bigskip
\item[Problem 11.3:]
Consider the following version of the {\sc Crossword-Puzzle} problem:
\begin{quote}
{\em Input\/}: $A_1,\ldots,A_m,B_1,\ldots,B_n$, where each $A_i$
is a finite set of length-$n$ strings and each $B_j$ is a finite set of
length-$m$ strings, over a finite alphabet $\Sigma$.\\[3pt]
{\em Output\/}: ``yes'' iff there exists an $m\times n$ table $T$ of symbols such that
for each $i=1,\ldots,m$, the $i$-th row of $T$ is a string in the set $A_i$,
and for each $j=1,\ldots,n$, the $j$-th column of $T$ is a string in the set $B_j$.
\end{quote}
Example: on the input $A_1=\{\texttt{CAT}, \texttt{DOG}\}$, $A_2=\{\texttt{CAT},
\texttt{APE}, \texttt{AGO}\}$,
$A_3=\{\texttt{BAD}, \texttt{BEE}\}$, $B_1= \{\texttt{CAB}, \texttt{DAB}\}$,
$B_2=\{\texttt{APE}, \texttt{EGG}\}$, and $B_3= \{\texttt{GOD}, \texttt{TEE}\}$,
the answer is yes, with the following solution $T$:
\begin{quote}\begin{verbatim}
CAT
APE
BEE
\end{verbatim}\end{quote}
Prove that {\sc Crossword-Puzzle} is NP-complete.
[Hint: reduce from 3SAT\@.
Given a 3CNF formula $F$ with variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots, C_m$,
let $b_j$ be the length-$m$ binary string (over $\Sigma=\{0,1\}$) such that the $i$-th bit is 1 iff $x_j$ appears in $C_i$,
and let $b_j'$ be the length-$m$ binary string such that the $i$-th bit is 1 iff
$\overline{x_j}$ appears in $C_i$. Define $B_j=\{b_j,b_j'\}$, which contains 2
strings. Now define $A_i$ to contain 7 appropriately chosen strings\ldots]
\end{description}
\end{document}