\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage{graphicx,fancyhdr,algorithm,algorithmic}
\usepackage[space]{grffile}
\usepackage{titlesec}
\usepackage{multicol}
\usepackage{enumitem} 
\usepackage{tikz}
\usepackage{tikz-qtree}
\usetikzlibrary{arrows,automata}


\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\firstword}[1]{\textsf{{\color{darkred}{\raisebox{.3em}{#1}}}}}
\newcommand{\secondword}[1]{\textsf{{\color{niceblue}{#1}}}}


\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{question}{Problem}

\newenvironment{solution}{\bigskip\noindent{\it Solution.}  \ignorespaces}{\hfill\qed}

\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
\urlstyle{same}
\PassOptionsToPackage{hyphens}{url}


\newcommand{\homework}[6]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS256:~Algorithm Design and Analysis \hfill #1} }
       \vspace{6mm}
       \hbox to 6.28in { {\Large \hfill #2 \normalsize{(#3)}  \hfill} }
       \vspace{6mm}
     \hbox to 6.28in { {\it Instructor: #4 \hfill  } }
   }
   }
   \end{center}
   \markboth{#1}{#1}
   \vspace*{4mm}
}

\begin{document}
\homework{Spring 2024}{Assignment 7}{due 05/08/2024 }{Sam McCauley}{}

\begin{question}
	Suppose an extra-terrestrial being gave you a magic blackbox that can solve $\mathsf{HAMILTONIAN\textnormal{-}CYCLE}$,
which is an NP-complete problem, with a worst-case running time of $O(n^8)$, where $n$ denotes the number of vertices in the graph.  

Assuming that our magic box actually works, which of the following can we conclude?  Give a brief justification with your response.
\begin{enumerate}[noitemsep, nolistsep, label = (\alph*)]
     \item All problems in NP are solvable in polynomial time.
    \item All NP-hard problems are solvable in polynomial time.
    \item All NP-complete problems are solvable in $O(n^8)$ time.
\end{enumerate}
\end{question}

\begin{solution}

\end{solution} 

\newpage
\section*{NP-Completeness}


\paragraph{A Note of NP-completeness proofs.}  
The next three questions will ask you to prove that a given problem $X$ is NP Complete.  A complete solution would include the following: 
\begin{itemize}[leftmargin=*]
\item Problem $X$ is in NP:  you don't have to give a ``tight bound'' on the verification complexity just briefly reason why it can be achieved in time polynomial in the input size.
\item State a {\em known} NP hard problem $Y$ from class that you will use to prove $X$ is also NP hard
\item Show that $Y \leq_p X$.  Remember to:
  \begin{itemize}
  \item Prove that the reduction is correct by arguing both the ``if'' and ``only if'' directions
  \item Argue that your reduction is polynomial time (again,
you are don't have to give an efficient bound, just that is is polynomial time, so this piece should 1-2 sentences)
  \end{itemize}
\end{itemize}


Students often ask ``Which problems can I use as the \emph{known} NP-hard problem?'' You can use any of the
problems whose NP-hardness was established in class, or Chapter 8 of Kleinberg Tardos or Chapter 12 of Erickson. Here is a (not necessarily complete) list:
\begin{multicols}{2}
\begin{enumerate}[noitemsep, label = (\alph*)]
    \item Independent Set
    \item Vertex Cover
    \item Set Cover
    \item Clique
\end{enumerate}
\columnbreak
\begin{itemize}[noitemsep]
    \item[(e)] Circuit-SAT/SAT/3-SAT
    \item[(f)] Hamiltonian Cycle/Path 
    \item[(g)] Graph 3-color 
    \item[(h)] Subset-Sum
\end{itemize}
\end{multicols}

\bigskip
\bigskip

\begin{question} (KT 8.5)
Consider a set $A = \{a_1, \ldots, a_n\}$ and a collection $B_1, B_2, \ldots, B_m$ of subsets of $A$ (i.e., $B_i \subseteq A$ for each $i$). We say that $H \subseteq A$ is a hitting set for the collection $B_1, \ldots, B_m$ if $H$ contains at least one element from each $B_i$---that is, if $H \cap B_i$ is not empty for each $i$ (so $H$ ``hits'' all the sets $B_i$).

We now define the \emph{Hitting Set Problem} as follows: given $A = \{a_1, \ldots, a_n\}$, a collection $B_1, B_2, \ldots, B_m$ of subsets of $A$, and a number $k$, is there a hitting set $H \subseteq A$ for $B_1, B_2, \ldots B_m$ such that size of $H$ is at most $k$. Prove that Hitting Set is NP complete.
\end{question}

\begin{solution}

\end{solution}

\newpage
\begin{question} 
Suppose you are in charge of forming a student committee at Williams. Given a set 
of $n$ students and a compatibility function 
that maps every student to a subset of students they are compatible with, you must choose $k$ students to be in the committee such that each student in the committee is compatible with everyone else. 
\begin{enumerate}[noitemsep, nolistsep, label = (\alph*)]
    \item Show that the problem of determining whether it is possible to form such a committee is NP-complete.
    \item Suppose you were forced to pick a given student as the president of your committee. That is, you must always include this person (and each person in the committee should still be compatible with the president and everyone else). Show that this new version is still NP-complete, by modifying your reduction from part (a). \newline 
\end{enumerate}

\textit{Note:} You need to use a polynomial-time reduction as defined in class: you need to map ``yes''-instances to ``yes''-instances, and ``no''-instances to ``no''-instances.  Any answers of the type: ``choose each vertex one at a time as president and call the oracle $n$ times'' are not correct polynomial time reductions..
\end{question}

\begin{solution}

\end{solution}

\newpage

\begin{question} (KT 8.28)
The following is a version of the Independent Set problem. You are
given an undirected connected graph $G = (V, E)$ and an integer $k$. For this problem, we will call a set $I \subseteq V$ \emph{strongly independent} if for any two nodes $v, u \in I$, the edge $(v, u)$ does not belong
to $E$, and there is also no path of $2$ edges from $u$ to $v$, i.e., there is no node $w$ such
that both $(u, w) \in E$ and $(w, v) \in E$. The Strongly Independent Set problem is to decide whether $G$ has a strongly independent set of size at least $k$. Prove that the Strongly
Independent Set problem is NP-complete.
\end{question}

\begin{solution}
\end{solution}


\newpage

\begin{question} ({\bf Extra Credit:  5 points})


  Define the $\mathsf{ODD-SUBSET-SUM-RANGE}$ problem as follows.  Given $n$ odd numbers $s_1,\ldots s_n$, and two target integers $T_1$ and $T_2$, determine if there exists a subset of numbers that adds up to a value between $T_1$ and $T_2$.\footnote{``Between'' is inclusive, so a subset adding up to exactly $T_1$ or $T_2$ indicates a yes instance.}

  Prove that $\mathsf{ODD-SUBSET-SUM-RANGE}$ is NP-hard.

\end{question}

\begin{solution}
\end{solution}

\newpage
\end{document}


