%-*- LaTeX -*-

\NeedsTeXFormat{LaTeX2e}
\documentclass{assign}
\usepackage{newcent}
\usepackage{amsmath,amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Start reading here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% The four commands below are used to define the ordinal number of the
% lecture (can be found on the lecture syllabus), the title of the lecture
% (formulate the best description you can come up with; you can always
% resort to the tentative title on the lecture syllabus if you have
% difficulty), the date of the lecture (in this format: DD Month YYYY),
% and the name of the scribe (that's you).
%
% Please supply correct arguments for the four commands below:
%

    \lecturenumber{3}
    \lecturetitle{Homework\ }
    \lecturedate{Oct 22, 2007}
    \duedate{Oct 29, 2007}
    \lecturescribe{}

%
% In the space indicated below, please type out your lecture notes.  You
% should use all the standard LaTeX typesetting conventions, plus a couple
% of additional commands described below.  If you are unfamiliar with using
% LaTeX to typeset technical documents, please read the very useful summary
% entitled ``The Not So Short Introduction to LaTeX2e'' which is available
% on BlackBoard.  You can also examine the source files for the scribed
% lecture notes from lectures 1, 2, and 3 for some formatting ideas. 
%
% Use the standard commands \section{}, \subsection{}, and \subsubsection{}
% to format your document logically into sections, subsections, and 
% subsubsections (as needed). 
%
% If you reference a URL anywhere, use the provided command \urlclick{}
% like this: \urlclick{http://www.web.com/foo.html}.  This will create a
% clickable hyperlink in the resulting .pdf file. 
%
% To add a figure to your notes, use the provided command \figureadd{}
% like this: \figureadd{basename}{label}{caption}.  In this command,
% basename is the base name of your figure, which must exist in both .eps
% and .jpg formats.  For example, if you have created a figure named both
% foo.jpg and foo.eps, then the basename is simply foo.  The label field
% creates a label which you can reference elsewhere using the standard
% command \ref{}.  Please use the caption field to provide a descriptive
% caption for any figure you create.  When you submit your scribed notes,
% please also submit all your figure files in both .eps and .jpg formats.
%
% For a theorem, corollary, lemma, claim, fact, definition, assumption,
% observation, or example, consider using these provided commands to set it
% apart from other text: 
%     \theorem{...}
%     \corollary{...} 
%     \lemma{...}
%     \claim{...}
%       etc.
%
% For proofs, or sketches of proofs, use these provided environments: 
%     \begin{proof}        ... \end{proof}
%     \begin{proof_sketch} ... \end{proof_sketch}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\reals}{{\mathbb R}}
\newcommand{\integers}{{\mathbb Z}}
\newcommand{\ch}{\ensuremath\mathcal{CH}}
% \newtheorem{theorem}{Theorem}[section]
% \newtheorem{lemma}{Lemma}[section]
% \newtheorem{corollary}{Corollary}[section]
% \newtheorem{claim}{Claim}[section]
% \newtheorem{prop}{Proposition}[section]
% \newtheorem{fact}{Fact}[section]
% \newtheorem{problem}{Problem}[section]
% \numberwithin{equation}{section}
\newtheorem{defn}{Definition}[section]
\newenvironment{proofsketch}{\par{\textbf{Proof Sketch:}}}{\(\qed\) \par}

\begin{document}
\label{begin}


\section{Simple NP-hardness}
\label{sec:monotone-3saty}

\begin{enumerate}
\item Solve Problem 8.6 from the textbook
\item The problem \textsc{longest path} is defined as follows: Given a
  graph $G = (V,E)$ and a parameter $k$, determine whether $G$ contains a
  path of length at least $k$. Show that \textsc{longest path} is NP-Complete.
\item What's wrong with the following ``proof'' that $P \ne NP$: To solve
  3SAT, we need to try all $2^n$ possible assignments to the variables in
  the worst case. Therefore 3SAT
  cannot be in $P$, and therefore, since 3SAT is NP-Complete, $P \ne NP$. 
\end{enumerate}


\section{Independent Set on paths}
\label{sec:indep-set-paths}

Given a path $G = v_1-v_2-\ldots-v_n$, and weights $w(v_i) =w_i$, we wish
to find an independent set of maximum weight. Consider the following two
heuristics:

\begin{enumerate}
\item Pick the vertex of largest weight. Delete it and its
  neighbours. Repeat until the graph is empty.
\item Check which of the sets $\{v_1, v_3, \ldots \}$ and $\{v_2, v_4,
  \ldots\}$ has larger weight. Return this set.
\end{enumerate}

In HW 2, you were asked to show both of these heuristics return
sub-optimal solutions. Now, show that both of these heuristics return
2-approximations to the optimal solution.

\section{Integer Programming}
\label{sec:lp-some-problem}

Write down an integer program for the travelling salesman problem. Your
solution should have a polynomial number of variables and a polynomial
number of inequalities. Make sure that your solution is written in the
canonical form 
\begin{align*}
  \label{eq:1}
  \max & \ \mathbf{c^\top x} \\
  & A\mathbf{x} \le \mathbf{b}
\end{align*}
where $\mathbf{c}, \mathbf{x}$ and $\mathbf{b}$ are vectors, and $A$ is a matrix.
\section{Packing Trucks}
\label{sec:11.1-1}

Solve Problem 11.1 from the textbook.

\section{Planar Vertex Cover}
\label{sec:planar-vertex-cover}

\textbf{Warning: this problem will need some careful reasoning !}

To prove that many geometric problems are NP-hard, we need ``planar''
versions of standard NP-hardness results. Consider \textsc{vertex
  cover}. We know that \textsc{vertex cover} is NP-Complete for general
graphs, but what happens if we restrict ourselves to planar graphs (i.e
graphs that can be drawn on a sheet of paper without needing edges to
cross each other) ? Since typical reductions to \textsc{vertex cover}
produce an arbitrary non-planar graph, we can't use the NP-Completeness of
\textsc{vertex cover} to show that \textsc{planar vertex cover} is
NP-Complete. 

In this problem, we will prove that \textsc{planar vertex cover} is
NP-Complete, by reduction from \textsc{vertex cover}. The tricky step is
this: given a graph $G$ that might in general be nonplanar, how can we
convert it to a graph that is planar, while carrying over some
relationship between the vertex cover sizes ? 

The idea is to construct a gadget that removes crossings in the
graph. Figure~\ref{fig:vc} illustrates this idea, removing the single
crossing in the drawing of the graph $K_{3,3}$. 

\begin{figure}[h]
  \centering
  \includegraphics[width=3in]{vc}
\caption{Eliminating a  crossing\label{fig:vc}}
\end{figure}

We can use such gadgets to replace every crossing in $G$. However, the
catch is that we need to ensure that the size of the resulting vertex
cover can be used to infer something about the size of a vertex cover for
the original graph. 

It turns out that the following \emph{crossover} gadget can be used to achieve this:
\begin{figure}[h]
  \centering
    \includegraphics[width=2in]{gadget}
\caption{A crossover gadget for eliminating crossings in a graph\label{fig:gadget}}
\end{figure}
In the figure, the single crossing between the edges $(v_1, v_2)$ and
$(u_1, u_2)$ is eliminated with the crossover gadget that adds 18 vertices for this
crossing. In general, if an edge is crossed by many other edges, we add
one crossover gadget for each crossing:

\begin{figure}[h]
  \centering
    \includegraphics[width=2.5in]{medges}
\caption{Eliminating multiple crossings along an edge\label{fig:gadget}}
\end{figure}

Using this construction, we can take any graph $G$, draw it in the plane
while allowing any edges to cross, and then replace each crossing by the
construction above, obtaining a planar graph $G'$. Notice also that if the
edge $(u_1, u_2)$ was covered in $G$ by choosing $u_1$, we can cover the
set of edges that $(u_1,u_2)$ is broken into by choosing $u_1$ and the
left endpoint of each crossover gadget (of course, the internal edges of
the gadget will still need to be covered). 

Suppose we added $d$ of these gadgets. Show that a vertex cover of size
$k$ in $G$ exists in $G$ if and only if a vertex cover of size $k+13d$
exists in $G'$. Use this fact to conclude that \textsc{planar vertex
  cover} is NP-hard. 


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: