\documentclass{article}
\pagestyle{empty} 
 
\begin{document} 
\begin{center} 
{\LARGE CS140: Algorithms }\\ 
\vspace{.1 in} 
{\Large Spring 2001}\\ 
\vspace{.3 in} 
{\large Assignment 11} 
\end{center} 
 
\noindent 
This assignment is due by the start of class on Tuesday, April 17.  You may collaborate 
with your classmates to complete this assignment but you must reference your collaborators.  In addition, 
you must do your own write-up.  This assignment is worth 100 points (65 points if handwritten).   
 
\begin{enumerate} 
\item 
(Trivial) 
The Largest Common Subgraph problem is defined as follows. 
\begin{description} 
\item[Input:]   
Graphs $G_1$ and $G_2$ and integer $k$, 
\item[Question:] 
Is there a graph $G$ containing at least $k$ edges that is a subgraph 
of both $G_1$ and $G_2$. 
\end{description} 
\begin{enumerate} 
\item 
Give a Yes-instance of LCS. 
\item 
Give a No-instance of LCS. 
\item 
Cast this problem as a search problem.  Show that the search 
problem is polynomial-time equivalent to the decision problem. 
\item 
Show that LCS is in NP. 
\item 
Show that LCS is NP-complete by giving a reduction from one of 
the NP-complete problems we discussed in class. 
\end{enumerate} 
\item 
(Easy) 
Repeat the above exercise for the Minimum Sum of Squares problem defined 
below. 
\begin{description} 
\item[Input:] 
A set $A$ of integers and two additional integers $K$ and $J$. 
\item[Question:] 
Can the elements of $A$ be partitioned into $K$ disjoint sets $A_1, A_2, \ldots, A_K$ 
such that  
$\sum_{i=1}^K (\sum_{s \in A_i} s)^2 \le J$? 
\end{description} 
\item 
Repeat the previous exercise for the Steiner Tree in Graphs problem defined below. 
(Hint:  Reduce from Vertex Cover.) 
\begin{description} 
\item[Input:] 
A graph $G$, a subset $R$ of the vertices of $G$, and an integer $K$. 
\item[Question:] 
Is there a subtree (not necessarily a spanning tree) of $G$ that includes 
the vertices $R$ and at most $K$ edges? 
\end{description}  
\item 
 
\end{enumerate} 
   
 
\end{document} 
