% ---------
% Compile with "pdflatex hw0".
% --------
%!TEX TS-program = pdflatex
\documentclass[11pt]{article}
\usepackage{jeffe,handout,graphicx,mathtools,url}
%!TEX encoding = UTF-8 Unicode
\usepackage[utf8x]{inputenc} % Allow some non-ASCII Unicode in source
\usepackage{enumerate}
\usepackage{stmaryrd}
\def\Sym#1{\textbf{\texttt{\color{BrickRed}#1}}}
% ---------
% The next following lines change the default text and math fonts and
% make a few other minor cosmetic changes. If you get any error
% messages related to these packages, just comment them out. -- Jeff
% --------
\usepackage[charter]{mathdesign}
\usepackage{berasans,beramono}
\SetMathAlphabet{\mathsf}{bold}{\encodingdefault}{\sfdefault}{b}{\updefault}
\SetMathAlphabet{\mathtt}{bold}{\encodingdefault}{\ttdefault}{b}{\updefault}
\SetMathAlphabet{\mathsf}{normal}{\encodingdefault}{\sfdefault}{\mddefault}{\updefault}
\SetMathAlphabet{\mathtt}{normal}{\encodingdefault}{\ttdefault}{\mddefault}{\updefault}
\usepackage{microtype}
% ---------
% End of cosmetics.
% --------
% ---------
% Redefine suits
% --------
\usepackage{pifont}
\def\Spade{\text{\ding{171}}}
\def\Heart{\text{\textcolor{Red}{\ding{170}}}}
\def\Diamond{\text{\textcolor{Red}{\ding{169}}}}
\def\Club{\text{\ding{168}}}
% ---------
% Dashed lines in arrays
% --------
\usepackage{arydshln}
\dashlinedash 0.75pt
\dashlinegap 1.5pt
\hidesolutions
% -----
% Additional notation
% -----
\usepackage{xspace}
\newcommand{\pos}{\ensuremath{\mathrm{pos}}\xspace}
% =========================================================
\begin{document}
\headers{“CS 374”}{Homework 1}{Fall 2015}
\thispagestyle{empty}
\begin{center}
\LARGE
\textbf{“CS 374” Fall 2015 --- Homework 10}
\\
\Large Due Wednesday, December 2, 2015 at 10am
\end{center}
\bigskip
\bigskip
\bigskip
\hrule
\begin{center}
\Large \textbf{••• Some important course policies •••}\\
\end{center}
\hrule
\bigskip
\begin{itemize}
\item \textbf{You may work in groups of up to three people.} However, each problem should be submitted by exactly one person, and the beginning of the homework should clearly state the names and NetIDs of each person contributing.
\item \textbf{You may use any source at your disposal}—paper,
electronic, or human—but you \EMPH{must} cite \EMPH{every} source
that you use. See the academic integrity policies on the course web
site for more details. For all future homeworks, groups of up to
three students will be allowed to submit joint solutions.
\item
\textbf{Submit your pdf solutions in Moodle.}
See instructions on the course website and submit a separate pdf
for each problem. Ideally, your solutions should be typeset in LaTex. If you hand write your homework make sure that the pdf scan is easy to read. Illegible scans will receive no points.
\item
\textbf{Avoid the Three Deadly Sins!} There are a few dangerous writing (and thinking) habits that will trigger an automatic zero on any homework or exam problem. Yes, we are completely serious.
\begin{itemize}\itemsep0pt
\item Give complete solutions, not just examples.
\item Declare all your variables.
\item Never use weak induction.
\end{itemize}
\item
Unlike previous editions of this and other theory courses we are not
using the “I don’t know” policy.
\end{itemize}
\bigskip
\hrule
\begin{center}
\large \textbf{See the course web site for more information.}\\[2ex]\normalsize
If you have any questions about these policies,\\
please don’t hesitate to ask in class, in office hours, or on Piazza.
\end{center}
\hrule
\vfil
\vfil
\vfil
\newpage
\begin{enumerate}
\parindent 1.5em \itemsep 3ex plus 0.5fil
%----------------------------------------------------------------------
\def\arraystretch{1.2}
%----------------------------------------------------------------------
\item Reduce the Hamiltonian Path problem in Directed graphs to SAT via
the following hints. Note that this means that you should come up with
a polynomial-time algorithm that given a directed graph $G=(V,E)$ outputs a SAT
formula $\varphi$ such that $\varphi$ is satisfiable iff $G$ has
a Hamiltonian Path. You can come up with your own reduction without
looking at the outline below which is only one of several
possible reductions.
\begin{itemize}
\item Given directed graph $G=(V,E)$ use variables $x(v,i)$ for each
$v$ and $1 \le i \le n$ to indicate whether $v$ is in the Hamiltonian
path at position $i$.
\item Write constraints to ensure that for each $v \in V$ exactly one
of $x(v,1), x(v,2), \ldots, x(v,n)$ is set to $1$. Here $n = |V|$.
\item Add variables $z(u,v)$ for each ordered pair $(u,v)$.
Write constraints such that $z(u,v)$ is $1$ iff edge $(u,v)$ is in
$E$.
\item Write constraints to ensure that if $x(u,i)$ is $1$ and $x(v,i+1)$ is
$1$ then $z(u,v)$ is $1$.
\item What is the size of the formula in your struction as a function
of $|V|$ and $|E|$? By size of a SAT formula we mean the total sum
of all the claus lengths.
\end{itemize}
Justify the correctness of the reduction.
%----------------------------------------------------------------------
\item Suppose you are given a graph $G=(V,E)$ where
$V$ represents a collection of people and an edge between two
people indicates that they are friends. You wish to break up $V$
into at most $k$ non-overlapping groups $V_1,V_2,\ldots,V_k$ such that
each group is very cohesive. One way to model cohesiveness is to insist
that each pair of people in the same group should be friends; in other
words they should form a clique. Given $G$ and $k$ show that the problem
of deciding whether $G$ can be partitioned into at most $k$ cliques
is NP-Complete. {\em Hint:} Consider a reduction from $k$-coloring.
%----------------------------------------------------------------------
\item MAX 2SAT is the decision problem where the input
consists of a 2CNF formula $\varphi$ and an integer $L$ and
the goal is to decide if there is an assignment to the
variables such that at least $L$ cluases of $\varphi$ are
satisfied. Note that 2SAT is polynomial-time solvable.
Here we will see that MAX 2SAT is NP-Complete.
\begin{enumerate}
\item Consider two boolean variables $x$ and
$y$. Write a 2CNF formula that computes the function $\neg(
x \wedge y)$.
\item Given a connected graph $G=(V,E)$ with
$n$ vertices and $m$ edges, we want to compute its maximum
size independent set. To this end, we define a boolean
variable for every vertex of $V$. Describe how to write a
2CNF formula that is true if and only if the vertices that
are assigned value $1$ are all independent.
\item Given a graph $G$ and an integer $k$, describe how to compute
a 2CNF formula $\varphi$ and a value $L$ such that at least $L$
clauses of $\varphi$ can be satisfied if and only if there is an
independent set in $G$ of size $k$ (or larger). To make things
easy, you are allowed to duplicate the same clause in your
formula as many times as you want. Naturally, the algorithm for
computing this formula from $G, k$ should work in polynomial time
(and of course, you need to describe this algorithm). What is the
value of $L$ as a function of $n$, $m$ and $k$ where $n=|V|$ and
$m=|E|$?
\item Using the preceding part prove that MAX 2SAT is
NP-Complete.
\end{enumerate}
\end{enumerate}
\end{document}
%----------------------------------------------------------------------