\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref,graphicx,xcolor}
\newcommand{\eps}{\varepsilon}
\newcommand{\fig}[2]{\begin{figure}[h]\begin{center}%
\includegraphics[scale=#2]{#1.pdf}\end{center}%
\end{figure}}
\newlength{\mylength}
\newcommand{\scratch}[1]{\makebox[0in][l]{#1}\settowidth{\mylength}{#1}{\color{red}\rule[.6ex]{\mylength}{1pt}}}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2024)\\
{\Large Homework 11} (due Apr 25 Thursday at 10am)
\end{center}
\medskip\noindent
{\bf Instructions:} As in previous homeworks. See also Past HW 11 for tips and examples of NP-hardness proofs.
\begin{description}
\bigskip
\item[Problem 11.1:]
Consider the following problem called {\sc Super-SAT}:
\begin{quote}
\emph{Input}: a CNF Boolean formula $F$ with $m$ clauses and $n$ variables.\\[2pt]
\emph{Output}: true iff there exists an assignment such that in each clause, strictly more than half
of its literals are true.
\end{quote}
\begin{enumerate}
\item[(a)] (10 pts) Prove that {\sc Super-SAT} is in NP.
\item[(b)] (90 pts) Prove that {\sc Super-SAT} is NP-hard, by reduction from the 3SAT problem.
Hint: given a 3CNF formula, create a new 5CNF formula\ldots
\end{enumerate}
\bigskip
\item[Problem 11.2:]
Consider the following problem called {\sc Connections}:
\begin{quote}
\emph{Input}: a set $X$ of $M$ elements, a collection of $N$ subsets $Y_1,\ldots,Y_N\subseteq X$,
and numbers $A$ and $B$ with $AB=M$.\\[2pt]
\emph{Output}: true iff there exists a partition of $X$ into $A$ disjoint subsets $Z_1,\ldots,Z_A$ each of size exactly $B$,
such that for each $i\in\{1,\ldots,A\}$, the subset $Z_i$ is contained in $Y_{j_i}$ for some $j_i\in\{1,\ldots,N\}$ (the $j_i$'s need not be distinct).
\end{quote}
For example: for $X=\{1,2,3,4,5,6,7,8,9\}$, subsets $\{1,4,7,8\}$, $\{2,3,5,7,9\}$, $\{2,5,7,8\}$, $\{1,2,5,6,7\}$,
and $A=B=3$, the answer is true (one feasible partition is $\{1,4,8\}$, $\{3,5,9\}$, $\{2,6,7\}$).
[Note: This is inspired by a word puzzle from the New York Times (no, it's not Wordle!).
The elements correspond to words,
each subset $Y_i$ corresponds to a potential category, and we want to form $A$ groups of $B$ words, such that each group fits in a common category; in the game, $A=B=4$ and $M=16$, but the subsets/categories are not given explicitly\ldots]
[For those who don't like games (but who doesn't?), a more serious motivation is in clustering large datasets into $A$ groups\ldots]
\begin{enumerate}
\item[(a)] (10 pts) Prove that {\sc Connections} is in NP.
\item[(b)] (90 pts) Prove that {\sc Connections} is NP-hard, by reduction from the vertex cover problem.
Recall that in the vertex cover (decision) problem, the input is an undirected graph $G=(V,E)$ and a number $K$,
and the output is true iff there exists a subset $S\subseteq V$ of $K$ vertices such that each edge $uv\in E$
has $u\in S$ or $v\in S$.
Hint: let the elements of $X$ correspond to the edges of the given graph; also add some number of extra ``dummy'' elements.
For each vertex $v$, create a subset containing all edges incident to $v$ together with all the dummy elements\ldots
\end{enumerate}
\end{description}
\end{document}