%  Problem set 8
%  Combinatorial Optimization, SUAMI, summer 2015
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

% AMSFonts
\input amssym.tex

\font\titlefont=cmbx12  \font\smfont=cmr8  \font\transposefont=cmss8 at6pt

\headline={\hfil}
\footline={\hfil}

\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
	\medskip\filbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent{\bf Solution.}\enspace\ignorespaces}

\def\R{{\mathord{\Bbb R}}}  \def\N{{\mathord{\Bbb N}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}  \def\abs#1{\labs#1\rabs}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~8}
\smallskip
\centerline{Assigned Thursday, July~2, 2015. Due Thursday, July~9, 2015.}

\medskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Fix constants $a\in\R$ and $b>1$. For $n\in\N$, let $f(n)=n^a$ and
$g(n)=b^n$. Prove that $f(n)=o\bigl(g(n)\bigr)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Carefully state the decision (recognition) version of the minimum
spanning tree problem. Prove that this problem is in~P.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Prove that if we had a polynomial-time algorithm for {\it computing
the length\/} of the shortest TSP tour, then we would have a polynomial-time
algorithm for {\it finding\/} the shortest TSP tour. (In other words, show how
to solve the optimization version of the traveling salesman problem in
polynomial time given a polynomial-time algorithm for solving the evaluation
version.)

\smallskip

\noindent[Hint: It may be helpful first to assume that the optimal tour is
unique, and then later revise your approach to remove that assumption. If the
optimal tour is unique, then, of course, each arc either is in the optimal tour
you're searching for or else is not in any optimal tour.]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In the {\smfont VERTEX COVER} problem, an instance is a simple
undirected graph $G=(V,E)$ and a positive integer $k\le\abs V$, and the
question is whether there exists a {\it vertex cover\/} of size no greater
than~$k$, that~is, a subset $V'\subseteq V$ with $\abs{V'}\le k$ such that for
every edge $\{u,v\}\in E$ at least one of the endpoints $u$~and~$v$ belongs
to~$V'$. Prove that {\smfont VERTEX COVER} is in~NP.

\smallskip

\noindent[To do this, you will need to carefully describe the form of a
certificate and the operation of a corresponding verifier (i.e., a
certificate-checking algorithm) and show that every ``yes'' instance of the
{\smfont VERTEX COVER} problem has a polynomial-size certificate that can be
verified in polynomial time by the verifier.]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In the 3-{\smfont COLORABILITY} problem, an instance is a simple
undirected graph $G=(V,E)$, and the question is whether there exists a proper
3-coloring of the vertices of~$G$, that~is, a function $f:V\to\{1,2,3\}$ such
that $f(u)\not=f(v)$ for every edge $\{u,v\}\in E$. (Think of the function~$f$
as assigning each vertex a ``color'' in the set $\{1,2,3\}$; then no two
adjacent vertices can be assigned the same color.) The 4-{\smfont COLORABILITY}
problem is defined analogously. Describe and justify a polynomial-time
transformation from 3-{\smfont COLORABILITY} to 4-{\smfont COLORABILITY}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In the {\smfont SUBGRAPH ISOMORPHISM} problem, an instance consists of
two simple undirected graphs $G=(V_G,E_G)$ and $H=(V_H,E_H)$, and the question
is whether $G$ contains a subgraph isomorphic to~$H$, that~is, a subgraph
$K=(V_K,E_K)$ with $V_K\subseteq V_G$ and $E_K\subseteq E_G$ such that there
exists a bijection $f:V_H\to V_K$ with $\{u,v\}\in E_H$ if and only~if
$\{f(u),f(v)\}\in E_K$. Prove that {\smfont SUBGRAPH ISOMORPHISM} is
NP-complete.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
