\documentclass{article}
\usepackage{graphicx}

\begin{document}

\noindent CS140: Exam 3 \hfill Name \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \\
\noindent 12/6/01

\vspace{1 in}

This exam consists of 4 problems and 21 pages.  Before you begin the exam
make sure your copy is complete.  You have four hours to complete this exam. 
The exam must be turned in by Sunday morning at 10AM.
 

Your answers will be 
judged for clarity, conciseness, and correctness.  The space provided 
should be adequate for your solutions.  


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!

\vspace{1 in}

Write your name above.  
Write the day and time that you start and stop the exam in the space provided.

\vspace{1 in}
\noindent Start Day/Time \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \\

\vspace{.2 in}
\noindent End Day/Time \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \\
 
\vspace{2 in}


\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 $K$ or fewer vertices such that every
edge of $G$ is incident to some vertex in $W$?
\end{description}

\item
Dominating Set
\begin{description}
\item[Input:]
A graph $G=(V,E)$ and an integer $K$
\item[Question:]
Is there a subset $W \subseteq V$ containing $K$ or fewer vertices such that every vertex
of $G$ is either in $W$ or adjacent to a 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
A star on $n$
vertices is a tree in which no more than one node has degree greater than one.
Following are examples of stars for $n=1,3,$ and $9$.

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

\vspace{.5 in}
\noindent The Star Partition problem (SP) is defined as follows:
\begin{description}
\item[Input:]
Connected graph $G=(V,E)$ and integer $K$.
\item[Question:]
Can the vertices of $G$ be partitioned into $K$ or fewer sets $V_1, \ldots , V_k$
so that the induced subgraph on each $V_i$ contains a star on $||V_i||$ nodes?

\end{description}

For example, the following graphs contain a star on $4$ nodes.

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

\vspace{.5 in}
\begin{enumerate}

\item
State whether the following is a yes or a no instances of SP.

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

\pagebreak

\item
Prove that SP is in NP.
\vspace{1 in}




\item
Consider the following search variant of SP.
\begin{description}
\item[Input:]
Connected graph $G=(V,E)$
\item[Output:]
A partition $V_1, \ldots, V_k$ of $V$ such that $k$ is as small as possible and
the subgraph of $G$ induced by each $V_i$ contains a star on $||V_i||$ nodes.
\end{description}
Give a polynomial-time reduction from this search problem to the decision problem.

\pagebreak
\item
Show that SP is NP-hard by giving a polynomial time reduction from one of the NP-complete
problems described at the beginning of this exam.  More specifically, answer the following questions.   
\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
SP?  Show that the construction can be done in polynomial-time.
\vspace{3 in}

\pagebreak
\item
Suppose the input X of the selected problem is a yes-instance.  Prove that the instance
$G,K$ of SP created by your reduction is also a yes-instance.
\vspace{3 in}
\item
Suppose that the instance $G,K$ of SP created by your reduction is a yes-instance.
Prove that the instance $X$ of the selected problem is also a yes-instance.
\end{enumerate}
\end{enumerate}
\pagebreak

\item
The Hitting String (HS) problem is defined as follows.
\begin{description}
\item[Input:]
A set of strings $C$ over the alphabet $\{0,1,2\}$, all having the same length
$n$.
\item[Question:]
Is there a string $x$ over the alphabet $\{0,1\}$ such that $x$
has length $n$ and for each $y \in C$ there is some $i$ such that the
$i$th symbol of $x$ and $y$ agree?
\end{description}

\begin{enumerate}
\item
The following is a yes-instance of HS.  Prove it by giving an appropriate
string $x$ over $\{0,1\}$.  (Note that $x$ cannot contain the symbol $2$.)
\begin{displaymath}
C = \{ 0112, 1102, 0001, 2020, 2101\}
\end{displaymath}

\vspace{1 in}

\item
Give a no-instance of HS.
\vspace{1 in}

\item
Show that HS is in NP.
\vspace{1 in}

\pagebreak
\item
Show that HS is NP-hard by giving a reduction from 3SAT.  More specifically, answer the following questions.
\begin{enumerate}
\item
Given an input ${\cal F}$ of 3SAT, how do you construct the input $C$ for
HS?  Show that the construction can be done in polynomial-time.
\vspace{3 in}

\pagebreak
\item
Suppose the input ${\cal F}$ is satisfiable.  Prove that the instance
$C$ of HS created by your reduction is also a yes-instance.
\pagebreak
\item
Suppose that the instance $C$ of HS created by your reduction is a yes-instance.
Prove that the formula ${\cal F}$ is satisfiable.
\end{enumerate}

\end{enumerate}

\pagebreak

\item
The Maximum Leaf Spanning Tree (MLST) problem is defined as follows.
\begin{description}
\item[Input:]
A connected graph $G=(V,E)$ and an integer $K$
\item[Question:]
Is there a spanning tree of $G$ in which $K$ or more vertices have degree 1?
\end{description}
\begin{enumerate}
\item
Give a yes-instance of MLST.
\vspace{1 in}
\item
Give a no-instance of MLST.
\vspace{1 in}
\item
Show that MLST is in NP.
\pagebreak
\item
Consider the following search problem.
\begin{description}
\item[Input:]  Connected graph $G=(V,E)$
\item[Output:]  A spanning tree of $G$ with a maximum number of degree 1 vertices.
\end{description}
Give a polynomial time reduction from the search problem to the decision problem.
\pagebreak
\item
Show that MLST is NP-hard by giving a polynomial-time
reduction from Dominating Set.  More specifically, answer the following questions.
\begin{enumerate}
\item
Given an input $G,K$ of DS, how do you construct the input $G', K'$ for
the MLST problem?  Show that the reduction can be done in polynomial-time.
\pagebreak
\item
Suppose $G,K$ is a yes-instance of DS.  Prove that the instance
$G',K'$ of SP created by your reduction is also a yes-instance.
\vspace{3 in}
\pagebreak

\item
Suppose that the instance $G'K'$ of MLST created by your reduction is a yes-instance.
Prove that the instance $G,K$ of DS is also a yes-instance.
\end{enumerate}
\end{enumerate}
\pagebreak
\item
The Max Cut (MC) problem is defined as follows.
\begin{description}
\item[Input:]
A graph $G=(V,E)$ with positive (integer) edge weights and an integer $K$.
\item[Question:]
Is there a cut of $G$ such that the total weight of the edges spanning the
cut is at least $K$?
\end{description}

(Recall that a cut of a graph is a partition of its vertices into two
sets $S_1$ and $S_2$.  An edge spans the cut if it has one endpoint in
$S_1$ and the other in $S_2$.)

\begin{enumerate}
\item
Give a yes-instance of MC.
\vspace{1 in}
\item
Give a no-instance of MC.
\vspace{1 in}
\item
Prove that MC is in NP.
\pagebreak
\item
This problem is NP-hard and remains so even if we restrict the edges
weights to be either $1$ or $m$, where $||E||=m>1$.
Prove that this restricted verion of MC is NP-hard by giving a polynomial-time reduction from
3SAT.  More specifically, answer the following questions.
\begin{enumerate}
\item
Suppose that $G=(V,E),~~K$ is an instance of MC where $K= \ell m +j$ for
some $\ell \ge 0$ and $0 \le j <m$.  Give a necessary condition  on
the edge weights of $G$ for it to be a yes-instance.  (This question is intended to be a hint to help you in the reduction so make sure you figure it out before you go on.)
\pagebreak
\item
Design a ``truth-setting'' gadget.  (Hint:  Rather than calling the partition sets $S_1$ and $S_2$ you may want to call them $T$ and $F$!)
\vspace{3 in}
\item
Design a ``clause-testing'' gadget.  (Hint:  Think triangles.)
\pagebreak
\item
Complete the reduction and show that it can be done in polynomial-time.
\pagebreak
\item
Suppose ${\cal F}$ is a satisfiable 3SAT formula.  Show that the instance
$G,K$ of MC created by your reduction is a yes-instance.
\pagebreak
\item
Suppose the instance $G,K$ of MC created by your reduction on input
${\cal F}$ is a yes-instance.  Show that ${\cal F}$ is satisfiable.
\end{enumerate}
\end{enumerate}

\end{enumerate}

\end{document}
