\documentclass{article}
\usepackage{graphicx} 
 
\begin{document} 
 
\noindent CS140: Exam 3 \hfill Name \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \\ 
\noindent 4/26/01 
 
\vspace{1 in} 
 
This exam consists of 6 problems and 14 pages.  Before you begin the exam 
make sure your copy is complete.   
The exam is designed to be finished in under 3 hours but you may use 
up to 24 hours to complete the test. 
The test must be turned in by the end of the end of the day Sunday,
April 29.  You will receive 5 bonus points for turning in the exam at
least 24 hours early.
\vspace{1 in} 
 
Write your name above.   
Write the day and time that you start and stop the exam in the space provided. 
 
\vspace{.2 in} 
\noindent Start Day/Time \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \\ 
 
\vspace{.2 in} 
\noindent End Day/Time \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \\ 
  
\vspace{1 in} 
Your answers will be  
judged for clarity, conciseness, and correctness.  The space provided  
should be adequate for your solutions.   
 You should use some of the extra 
time allotted for the exam to write your answers carefully.  Illegible, confusing, 
and/or incomplete ideas will be judged harshly.   
 
You may use a one page cheat sheet but no other texts, notes, web pages, etc. during this 
exam. You may not discuss the exam with anyone.  
 
The next page of the exam gives the definition of several NP-hard problems you may 
find useful. 
 
Good luck! 
 
\pagebreak 
 
\vspace{. in} 
Here are some NP-hard problems you may want to use in completing this exam. 
 
\begin{enumerate} 
\item 
Vertex Cover 
\begin{description} 
\item[Input:] 
A graph $G=(V,E)$ and an integer $K$ 
\item[Question:] 
Is there a subset $W\subseteq V$ containing at most $K$ vertices such that every 
edge of $G$ is incident to some vertex in $W$? 
\end{description} 
\item 
3-Colorability 
\begin{description} 
\item[Input:] 
A graph $G=(V,E)$ 
\item[Question:] 
Can the vertices of $G$ be colored {\em red, green,} and {\em blue} so that no 
adjacent vertices have the same color. 
\end{description} 
\item 
Hamiltonian Path 
\begin{description} 
\item[Input:] 
A graph $G=(V,E)$ 
\item[Question:] 
Does $G$ contain a simple path that includes every vertex? 
\end{description} 
\item 
3SAT 
\begin{description} 
\item[Input:] 
A boolean formula ${\cal F}$ in conjunctive normal form in which every clause 
contains exactly 3 literals. 
\item[Question:] 
Is ${\cal F}$ satisfiable? 
\end{description} 
\end{enumerate} 
 
\pagebreak 
 
\begin{enumerate} 
\item 
Following is a flow network with a feasible flow.  Note:  The label 
$X/Y$ on an edge indicates that the flow is $X$ and 
the capacity is $Y$. 

\begin{figure}[h] 
\centering
\includegraphics{netfig} 
\end{figure} 

\begin{enumerate} 
 
\item 
Draw the residual graph. 
\vspace{2 in} 
\pagebreak 
\item 
Find an augmenting path in the network. List the vertices of the path in order below. 
\vspace{1 in} 
\item 
Augment the flow along this path as much as possible.  Draw the network with the augmented 
flow below.   
\end{enumerate} 
\pagebreak 
 
\item 
Construct a weighted graph $G$ with distinct edge weights and containing a vertex $s$ such that  
the Minimum Spanning Tree of G is not a Shortest Path Tree for s.  Draw both the Minimum Spanning 
Tree and a Shortest Path Tree for S. 
\pagebreak 
\item 
 
I've run the DFS algorithm on a directed graph $G$ and constructed the following timestamp table. 
 
\begin{tabular}{ccc} 
Vertex & First Arrival 	& Last Departure \\ 
a	&  1 & 6\\ 
b	&  2 &  5\\ 
c	&  3 &  4\\ 
d	& 7 & 10\\ 
e	& 8 & 9 \\ 
\end{tabular} 
 
For each of the following statements, state whether the timestamp table implies that the statement 
is necessarily true, 
necessarily false, or if neither implication is made. 
 
\begin{enumerate} 
\item 
Vertices $a$ and $c$ are strongly connected. 
\item 
Vertices $a$ and $d$ are strongly connected. 
\item 
Vertex $a$ is reachable from vertex $d$. 
\item 
Vertex $d$ is reachable from vertex $a$. 
\end{enumerate} 
\pagebreak 
 
\item 
The Isomorphic Subtree problem is defined as follows. 
 
\begin{description} 
\item[Input:] 
A graph $G$ and a tree $T$. 
\item[Question:] 
Is there a subset $W$ of vertices of $G$ such that the subgraph of $G$ 
induced by $W$ is exactly $T$? 
\end{description} 
\begin{enumerate} 
\item 
Show that the Isomorphic Subtree problem is in NP. 
\vspace{2 in} 
\item 
Give a yes-instance of the problem. 
\vspace{2 in} 
\item 
Give a no-instance of the problem. 
\vspace{2 in} 
\pagebreak 
\item 
Show that the Isomorphic Subtree problem is NP-hard by giving a polynomial-time 
reduction from one of the NP-hard problems described in the instructions of this exam. 
\begin{enumerate} 
\item 
Which NP-hard problem will you use? 
\vspace{1 in} 
\item 
Given an input X of the selected problem, how do you construct the input $G, T$ for 
the Isomorphic Subtree problem?  Show that the reduction can be done in polynomial-time. 
\vspace{3 in} 
\item 
Suppose the input X of the selected problem is a yes-instance.  Prove that the instance 
$G,T$ of Isomorphic Subtree created by your reduction is also a yes-instance. 
\vspace{3 in} 
\item 
Suppose that the instance $G,T$ of Isomorphic Subtree created by your reduction is a yes-instance. 
Prove that the original instance $X$ of the selected problem is also a yes-instance. 
\end{enumerate} 
\end{enumerate} 
\pagebreak 
 
\item 
The Bipartite Cover Problem is defined as follows. 
\begin{description} 
\item[Input:] 
A bipartite graph $G=(U,V,E)$ and an integer $K$. 
\item[Question:] 
Is there a subset $W \subseteq U$ such that $||W|| \le K$ and 
every vertex in $V$ is adjacent to some vertex in $W$? 
\end{description} 
\begin{enumerate} 
\item 
Show that the Bipartite Cover problem is in NP. 
\vspace{2 in} 
\item 
A search version of this problem takes as input a bipartite graph $G=(U,V)$ and outputs 
a smallest subset $W\subset U$ such that every vertex in $V$ is adjacent to some vertex in 
$U$.  Give a polynomial-time reduction from this search problem to the decision problem. 
\pagebreak 
\item 
Show that the Bipartite Cover problem is NP-hard by giving a polynomial-time 
reduction from one of the NP-hard problems described in the instructions of this exam. 
\begin{enumerate} 
\item 
Which NP-hard problem will you use? 
\vspace{1 in} 
\item 
Given an input X of the selected problem, how do you construct the input $G, K$ for 
the Bipartite Cover problem?  Show that the reduction can be done in polynomial-time. 
\vspace{3 in} 
\item 
Suppose the input X of the selected problem is a yes-instance.  Prove that the instance 
$G,K$ of Bipartite Cover created by your reduction is also a yes-instance. 
\vspace{3 in} 
\item 
Suppose that the instance $G,T$ of Bipartite Cover created by your reduction is a yes-instance. 
Prove that the original instance $X$ of the selected problem is also a yes-instance. 
\end{enumerate} 
\end{enumerate} 
\pagebreak 
\item 
The Shortest Common Supersequence  problem is defined as follows. 
\begin{description} 
\item[Input:] 
A set of strings $S=\{s_1, s_2, \ldots, s_n\}$ over an alphabet $\Sigma$ and an integer $K$. 
\item[Question:] 
Is there a string of length at most $K$ that contains each $s \in S$ as a subsequence? 
\end{description} 
For example $abcd$ is a shortest string that contains $ac$ and $bd$ as subsequences.   
(Other strings work as well.) 
\begin{enumerate} 
\item 
Find a shortest string that contains $aba$, $cb$, and $caa$ as subsequences. 
\vspace{1 in} 
\item 
Show that the Shortest Common Supersequence problem is in NP. 
\vspace{1 in} 
\item 
Show that the Shortest Common Supersequence problem is NP-hard by giving a reduction 
from Vertex Cover. 
\begin{enumerate} 
\item 
Given an instance $G=(V,E),K$ of Vertex Cover, show how to create the instance $S,K'$ of 
Shortest Common Supersequence.  Hint:  Let $\Sigma = V$; i.e. there is a unique symbol for 
each vertex of the graph. 
\vspace{3 in} 
\item 
Suppose that $G,K$ is a yes-instance of Vertex Cover.  Prove that the instance $S,K'$ 
of Shortest Common Supersequence created by your reduction is also a yes-instance. 
\vspace{3 in} 
\item 
Suppose that the instance $S,K'$ of Shortest Common Supersequence produced by your reduction 
is a yes-instance.  Prove that the input $G,K$ is a yes-instance of Vertex Cover. 
\end{enumerate} 
\end{enumerate} 
\end{enumerate} 
 
\end{document} 
