\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{fancybox}
\usepackage{graphicx}

\newcommand{\HC}{\textsf{\sc HamiltonCycle}}
\newcommand{\HP}{\textsf{\sc HamiltonPath}}
\newcommand{\TSAT}{\textsf{\sc 3Sat}}
\newcommand{\LT}{\textsf{\sc LosTabernacos}}
\newcommand{\VC}{\textsf{\sc VertexCover}}
\newcommand{\SC}{\textsf{\sc SetCover}}
\newcommand{\LP}{\textsf{\sc LongestPath}}

\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}

\begin{document} 

\begin{center} \Large\bf
COMP 3804 --- Assignment 4 
\end{center} 

\noindent {\bf Due:} Monday April 8, 23:59.

\vspace{0.5em}

\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
      Brightspace.

\begin{center}
\hfill\shadowbox{
  \begin{minipage}{.90\linewidth}
    {\textsf{Use the following format to name your file:
        \[ {\tt LastName\_StudentId\_a4.pdf}
        \]
      }}
  \end{minipage}
}
\end{center}
\item {\bf Late assignments will not be accepted. I will not reply to
      emails of the type ``my internet connection broke down at
      23:57'' or ``my scanner stopped working at 23:58'', or
      ``my dog ate my laptop charger''.}
\item You are encouraged to collaborate on assignments, but at the level
      of discussion only. When writing your solutions, you must do so
      in your own words.
\item Past experience has shown conclusively that those who do not put
      adequate effort into the assignments do not learn the material and
      have a probability near 1 of doing poorly on the exams.
\item When writing your solutions, you must follow the guidelines below.
      \begin{itemize}
      \item You must justify your answers.
      \item The answers should be concise, clear and neat.
      \item When presenting proofs, every step should be justified.
      \end{itemize}
\end{itemize}

\newpage 

\begin{question}
Write your name and student number.
\end{question}

\begin{question}
The \emph{set cover problem} is defined as follows:

\vspace{0.5em}

\begin{tabular}{rl}
   $\SC = \{ (S,n,A_1,A_2,\ldots,A_m,K) :$ & $S$ is a set of size $n$, 
               each $A_i$ is a subset of $S$, \\
                     & $\exists I \subseteq \{1,2,\ldots,m\}$ such that \\ 
                     & $|I|=K$ and $\cup_{i \in I} A_i  = S$ $\}$.
\end{tabular}

\vspace{0.5em}

\noindent
Prove that $\SC$ is in {\bf NP}.
\end{question}

\begin{question}
\emph{Los Tabernacos} is a famous poutine restaurant in Playa del Carmen,
Mexico. The owners want to advertize their restaurant to all people 
(``users'') on Instagram. For a given integer $K$, they ask $K$ users
to post a picture of the 
restaurant\footnote{and offer them free poutine} on their account. 

All users follow the Instagram etiquette: If user $u$ posts a 
picture, then all users who follow $u$ post a copy of this picture. 

Can the owners of Los Tabernacos choose $K$ users such that all 
Instagram users post a picture of the restaurant? 

\begin{itemize} 
\item Formulate this problem as a decision problem $\LT$ on a graph.  
\item Prove that $\LT \leq_P \SC$, i.e., in polynomial time, $\LT$ 
can be reduced to $\SC$.
\end{itemize} 
\end{question}

\begin{question}
Let $G=(V,E)$ be an undirected graph. A \emph{Hamilton cycle} is a 
cycle in $G$ that contains every vertex exactly once. 
A \emph{Hamilton} $st$-\emph{path} is a path in $G$ between the 
vertices $s$ and $t$ that contains every vertex exactly once. 

Consider the problems 
\[ \HC= \{ G : \mbox{ graph $G$ contains a Hamilton cycle} \}  
\]
and 
\[ \HP= \{ (G,s,t) : \mbox{ graph $G$ contains an $st$-Hamilton path} \} .  
\]

\begin{itemize} 
\item Prove that $\HC \leq_P \HP$, i.e., in polynomial time, 
$\HC$ can be reduced to $\HP$.
\item Prove that $\HP \leq_P \HC$, i.e., in polynomial time, 
$\HP$ can be reduced to $\HC$.
\end{itemize} 
\end{question}

\begin{question}
In the \emph{longest path problem}, we are given an undirected graph 
$G=(V,E)$ in which each edge has a positive weight, two vertices $s$ 
and $t$, and a number $L$. The question is whether or not $G$ contains 
an $st$-path (i.e., a path between $s$ and $t$) of length at least $L$. 
In such a path, any vertex cannot be visited more than once. 

\[ \LP= \{ (G,s,t,L) : \mbox{ graph $G$ contains an $st$-path of length 
     at least $L$} \} .  
\]

\noindent 
Prove that $\HC\leq_P \LP$, i.e., in polynomial time, 
$\HC$ can be reduced to $\LP$.
\end{question}

\begin{question}
A Boolean formula $\varphi$, in the variables $x_1,x_2,\ldots,x_n$, is 
in \emph{three conjunctive normal form} (3CNF), if it is of the form 
\[ \varphi = C_1 \wedge C_2 \wedge \ldots \wedge C_m ,
\]
where each \emph{clause} $C_i$, $1 \leq i \leq m$, is of the form
\[ C_i = l_1^i \vee l_2^i \vee l_3^i .
\]
Each $l_j^i$ is a \emph{literal}, which is either a variable or the
negation of a variable.

The \emph{three-satisfiability problem} is defined as follows:
\[ \TSAT = \{ \varphi : \varphi \mbox{ is in 3CNF-form
                                       and is satisfiable} \} .  
\]

A \emph{vertex cover} of an undirected graph $G=(V,E)$ is a subset 
$X$ of $V$ such that for each edge $\{u,v\}$ in $E$, at least one of 
$u$ and $v$ is in $X$. 

The \emph{vertex cover problem} is defined as follows:
\[ \VC= \{ (G,K) : \mbox{ graph $G$ contains a vertex cover of size $K$} 
            \} . 
\]

\noindent
Prove that $\TSAT \leq_P \VC$, i.e., in polynomial time, $\TSAT$ 
can be reduced to $\VC$.
\end{question}

\end{document} 
