\documentclass[11pt]{article}
\usepackage{program}


\title{6.046 Problem Set 10}
\author{Chris Laas: Section G}
\date{May 5, 2000}

\pagestyle{myheadings}
\markright{Chris Laas: Section G \hfil 6.046J/18.410J \hfil 5/5/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}.}
\NumberProgramstrue
\def\RETURN{\keyword{return}\ }
\def\MOD{\mbox{mod}\ }
\def\text#1{\mbox{ #1 }}
\def\AND{\mbox{\bf\ and }}
\def\OR{\mbox{\bf\ or }}
\def\TRUE{\mbox{\bf true}}
\def\FALSE{\mbox{\bf false}}
\def\choice#1{\left\{ \begin{array}{ll} #1 \end{array} \right.}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}



\begin{document}
\maketitle



\section*{Problem 10-1}
\begin{enumerate}

\item%(a)

It's quite easy to see that, if there exists a spanning graph of
degree $d$ for a graph $G = (V,E)$ and a vertex $u$ with degree
greater than $d$, then there must exist some edge $(u,v)$ such that
the graph with that edge removed still has a spanning graph of degree
$d$.  For, if there existed no such edge, then every spanning graph of
degree $d$ would contain all of the edges incident upon $u$, which
would mean that the degree of $u$ in the spanning graph would still be
greater that $d$, which is a contradiction.

Thus, we need only to remove such edges until a graph of degree $d$
remains.  A very simple, inefficient but polynomial-time, algorithm to
do this would be:

\begin{program}
|Search-SG|(<G,d>)
\quad\tab \IF \mbox{\ there exists a vertex $u \in V[G]$ such that $degree(u) > d$}
             \THEN \FOR \mbox{\ each vertex $v \in V[G]$ such that $(u,v) \in E[G]$}
                       G' \gets (V[G], E[G] - \{(u,v)\})
                       \IF |Decision-SG|(<G',d>)
                          \THEN \RETURN |Search-SG|(<G',d>)
                                \untab%
                          \untab%
                       \untab%
              \ELSE \RETURN G
\end{program}

Correctness follows from the correctness of the above proof, since
this algorithm is a direct translation from the wording of the theorem
into pseudocode.  Termination is guaranteed, since one edge is removed
on every recursive call, and the algorithm terminates as soon as the
degree of the graph is $d$ or less.

Even using the most inefficient search algorithms (linear in number of
vertices), this algorithm calls $|Decision-SG|$ at most $O(VE)$ times,
and takes at most $O(VE)$ overhead, since one edge is removed on
every recursive call.  Thus, if $|Decision-SG|$ runs in polynomial
time, then $|Search-SG|$ runs in polynomial time.


\item%(b)

Your co-worker, by designing an algorithm for solving the NP-complete
problem 3-SAT in polynomial time, has just proven that $P=NP$, and is
probably either rich and famous, or dead, by now.  Regardless, since
$P=NP$, all problems in NP can be solved by a polynomial-time
algorithm.  Hence, we need only prove that the
spanning-graph-of-degree-$d$ problem is in NP.

Let the certificate be the set of vertices and edges which make up a
spanning graph of degree $d$ for the graph.  Then it is trivial to
check in polynomial time that all of the vertices of the original
graph are in the spanning graph and that all of the vertices have
degree less than or equal to $d$ in the spanning graph; and a
linear-time breadth-first search can be used to verify that the
spanning graph is connected, which proves that it spans the original
graph.

Thus, spanning-graph-of-degree-$d$ is in NP; since 3-SAT is
NP-complete and 3-SAT is in P, we have that
spanning-graph-of-degree-$d$ is in P.  Thus, there exists a
polynomial-time algorithm that solves the spanning-graph-of-degree-$d$
problem.

We can use this as a subroutine to solves the smallest degree spanning
graph, simply by checking whether there exists a
spanning graph of degree $d$ for all $d$ between 1 and $\|V\|$,
inclusive.  This would call spanning-graph-of-degree-$d$ at most
$\|V\|$ times, and thus would be polynomial-time.


\end{enumerate}
\newpage




\section*{Problem 10-2}
\begin{enumerate}

\item%(a)

We need to show that, if we could solve the knapsack problem in
polynomial time, then we could solve the subset-sum problem in
polynomial time.

Let's say we have an instance of the subset-sum problem: a set
$S = \{ s_1, s_2, \dots, s_n \}$ of integers and a target integer
$t$.  We can construct an instance of the knapsack problem by setting
the object sizes to be the integers $s_i$, setting the worths to be
$w_i = s_i$, and setting the knapsack size $B = t$.  If we can solve
the knapsack problem in polynomial time, then we can get the maximum
total worth of a subset of the objects in polynomial time.  If this
worth is less than $t$, then there clearly exists no subset of the
$s_i$ which adds up to $t$; if the total worth is equal to $t$, then
there does exist a subset which adds up to $t$.  The total worth
cannot be greater than $t$, since the subset's size would have to be
greater than $t$ and thus would not fit in the knapsack.

Thus, since the subset-sum problem is NP-complete, the knapsack
problem is NP-hard.


\item%(b)

Let's say that we have a knapsack of size $B$.  Let there be two
objects in our input set: one with size $B$ and value $v$, for some
value $v > 1$ that we choose, and another with size $B/2v$ and value
$1$.  Since $\frac{v}{B} < \frac{1}{B/2v}$, the greedy algorithm
chooses the object with size $B/2v$ first, and the other object
doesn't fit; thus, the greedy algorithm gives a total value of $1$.
On the other hand, the optimal solution would be to choose the object
with size $B$ and value $v$, which gives a total value $v > 1$.  Since
$v$ can be made arbitrarily large, the greedy algorithm could be made
to give an arbitrarily small fraction of the optimal total worth.


\item%(c)

Consider the fractional solution: at the time the greedy algorithm
first rejects an object {\em which could fit in the empty knapsack},
instead split the object and put the amount that fits into the rest of
the backpack.  It is not possible for any non-fractional solution to
have higher utility than this solution, because the fractional
solution has the greatest possible value per unit size for every unit
of size.  Thus, the optimal solution for the non-fractional case
cannot have greater value than the fractional solution.

Now, let us assume, for purposes of contradiction, that our new
improved algorithm is not a 2-approximation algorithm.  Then, both the
total value of the greedy solution $v_g$ and the value of the single
most valuable object that fits in the knapsack $v_1$ are less than
one-half of the optimal value $v_o$, since if either were greater than
one-half, the maximum of the two would have to be greater than
one-half.  Thus, since the optimal value is less than the value of the
fractional solution $v_f$, we know that both $v_g$ and $v_1$ are less
than $\frac{v_f}{2}$.

Since the fractional solution is achieved by taking the greedy
solution and adding a fraction $\phi$ ($0 < \phi < 1$) of the next
object which could fit in the empty knapsack, it is the case that
$v_f = v_g + \phi v_n$, where $v_n$ is the value of this next object.
Since $v_g < \frac{v_f}{2}$, we must have $\phi v_n > \frac{v_f}{2}$,
and since $\phi < 1$, $v_n > \frac{v_f}{2}$.  But then this single
object has value greater than half the value of the fractional
solution, which contradicts the assumption that the value of the
single most valuable object that fits in your knapsack is less than
half the value of the fractional solution.

Thus, the assumption is wrong, and we have proven that this algorithm
is a 2-approximation algorithm.

\end{enumerate}
\newpage




\section*{Problem 10-3}
\begin{enumerate}

\item%(a)

This is an open question: it depends on whether $P=NP$.

If $P=NP$, then it is true:  for any $L_1,L_2 \in NP$, both $L_1$ and
$L_2$ are in $P$.

If $P \neq NP$, then it is false:  there exists some $L_2$ which is
in NP but not in P.  Then, for every $L_1 \in P$, we have that
$L_1 <_p L_2$, but $L_2 \notin P$.  This is because any
language in P is polynomial-time reducible to any other language,
trivially.


\item%(b)

True:  this is a fundamental lemma of reducibility.  In fact, it is
lemma 36.3 on CLR page 931.


\item%(c)

True:  this is a rephrasing of the standard method of proving
NP-completeness, i.e. ``If $L_1$ is NP-complete, and $L_1 <_p L_2$,
and $L_2 \in NP$, then $L_2$ is NP-complete.''  It is lemma 36.8 on
CLR page 939.


\item%(d)

False:  $L_1$ and $L_2$ might both be outside of NP, but reducible in
polynomial time to each other.  For example, if we choose $L_1$ to be
some language outside of NP, we could choose $L_2$ to be equal to
$L_1$; this would trivially satisfy the conditions $L_1 <_p L_2$ and
$L_2 <_p L_1$, but clearly the languages could not be NP-complete,
since they are not in NP.


\item%(e)

True: if $L_1$ and $L_2$ are both NP-complete, then clearly $L_2$ is
in NP; and thus, by the definition of NP-completeness, $L_2 <_p L_1$,
since $L_1$ is NP-complete.


\end{enumerate}
\newpage




\section*{Problem 10-4}
\begin{enumerate}

\item%(a)

First, we must show that the directed Hamiltonian path problem is in
NP.  Given a graph $G = (V,E)$, let the certificate be the sequence of
$\|V\|$ vertices that make up the path.  The verification algorithm
checks that this sequence contains each vertex in $V$ exactly once and
that it forms a path in $G$ from $u$ to $v$; this can be done in
polynomial time.

We now must prove that if we could solve the directed Hamiltonian path
problem in polynomial time, then we could solve the Hamiltonian cycle
problem in polynomial time.

Let us consider an instance of the Hamiltonian cycle problem: an
undirected graph $G = (V,E)$.  For every edge $(u,v) \in E$, construct
a directed graph $G' = (V,E')$, where $(x,y) \in E'$ and $(y,x) \in E'$
if and only if $(x,y) \in E$ and $(x,y) \neq (u,v)$.  Hence, $G'$ is a
directed-graph version of the graph $G$ with the edge $(u,v)$ removed
(both forward and back edges in the directed graph).  This can clearly
be constructed in polynomial time; and, it can be used as a problem
instance of the directed Hamiltonian path problem with $u$ and $v$ as
the endpoints.

If there exists a directed Hamiltonian path in $G'$ for some endpoints
$(u,v)$ as specified above, then it is clear that there exists a
Hamiltonian cycle in the original graph $G$: simply take the sequence
of nodes returned by the path problem, and add the edge $(u,v)$ to
create a cycle in the undirected graph.  Conversely, if there exists a
Hamiltonian cycle in the graph $G$, then removing any edge $(u,v)$
from the cycle leaves a Hamiltonian path from $u$ to $v$ in the
directed graph $G'$.  Thus, there exists a directed Hamiltonian path
in $G'$ for some endpoints $u$ and $v$ such that $(u,v)$ is an edge in
$G$, if and only if there exists a Hamiltonian cycle in $G$.

Thus, we have provided a polynomial-time reduction from
Hamiltonian-cycle to directed-Hamiltonian-path.


\item%(b)

If the graph is a DAG, then it is simple to solve the directed
Hamiltonian path problem.  Perform a topological sort on the graph:
this can be done in linear time.  Then there exists a directed
Hamiltonian path from $u$ to $v$ in the graph if and only if $u$ is
the first element in the list, $v$ is the last, and there is an edge
between any two adjacent vertices in the list.  For, assume that that
is the case: then the Hamiltonian path from $u$ to $v$ consists of the
list produced by the topological sort.  On the other hand, if there
exists no edge between two adjacent vertices $x$ and $y$ (with $x$
coming before $y$), then no path in the graph can contain both $x$ and
$y$, since any path that contains $x$ must, if it continues, go on to
a vertex after $y$, and there are no back edges in the topologically
sorted list.  (And, if $u$ is not the first vertex, the first vertex
cannot be reached from any path starting at $u$; and if $v$ is not the
last vertex, then the last vertex cannot be touched by any path that
ends at $v$.)

To spell the algorithm out in pseudocode (although it's been described
sufficiently):

\begin{program}
|DAG-Directed-Hamiltonian-Path|(G, u, v)
\quad\tab V \gets |Topological-Sort|(G)
          \IF u \neq |First|[V] \OR v \neq |Last|[V]
             \THEN \RETURN \FALSE
                   \untab%
             \untab%
          \FOR i \gets 1 \rdots \|V\|-1
              \IF (V[i],V[i+1]) \notin E[G]
                 \THEN \RETURN \FALSE
                       \untab%
                 \untab%
              \untab%
          \RETURN \TRUE
\end{program}

Correctness is guaranteed by the above if-and-only-if relation;
termination is guaranteed by the explicit bounds on the loop.  The run
time is linear in the size of the input graph, since
$|Topological-Sort|$ runs in linear time, and the loop has at most
$\|V\|$ iterations.


\end{enumerate}
\newpage




\section*{Problem 10-5}
\begin{enumerate}

\item%(a)

True.  If the runtimes of all subroutines are bounded above by
$f(n) = O(n^k)$ and the output sizes are bounded by $g(n) = O(n^l)$,
and the algorithm $A$ makes a constant number of calls $c$ to
subroutines, then the run time of the algorithm $A$ is bounded by
$c f(n) = O(n^k)$ (and the output size is bounded by $c g(n) = O(n^l)$).
Thus $A$ runs in polynomial time.


\item%(b)

True.  If the runtimes of all decision-procedure subroutines are
bounded above by $f(n) = O(n^k)$, and the algorithm $A$ makes a
polynomial number of calls $F(n) = O(n^K)$ to subroutines, then the
run time of the algorithm $A$ is bounded by $F(n) f(n) = O(n^{k+K})$
(and the output size is bounded by $F(n) = O(n^K)$).  Thus $A$ runs in
polynomial time.


\item%(c)

True.  If the runtimes of all decision-procedure subroutines are
bounded above by $f(n) = O(n^k)$ and the output sizes are bounded by
$g(n) = O(n^l)$, and the algorithm $A$ makes a polynomial number of
calls $F(n) = O(n^K)$ to subroutines, then the run time of the
algorithm $A$ is bounded by $F(n) f(n) = O(n^{k+K})$ (and the output
size is bounded by $F(n) g(n) = O(n^{l+K}$).  Thus $A$ runs in
polynomial time.


\end{enumerate}
\newpage




\end{document}
