\documentclass{article}

\input{6045preamble}
\usepackage{amssymb,amsmath,graphicx,mdwlist}

\begin{document}

\homework{11}{Nancy Lynch}{Due: April 30, 2007}{Elena Grigorescu}

{\bf Readings:}  Sections 7.4, 7.5, Garey-Johnson (optional)

\bigskip

\begin{problem} 

(Sipser 7.39)  
In the proof of the Cook-Levin theorem (for NP-completeness of SAT),
we defined a tile to be a 2 by 3 rectangle of cells.  Show why the
proof would have failed if we had used 2 by 2 windows instead.
\end{problem}

\begin{problem} 


(Sipser 7.36)  Show that, if P=NP, a polynomial time algorithm exists
  that, given a Boolean formula $\phi$, actually produces a satisfying
  assignment for $\phi$ if it is satisfiable.\\
(Note: NP is a class of {\em languages} and above you are being asked
  for an {\em algorithm} that produces a satisfying assignment (if one
  exists) for a given $\phi$.  Thus simply saying that, ``because SAT
  is in NP, you are done'' isn't enough.)

\end{problem}


\begin{problem} (Sipser 7.20) 
Let $G$ represent an undirected graph and let
$$SPATH=\{\langle G,a,b,k \rangle|~G \mbox{ contains a simple path of length at {\bf most} $k$ from $a$ to $b$}\}$$
and
$$LPATH=\{\langle {G,a,b,k} \rangle|~G \mbox{ contains a simple path of length at {\bf least} $k$ from $a$ to $b$}\}$$
\begin{enumerate}
\item Show that SPATH $\in$ P. 
\item Show that LPATH is NP-complete.  You may assume the NP-completeness of UHAMPATH, the Hamiltonian path problem for undirected graphs.
\end{enumerate}
\end{problem}

\begin{problem} (Sipser 7.23) A {\bf cut} in an undirected graph is a
  separation of the vertices $V$ into two disjoint subsets $S$ and
  $T$.  The size of a cut is the number of edges that have one
  endpoint in $S$ and the other in $T$.  Let 
$$MAXCUT = \{\langle{G,k}\rangle|~G \mbox{ has a cut of size $k$ or more}\}.$$

Show that MAXCUT is NP-complete.  You may assume the result of Problem
7.24 of Sipser's book. \\

(Hint: Show that $\neq$-SAT $\leq_P$ MAXCUT.  The variable gadget for
variable $x$ is a collection of $3k$ nodes labeled with $x$ and
another $3k$ nodes labeled with $\overline{x}$, where $k$ is the
number of clauses.  All nodes labeled $x$ are connected with all nodes
labeled $\overline{x}$.  The clause gadget is a triangle of three
edges connecting three nodes labeled with the literals appearing in
the clique.  Do not use the same node in more than one clause gadget.
Prove that this reduction works.)
\end{problem}


\end{document}


