%  Problem set 8: solutions
%  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

\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
	\vskip0pt plus1in\medbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent\llap{$\triangleright$\bf\phantom.\enspace}{\bf Solution.}\enspace\ignorespaces}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}
\def\subqed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\raise2pt\hbox{\vrule height4pt width4pt depth0pt}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

\newdimen\pivotwidth  \newdimen\pivotdepth
\def\pivot#1{%
	\setbox0=\hbox{\vphantom/$#1$}
	\pivotdepth=\dp0
	\setbox0=\hbox{\vbox{\vskip1pt\hbox{\hskip2pt\box0\hskip2pt}\vskip1pt}}%
	\pivotwidth=\wd0  \advance\pivotwidth by0.8pt
	\lower\pivotdepth\hbox{\vbox{%
		\vskip-1.4pt
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\hbox{%
			\vrule height\ht0 depth\dp0 width0.4pt
			\copy0
			\vrule height\ht0 depth\dp0 width0.4pt
		}%
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\vskip-1.4pt
	}\hskip-2.4pt}%
}

\def\frac#1#2{{\textstyle{{#1}\over{#2}}}}
\def\R{{\mathord{\Bbb R}}}  \def\Q{{\mathord{\Bbb Q}}}
\def\Z{{\mathord{\Bbb Z}}}  \def\N{{\mathord{\Bbb N}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}  \def\abs#1{\labs#1\rabs}
\def\implies{\Longrightarrow}
\def\lh{\buildrel\rm L\mathchar"0027H\over=}
\def\lcm{\mathop{\rm lcm}}

% Modeled after \notin, TeXbook page 360
\catcode`\@=11
\def\notsubseteq{\mathrel{\mathpalette\c@ncel\subseteq}}
\catcode`\@=12

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

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~8: solutions}

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

\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)$.

\solution First we observe that $g(n)\ge0$ for all $n\in\N$ and
$\lim_{n\to\infty}g(n)=\lim_{n\to\infty}b^n=\infty$ because $b>1$. Now we
consider three cases based on the value of~$a$.

{\it Case~1: $a\le0$.}\enspace Then for all $n\in\N$ we have
$0\le n^a\le n^0=1$, so $0\le f(n)/g(n)\le1/g(n)$ for all $n\in\N$. Therefore,
by the squeeze theorem,
$$0\le\lim_{n\to\infty}{f(n)\over g(n)}\le\lim_{n\to\infty}{1\over g(n)}=0,$$
so $\lim_{n\to\infty}f(n)/g(n)=0$, which is to say, $f(n)=o\bigl(g(n)\bigr)$.

{\it Case~2: $a$~is a positive integer.}\enspace Since $a>0$,
$\lim_{n\to\infty}f(n)=\lim_{n\to\infty}n^a=\infty$, so the form of the limit
$\lim_{n\to\infty}f(n)/g(n)$ is $\infty/\infty$, which is an indeterminate
form. Therefore, by L'H\^opital's rule,
$$\lim_{n\to\infty}{f(n)\over g(n)}=\lim_{n\to\infty}{n^a\over b^n}
	\lh\lim_{n\to\infty}{an^{a-1}\over b^n\ln b}
	\lh\lim_{n\to\infty}{a(a-1)n^{a-2}\over b^n(\ln b)^2}\lh\cdots
	\lh\lim_{n\to\infty}{a!\over b^n(\ln b)^a}=0,$$
the last equality following from the fact that the numerator is a constant
while the denominator tends to infinity. So $f(n)=o\bigl(g(n)\bigr)$.

{\it Case~3: $a>0$ is not an integer.}\enspace Let $A=\lceil a\rceil$. Then for
all $n\in\N$ we have $0\le n^a/b^n\le n^A/b^n$, and by case~2 above we know
that $\lim_{n\to\infty}n^A/b^n=0$, so by the squeeze theorem
$\lim_{n\to\infty}f(n)/g(n)=\lim_{n\to\infty}n^a/b^n=0$. Hence
$f(n)=o\bigl(g(n)\bigr)$. \qed

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

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

\solution In {\smfont MINIMUM SPANNING TREE}, the decision version of the
minimum spanning tree problem, an instance is a simple undirected graph
$G=(V,E)$, a function $w:E\to\Q$ specifying edge weights, and a threshold
value $k\in\Q$, and the question is whether $G$~contains a spanning tree with
total edge weight no greater than~$k$. (It is not particularly important that
the codomain of~$w$ and the set from which $k$ is chosen be~$\Q$.)

The graph~$G$ in the instance may not be connected, so we first perform the
following transformation to convert the instance $(G,w,k)$ into another
instance $(G',w',k)$ such that $G'$ is {\it complete\/} (i.e., every two
vertices are adjacent) and such that $G'$~contains a spanning tree with total
edge weight no greater than~$k$ if and only~if $G$~does. Let $z$ be the sum of
all negative edge weights in the instance:
$$z=\sum_{\scriptstyle e\in E\atop{\scriptstyle{\rm such\ that}\atop\scriptstyle w(e)<0}}w(e).$$
Then take $G'=(V,E')$, where $E'=\bigl\{\,\{u,v\}:u,v\in V,\,u\not=v\,\bigr\}$.
Define the edge weights $w'(\{u,v\})$ for $\{u,v\}\in E'$ as follows:
$$w'(\{u,v\})=\cases{
	w(\{u,v\}),&if $\{u,v\}\in E$;\cr
	k-z+1,&otherwise.\cr
}$$
The value of~$z$ can be found in $O(\abs E)=O(\abs V^2)$ time, and the
construction of $E'$~and~$w'$ can be done in $O(\abs V^2)$~time, so this whole
transformation can be done in $O(\abs V^2)$~time.. Now, any spanning tree
in~$G$ is also a spanning tree in~$G'$ with the same total edge weight, so if
$G$ contains a spanning tree with weight no greater than~$k$, then so
does~$G'$. Conversely, no spanning tree in~$G'$ with weight no greater than~$k$
can contain an edge of weight $k-z+1$, because the total edge weight of a
subset of edges containing such an edge is at minimum $(k-z+1)+z=k+1>k$.
Therefore, if $G'$ contains a spanning tree with weight no greater than~$k$,
then it uses only edges that are also edges in~$G$ (of the same weight), so $G$
also contains a spanning tree with weight no greater than~$k$. Hence we may
solve the original instance $(G,w,k)$ by solving the instance $(G',w',k)$.

As we showed in class on June~17, a minimum spanning tree for a connected graph
can be found using Prim's algorithm. The specific implementation of Prim's
algorithm that was presented in the lecture is as follows:

\smallskip

\item{1.} Initialize $U:=\{u_1\}$, where $u_1$ is an arbitrary vertex in~$V$,
and $T:=\emptyset$.

\smallskip

\item{2.} If $U=V$, we are done. Stop.

\smallskip

\item{3.} Out of all edges having exactly one endpoint in~$U$, choose one with
minimum weight, say $\{u,v\}$ where $u\in U$ and $w\notin U$.

\smallskip

\item{4.} Add $v$ to~$U$ and add $\{u,v\}$ to~$T$.

\smallskip

\item{5.} Go back to step~2.

\smallskip

\noindent The initialization of this algorithm can be done in constant time.
The set~$U$ begins with a single vertex, each iteration of the algorithm adds
one vertex to~$U$, and the algorithm stops when $U=V$, which means the
algorithm will run for $\abs V-1=O(\abs V)$ iterations. In each iteration, the
algorithm must select one edge in step~3. To do this, we must first identify
the edges that have exactly one endpoint in~$U$; this can be done by iterating
through all edges in~$E$ and, for each edge~$\{u,v\}$, iterating through~$V$
attempting to find~$u$ and iterating through~$V$ attempting to find~$v$, and
then testing whether ($u\in U$ and $v\notin U$) or ($u\notin U$ and $v\in U$).
This part can be done in $O(\abs E\cdot\abs V)$ time. Then, out of those edges,
of which there are at most~$\abs E$, we must find the one that has minimum
weight; this can be done in $O(\abs E)$~time (see the algorithm for finding the
minimum element in an unordered list described in class on June~29). So step~3
of the algorithm can be done in $O(\abs E\cdot\abs V)=O(\abs V^3)$ time. Steps
2,~4, and~5 can be done in constant time. Steps 2 through~5 are performed
$O(\abs V)$~times, so the whole algorithm runs in $O(\abs V^4)$~time.

After we run Prim's algorithm to find a minimum spanning tree in~$G'$, we
calculate its total edge weight~$W$; this can be done in $O(\abs V)$~time
because the tree has $\abs V-1$~edges. Then we compare $W$ to~$k$, which can be
done in constant time, and we return ``yes'' if $W\le k$ or ``no'' if $W>k$.

This whole algorithm---the transformation from $(G,w,k)$ to $(G',w',k)$ in
$O(\abs V^2)$~time, the running of Prim's algorithm in $O(\abs V^4)$~time, and
the final calculations and comparison in $O(\abs V)$~time---can be done in
$O(\abs V^4)$~time, which is polynomial in the size of the instance. Therefore
{\smfont MINIMUM SPANNING TREE} is in~P. \qed

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

\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.)

\solution An instance of the traveling salesman problem consists of a positive
integer~$n$ and an $n\times n$~matrix~$C$ of costs~$c_{ij}$. An instance
therefore contains $\Theta(n^2)$~numbers. Note that we are not assuming that
$c_{ij}=c_{ji}$; the costs may be asymmetric. We do assume that the
costs~$c_{ij}$ are rational numbers, which is a reasonable assumption.
(Allowing arbitrary real-valued costs introduces some troublesome
complications, among which is the issue of representation---there are
uncountably many real numbers, but only countably many finite strings of
symbols from a fixed finite alphabet, so it is impossible to represent all real
numbers in a practical model of computation.)

Suppose that we have a polynomial-time algorithm~$\cal L$ for computing the
length of the shortest tour; so the input to~$\cal L$ is a pair $(n,C)$, and
the output is a single number giving the length of the shortest tour. Observe
that finding a shortest tour is equivalent to finding the {\it set of
arcs\/}~$(i,j)$ that the tour uses. (Converting from a set of arcs to a
sequence of nodes, or vice versa, can easily be done in polynomial time.)

Let us first assume that all costs are integers. Let us also assume that the
shortest tour is unique. Then we can find the shortest tour as follows: Given
an instance $(n,C)$, use~$\cal L$ to compute the length~$z^*$ of the shortest
tour. Now, for each arc~$(i,j)$, $i\not=j$, let $C'_{(ij)}$ be the matrix
obtained from~$C$ by replacing the single entry~$c_{ij}$ with $c_{ij}+1$, and
use~$\cal L$ to compute the length~$z'_{(ij)}$ of the shortest tour
in~$(n,C'_{(ij)})$. If $z'_{(ij)}=z^*$, then the arc~$(i,j)$ is not used in the
unique shortest tour in~$(n,C)$, because increasing its cost did not increase
the cost of this tour. On the other hand, if $z'_{(ij)}>z^*$, then the
arc~$(i,j)$ {\it is\/} used in the shortest tour in~$(n,C)$. So let
$U=\{\,(i,j):z'_{(ij)}>z^*\,\}$. The arcs in~$U$ are precisely those used in
the unique shortest tour in~$(n,C)$. Each matrix~$C'_{(ij)}$ can be constructed
in $O(n^2)$~time from the matrix~$C$, and the rest of the calculations for a
given arc~$(i,j)$ can be done in a constant number of elementary operations
plus one call to~$\cal L$. These steps are repeated for each of the
$\Theta(n^2)$~arcs~$(i,j)$, so this algorithm requires $O(n^4)$~elementary
operations plus $O(n^2)$~calls to~$\cal L$. If $\cal L$ runs in polynomial
time, then this gives us a polynomial-time algorithm to find the shortest tour.

If the costs are rational numbers rather than integers, then we can first
multiply all of the costs by their least common (positive) denominator~$d$,
which will convert them to integers. There are exactly $n$~arcs in every tour,
so this will multiply the cost of every tour by the same positive factor~$nd$,
and therefore a tour is optimal for this modified cost matrix if and only~if it
was optimal for the original matrix. This transformation can be performed with
$O(n^2)$~arithmetic operations (counting $\lcm$ as a single arithmetic
operation), which includes both finding the value of~$d$ and multiplying every
cost by this value. [To be more careful, the least common denominator can be
found using the Euclidean algorithm, which can be shown to run in polynomial
time in the number of bits in the input, so this is not a problem.] Therefore,
once we have a polynomial-time algorithm for finding the shortest tour in an
instance with integer costs, we can also use it to find the shortest tour in an
instance with rational costs in polynomial time.

Now we remove the assumption that the shortest tour is unique. For
$1\le i\le n$ and $1\le j\le n$, let $p_n(i,j)=n(i-1)+j$. So $p_n(1,1)=1$,
$p_n(1,2)=2$, \dots, $p_n(1,n)=n$, $p_n(2,1)=n+1$, $p_n(2,2)=n+2$, \dots,
$p_n(2,n)=2n$, $p_n(3,1)=2n+1$, \dots, $p_n(n,n)=n^2$; the function~$p_n$
assigns distinct integers in $\{1,2,\ldots,n^2\}$ to all of the ordered
pairs~$(i,j)$ with $1\le i\le n$ and $1\le j\le n$. Given a TSP
instance~$(n,C)$ with rational costs, first perform the transformation
described above to transform it to an instance~$(n,C')$ with all integer costs.
Then transform this to another instance~$(n,C'')$ by replacing each
cost~$c'_{ij}$ with $c''_{ij}=c'_{ij}+1/2^{p_n(i,j)}$; so $c'_{11}$ is
increased by~$1/2$, $c'_{12}$~is increased by~$1/4$, $c'_{13}$~is increased
by~$1/8$, and so on. [This second transformation can be done with
$O(n^2)$~arithmetic operations.] Note that the fractional parts of the
costs~$c''_{ij}$ are distinct positive integer powers of~$1/2$, so no two sums
of subsets of these costs can have the same fractional part, which means that
the optimal tour in~$(n,C'')$ must be unique. Furthermore, because the costs
in~$C'$ are all integers, the cost of any non-optimal tour in~$(n,C)$ is at
least 1 greater than the cost of an optimal tour; and the maximum amount that
the cost of a tour in~$(n,C')$ is increased in~$(n,C'')$ is certainly no more
than $\sum_{k=1}^{n^2}1/2^k<1$, so an optimal tour in~$(n,C')$ cannot be made
to have larger total weight in~$(n,C'')$ than a tour that is not optimal
in~$(n,C')$, so the unique shortest tour in~$(n,C'')$ is also optimal
in~$(n,C')$, and hence in~$(n,C)$. Thus we can use the algorithm described
above to find the unique shortest tour in~$(n,C'')$ in polynomial time, which
is also a shortest tour in~$(n,C)$. \qed

\medskip

\noindent [In fact, there is a way to use this last trick to find a shortest
tour in~$(n,C)$ with only {\it one\/} call to~$\cal L$: Transform $(n,C)$
to~$(n,C'')$ as described above, and then use~$\cal L$ to find the length~$z^*$
of the shortest tour in~$(n,C'')$. By the construction of the costs~$c''_{ij}$,
the fractional part of~$z^*$, when written in binary, will contain a~1 in
position $p_n(i,j)$ if and only~if the arc~$(i,j)$ is used in the shortest
tour! To get the same effect in base ten rather than binary, use $1/10$ rather
than $1/2$ in the construction of the costs~$c''_{ij}$.]

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

\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.

\solution To prove that {\smfont VERTEX COVER} is in~NP, we need to describe a
verifier and, for every ``yes'' instance, a polynomial-size certificate that
the verifier will accept in polynomial time; and we need to ensure that the
verifier will {\it not\/} accept any fraudulent certificate for a ``no''
instance.

A certificate will consist of a set~$V'$. For a ``yes'' instance, the
certificate that will be accepted by the verifier will be a vertex cover
$V'\subseteq V$ of size no greater than~$k$, which must in turn be no greater
than~$\abs V$. Such a certificate consists of a list of $k$~vertices in~$V$, so
it has size $O(\abs V)$ [or $O(\abs V\log{\abs V})$ if we are counting bits].
This is polynomial in the size of the instance.

\goodbreak

The verifier will act as follows. Remember that the input to the verifier
consists of an instance and a certificate, so the verifier has access to
$V$,~$E$, and~$k$ as well as the certificate~$V'$.

\smallskip

\item{$\bullet$} First, the verifier must verify that $\abs{V'}\le k$. This can
be done by iterating through the elements of the set~$V'$ given in the
certificate and counting them, and then comparing the final tally with~$k$.
For a ``yes'' instance and an appropriate certificate, we have
$\abs{V'}\le k\le\abs V$, so this stage of the verification can be done in
$O(\abs V)$~time. If this stage fails (i.e., if it is determined that
$\abs{V'}>k$), then the verifier will reject the certificate.

\smallskip

\item{$\bullet$} Next, the verifier must verify that $V'\subseteq V$. This can
be done by iterating through the elements of~$V'$ and, for each one, iterating
through the elements of~$V$ until a match is found or the end of~$V$ is reached
without a match. For a ``yes'' instance and an appropriate certificate, we have
$\abs{V'}\le k\le\abs V$, so there will be $O(\abs V)$~``outer'' iterations,
and each of these outer iterations will take $O(\abs V)$~``inner'' iterations
through the elements of~$V$. So this stage of the verification can be done in
$O(\abs V^2)$~time. If this stage fails (i.e., if it is determined that
$V'\notsubseteq V$), then the verifier will reject the certificate.

\smallskip

\item{$\bullet$} Then the verifier must verify that for every edge
$\{u,v\}\in E$ at least one of the endpoints $u$~and~$v$ belongs to~$V'$. This
can be done by iterating through the elements of~$E$. For each edge
$\{u,v\}\in E$, the verifier iterates through the elements of~$V'$ attempting
to find~$u$, and if that fails it iterates through the elements of~$V'$
attempting to find~$v$. For a ``yes'' instance and an appropriate certificate,
we have $\abs{V'}\le k\le\abs V$, so the verification for each edge
$\{u,v\}\in E$ takes at most $2\abs{V'}=O(\abs V)$ comparisons, and this is
done for each of $\abs E=O(\abs V^2)$ edges, so this stage of the verification
can be done in $O(\abs V^3)$~time. If this stage fails (i.e., if it is
determined that $E$ contains an edge $\{u,v\}$ such that neither $u$~nor~$v$ is
in~$V'$), then the verifier will reject the certificate.

\smallskip

\item{$\bullet$} If the verifier gets to this point, then it has verified that
$\abs{V'}\le k$, $V'\subseteq V$, and for every edge $\{u,v\}\in E$ at least
one of the endpoints $u$~and~$v$ belongs to~$V'$. This means that $V'$ is
indeed a vertex cover of size no greater than~$k$, so the answer to the
instance is ``yes,'' and the verifier will accept the certificate.

\smallskip

\noindent For a ``yes'' instance and an appropriate certificate, the three
stages of this verification process can be done in $O(\abs V)$~time, $O(\abs
V^2)$~time, and $O(\abs V^3)$~time, respectively, so the entire verification
process takes $O(\abs V^3)$~time, which is polynomial in the size of the
instance. Moreover, the verifier will accept the certificate {\it only~if\/}
the answer to the instance really is ``yes,'' because the verifier will accept
the certificate only if the certificate gives a vertex cover of size no greater
than~$k$. Therefore {\smfont VERTEX COVER} is in~NP. \qed

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

\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}.

\solution Let $G=(V,E)$ be an instance of 3-{\smfont COLORABILITY}. Our goal is
to construct a graph $G'=(V',E')$, an instance of 4-{\smfont COLORABILITY},
such that $G'$ has a proper 4-coloring if and only~if $G$~has a proper
3-coloring.

Let $V'=V\cup\{\alpha\}$, where $\alpha$ is a new vertex not in~$V$, and let
$E'=E\cup\bigl\{\,\{\alpha,v\}:v\in V\,\bigr\}$, that~is, join $\alpha$ to
every vertex in~$V$. This construction can be done in $O(\abs V)$~time if the
instance~$G$ can be modified in place (the only necessary modifications are the
addition of one more vertex and $\abs V$~more edges), or in $O(\abs V+\abs E)$
time if the instance~$G'$ must be written from scratch. In any case, it can be
done in polynomial time in the size of~$G$.

Suppose $G'$ has a proper 4-coloring $\phi:V'\to\{1,2,3,4\}$. The
vertex~$\alpha$ must receive some color; without loss of generality, suppose
$\phi(\alpha)=4$. Because $\alpha$ is adjacent to every other vertex in~$G'$,
no other vertex may be given the same color as~$\alpha$, so
$\phi(v)\in\{1,2,3\}$ for all $v\in V$. Furthermore, any two vertices
$u$~and~$v$ that are adjacent in~$V$ are also adjacent in~$V'$, because
$E\subseteq E'$, so $\phi(u)\not=\phi(v)$. Therefore, restricting the domain
of~$\phi$ to $V=V'\setminus\{\alpha\}$ yields a proper 3-coloring
$\phi\bigr|_V=f:V\to\{1,2,3\}$ of~$G$.

Conversely, suppose $G$ has a proper 3-coloring $f:V\to\{1,2,3\}$. Define
$\phi:V'\to\{1,2,3,4\}$ by $\phi(v)=f(v)$ if $v\in V$ and $\phi(\alpha)=4$. Let
$\{u,v\}\in E'$ be an edge in~$G'$. If $u\in V$ and $v\in V$, then
$\{u,v\}\in E$, so $\phi(u)=f(u)\not=f(v)=\phi(v)$. Otherwise, without loss of
generality, $u=\alpha$ and $v\in V$, so $\phi(u)=4$ and
$\phi(v)=f(v)\in\{1,2,3\}$, which means $\phi(u)\not=\phi(v)$. Hence $\phi$ is
a proper 4-coloring of~$G'$.

Thus $G'$ has a proper 4-coloring if and only~if $G$~has a proper 3-coloring,
so this construction is a polynomial-time transformation from
3-{\smfont COLORABILITY} to 4-{\smfont COLORABILITY}. \qed

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

\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.

\solution First we show that {\smfont SUBGRAPH ISOMORPHISM} is in NP. A
certificate will consist of sets $V_K$~and~$E_K$ and a function $f:V_H\to V_K$.
For a ``yes'' instance, the certificate that will be accepted by the verifier
will specify a subgraph $K=(V_K,E_K)$ of~$G$ and a bijection $f:V_H\to V_K$
such that $\{u,v\}\in E_H$ if and only~if $\{f(u),f(v)\}\in E_K$. Such a
certificate consists of lists of vertices and edges in~$G$, together with a
list of pairs $\bigl(v,f(v)\bigr)$ specifying the function~$f$, so it has size
$O(\abs V+\abs E+\abs{V_H})$, which is $O(\abs V^2)$ because
$\abs E=O(\abs V^2)$ and $\abs{V_H}\le\abs V$ for a ``yes'' instance. [The
certificate has size $O(\abs V^2\log{\abs V})$ if we are counting bits.] This
is polynomial in the size of the instance. The verifier will act as follows:

\smallskip

\item{$\bullet$} First, the verifier must verify that $V_K\subseteq V_G$. This
can be done by iterating through the elements of~$V_K$ and, for each one,
iterating through the elements of~$V_G$ until a match is found or the end
of~$V_G$ is reached without a match. For a ``yes'' instance and an appropriate
certificate, we have $\abs{V_K}\le\abs{V_G}$, so there will be
$O(\abs{V_G})$~``outer'' iterations, and each of these outer iterations will
take $O(\abs{V_G})$~``inner'' iterations through the elements of~$V_G$. So this
stage of the verification can be done in $O(\abs{V_G}^2)$~time. If this stage
fails (i.e., if it is determined that $V_K\notsubseteq V_G$), then the verifier
will reject the certificate.

\smallbreak

\item{$\bullet$} Then the verifier must verify that $E_K\subseteq E_G$. For a
``yes'' instance and an appropriate certificate, this stage of the verification
can be done in $O(\abs{E_G}^2)=O(\abs{V_G}^4)$ time. If this stage fails (i.e.,
if it is determined that $E_K\notsubseteq E_G$), then the verifier will reject
the certificate.

\smallbreak

\item{$\bullet$} Next, the verifier must verify that $(V_K,E_K)$ is a
graph---that for every edge $\{u,v\}\in E_K$ we have $u\in V_K$ and $v\in V_K$
and $u\not=v$. This can be done by iterating through the elements of~$E_K$. For
each edge $\{u,v\}\in E_K$, the verifier iterates through the elements of~$V_K$
attempting to find~$u$, iterates again through the elements of~$V_K$ attempting
to find~$v$, and compares $u$~and~$v$ to ensure they are distinct. For a
``yes'' instance and an appropriate certificate, we have
$\abs{E_K}\le\abs{E_G}=O(\abs{V_G}^2)$ and $\abs{V_K}\le\abs{V_G}$, so there
are $O(\abs{V_G}^2)$~``outer'' iterations, and each of these outer iterations
will take $O(\abs{V_G})$~``inner'' iterations through the elements of~$V_K$
plus a single comparison to ensure that $u\not=v$. So this stage of the
verification can be done in $O(\abs{V_G}^3)$~time. If this stage fails (i.e.,
if it is determined that some edge $\{u,v\}\in E_K$ has $u\notin V_K$ or
$v\notin V_K$ or $u=v$), then the verifier will reject the certificate.

\smallbreak

\item{$\bullet$} The verifier must then verify that the function $f:V_H\to V_K$
is well defined, which is to say that the list of pairs $\bigl(v,f(v)\bigr)$
specifying the function~$f$ gives one and only one value~$f(v)$ in~$V_K$ for
every $v\in V_H$. This can be done in two substages. First, the verifier
iterates through the pairs $\bigl(v,f(v)\bigr)$, and for each such pair it
iterates through the elements of~$V_H$ attempting to find~$v$ and iterates
through the elements of~$V_K$ attempting to find~$f(v)$. Second, the verifier
iterates through the elements of~$V_H$ and, for each $u\in V_H$, iterates
through the pairs $\bigl(v,f(v)\bigr)$, counting the number of times that
$v=u$. For a ``yes'' instance and an appropriate certificate, the number of
pairs $\bigl(v,f(v)\bigr)$ in the list specifying~$f$ is~$\abs{V_H}$, and we
have $\abs{V_H}=\abs{V_K}\le\abs{V_G}$, so each of these two substages takes
$O(\abs{V_G}^2)$~time, which means that the stage as a whole takes
$O(\abs{V_G}^2)$~time. If this stage fails [i.e., if it is determined that some
pair $\bigl(v,f(v)\bigr)$ has $v\notin V_H$ or $f(v)\notin V_K$, or that for
some $u\in V_H$ the number of pairs $\bigl(v,f(v)\bigr)$ such that $v=u$ is not
exactly~1], then the verifier will reject the certificate.

\smallbreak

\item{$\bullet$} Then the verifier must verify that $f$ is a bijection. This
can be done by iterating through the elements of~$V_K$ and, for each
$u\in V_K$, iterating through the pairs $\bigl(v,f(v)\bigr)$ that specify the
function~$f$, counting the number of times that $f(v)=u$. For a ``yes''
instance and an appropriate certificate, we have
$\abs{V_H}=\abs{V_K}\le\abs{V_G}$ and the number of pairs $\bigl(v,f(v)\bigr)$
is~$\abs{V_H}$, so there will be $O(\abs{V_G})$~``outer'' iterations, and each
of these outer iterations will take $O(\abs{V_G})$~``inner'' iterations through
the pairs $\bigl(v,f(v)\bigr)$. So this stage of the verification can be done
in $O(\abs{V_G}^2)$~time. If this stage fails [i.e., if it is determined that
for some $u\in V_K$ the number of pairs $\bigl(v,f(v)\bigr)$ such that $f(v)=u$
is not exactly~1], then the verifier will reject the certificate.

\smallbreak

\item{$\bullet$} Finally, the verifier must verify that $\{u,v\}\in E_H$ if and
only~if $\{f(u),f(v)\}\in E_K$. To do this, the verifier iterates through the
vertices in~$V_H$, letting $u$ be each such vertex in turn; for each
vertex~$u$, the verifier iterates through the vertices in~$V_H$, letting $v$ be
each such vertex in turn; for each pair $(u,v)$, the verifier iterates through
the list of pairs specifying~$f$ in order to determine $f(u)$~and~$f(v)$,
iterates through the elements of~$E_H$ attempting to find $\{u,v\}$, iterates
through the elements of~$E_K$ attempting to find $\{f(u),f(v)\}$, and then
compares the results of these last two searches to see if they both succeeded
or both failed. For a ``yes'' instance and an appropriate certificate, we have
$\abs{V_H}\le\abs{V_G}$ and $E_H=E_K=O(\abs{V_G}^2)$, and the number of pairs
specifying~$f$ is~$\abs{V_H}$. So there will be $\abs{V_H}=O(\abs{V_G})$
$u$-iterations, each of which consists of $\abs{V_H}=O(\abs{V_G})$
$v$-iterations, each of which consists of $O(\abs{V_G})$~iterations through the
pairs specifying~$f$, $O(\abs{V_G}^2)$~iterations through the elements
of~$E_H$, and $O(\abs{V_G}^2)$~iterations through the elements of~$E_K$. Hence
this stage of the verification can be done in $O(\abs{V_G}^4)$~time. If this
stage fails [i.e., if it is determined that there exist $u,v\in V_H$ such that
($\{u,v\}\in E_H$ but $\{f(u),f(v)\}\notin E_K$) or ($\{u,v\}\notin E_H$ but
$\{f(u),f(v)\}\in E_K$)], then the verifier will reject the certificate.

\smallskip

\item{$\bullet$} If the verifier gets to this point, then it has verified that
$V_K\subseteq V_G$, $E_K\subseteq E_G$, $K=(V_K,E_K)$~is a graph, the function
$f:V_H\to V_K$ is well defined, $f$~is a bijection, and $\{u,v\}\in E_H$ if and
only~if $\{f(u),f(v)\}\in E_K$. This means that $K$ is a subgraph of~$G$ that
is isomorphic to~$H$, so the answer to the instance is ``yes,'' and the
verifier will accept the certificate.

\smallbreak

\noindent For a ``yes'' instance and an appropriate certificate, the six stages
of this verification process can be done in $O(\abs{V_G}^2)$~time,
$O(\abs{V_G}^4)$~time, $O(\abs{V_G}^3)$~time, $O(\abs{V_G}^2)$~time,
$O(\abs{V_G}^2)$~time, and $O(\abs{V_G}^4)$~time, respectively, so the entire
verification process takes $O(\abs{V_G}^4)$~time, which is polynomial in the
size of the instance. Moreover, the verifier will accept the certificate
{\it only if\/} the answer to the instance is ``yes,'' because the verifier
will accept the certificate only if the certificate gives a subgraph of~$G$
that is isomorphic to~$H$. Therefore {\smfont SUBGRAPH ISOMORPHISM} is in~NP.

\goodbreak

Next we show that {\smfont CLIQUE} polynomially transforms to {\smfont SUBGRAPH
ISOMORPHISM}. Let $(\Gamma,k)$ be an instance of {\smfont CLIQUE}; that~is, let
$\Gamma=(V,E)$ be a simple undirected graph and let $k$ be a positive integer.
(The question is whether $\Gamma$~contains a clique of size~$k$.) Our goal is
to construct an instance $(G,H)$ of {\smfont SUBGRAPH ISOMORPHISM} such that
$G$~contains a subgraph isomorphic to~$H$ if and only~if $\Gamma$~contains a
clique of size~$k$.

First of all, if $k>\abs V$, then the answer to the {\smfont CLIQUE} instance
is obviously ``no,'' so we can take $G$ to be a graph with exactly one vertex
and $H$~to be a graph with two vertices, for example; then $G$~obviously does
not contain a subgraph isomorphic to~$H$. So we may as well assume that
$k\le\abs V$.

Take $G=\Gamma$ and $H=K_k$, the complete graph on $k$~vertices; so
$H=(V_H,E_H)$ where $V_H=\{1,2,\ldots,k\}$ and
$E_H=\bigl\{\,\{u,v\}:u,v\in V_H,\,u\not=v\,\bigr\}$. This construction can be
done in $O(\abs V^2)$~time, because the number of edges in~$E_H$ is
$k(k-1)/2=O(\abs V^2)$. So the running time of this construction is polynomial
in the size of the {\smfont CLIQUE} instance.

Suppose that $G$ contains a subgraph isomorphic to~$H$. Then there 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$. But $\{u,v\}\in E_H$ for every pair of distinct
vertices $u$~and~$v$ in~$V_H$, so every two vertices in~$V_K$ are adjacent,
which means that $V_K$~is a clique in~$G$. Since $f$ is a bijection, we have
$\abs{V_K}=\abs{V_H}=k$. So $G=\Gamma$ contains a clique of size~$k$.

Conversely, suppose $\Gamma=G$ contains a clique $Q\subseteq V$ of size~$k$.
Take $V_K=Q$ and $E_K=\bigl\{\,\{u,v\}:u,v\in Q,\,u\not=v\,\bigr\}$. Since
$\abs Q=k$, there exists a bijection $f:\{1,2,\ldots,k\}\to Q$. Now
$\{u,v\}\in E_H$ for every pair of distinct vertices $u$~and~$v$ in
$V_H=\{1,2,\ldots,k\}$, and every two vertices in~$Q$ are adjacent, so $G$
contains a subgraph $K=(V_K,E_K)$ isomorphic to~$H$.

Thus $G$~contains a subgraph isomorphic to~$H$ if and only~if $\Gamma$~contains
a clique of size~$k$, so this is a polynomial transformation from
{\smfont CLIQUE} to {\smfont SUBGRAPH ISOMORPHISM}. We proved in class (July~7;
Theorem~15.3 in Papadimitriou and Steiglitz) that {\smfont CLIQUE} is
NP-complete, so {\smfont SUBGRAPH ISOMORPHISM} is also NP-complete. \qed

\medskip

\noindent[Two other possible approaches are to show a polynomial transformation
from {\smfont HAMILTONIAN CIRCUIT} or {\smfont HAMILTONIAN PATH} to
{\smfont SUBGRAPH ISOMORPHISM} by taking $H$ to be a cycle with
$\abs V$~vertices or a path with $\abs V$~vertices, respectively. Note that
taking $H$ to be the graph with $k$~vertices and no edges does {\it not\/} give
a polynomial transformation from {\smfont INDEPENDENT SET} to {\smfont SUBGRAPH
ISOMORPHISM}, because {\it every\/} graph~$G$ with at least $k$~vertices
contains a subgraph isomorphic to this~$H$, whether or not $G$ has an
independent set of size~$k$.]

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

\bye
