\documentclass[11pt,psfig]{article}
%\pagestyle{empty}
%\input{psfig}
\usepackage{amssymb,epsfig}
\oddsidemargin -5mm
\evensidemargin -5mm
\textwidth 17cm
\usepackage{a4wide}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{mainresult}[theorem]{Main Result}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim} \newenvironment{proof}{\noindent
  {\bf Proof }}{\qed} \newtheorem{definition}[theorem]{Definition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{conjecture}[theorem]{Conjecture}
\newcommand{\qed}{\penalty 1000 \hfill\penalty
  1000$\rule{2mm}{2mm}$\par\medskip} \newcommand{\floor}[1]{\lfloor
  {#1} \rfloor} \newcommand{\ceiling}[1]{\lceil {#1} \rceil}
\newcommand{\ZZ}{\mbox{\bf Z}} \newcommand\set[1]{\left\{#1\right\}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\comment}[1]{}
\newcommand{\NP}{\mbox{${\cal NP}$}}
\newcommand{\p}{\mbox{${\cal P}$}}

\begin{document}
\begin{flushright}
{\sc Design and Analysis of Algorithms} \\
({\sc CSCE 423/823, Spring 2005})\\
{ URL: {\small\tt http://www.cse.unl.edu/$\sim$vinod/823S05/index.html}}\\
{\it 1st April, 2005}
\end{flushright}

\vspace{-1.6cm}
\begin{flushleft}
{\Large\bf Homework 5} \\
{\bf Due on 15th April, 2005}
\end{flushleft}
\vspace{-1mm}
\hrule
\vspace{2mm}
\begin{flushright}
\begin{tabular}{rcl}
Name &:& \hspace{5cm} \\[.5cm] Student ID &:& \hspace{4cm}\\[.5cm]
Course No & : & ~~~{\bf 423}\hspace{1.2cm} {\bf 823} \end{tabular}
\end{flushright}

\vspace*{-.5cm}
\section*{Instructions}
%\vspace*{-.2cm}
\begin{enumerate}
\item[-] Write your name and student ID on the space provided. Circle
the course number in which you are registered. Return this
sheet with your solutions.\\[-.7cm]
\item[-] Clarity of presentation is utmost important. You should give a
clear description of all your algorithms with an analysis of their
time complexity.\\[-.7cm]
\item[-] {\sc No collaboration with any one is permitted for CORE
problems!}. See the Instructor or the TA if you need additional
guidance. You may discuss approaches to solving {\sc ADVANCED}
problems with your classmates. However, you must write up your own
solutions in your own words and acknowledge any one with whom you
collaborated.
\end{enumerate}
\vspace*{-.3cm}
\subsection*{\sc Core Problems}
\begin{enumerate}
\item (9 Points) Let ${\cal P}$ denote the set of decision problems
solvable in polynomial time, and ${\cal NP}$ denote the set of
decision problems which can be verified in polynomial time
(non-deterministic polynomial time).  Suppose $P_{1}$ and $P_{2}$ are
decision problems and $P_{1}$ is polynomial time reducible to
$P_{2}$. That is, $P_1\leq_{p}P_2$. For each of the following give
``Yes/No/Not necessary'' answer and justify.

\begin{enumerate}
\item If $P_{1}$ is in $\p$, is $P_{2}$ in $\p$?

\item If $P_{2}$ is in $\p$, is $P_{1}$ in $\p$?

\item If $P_{1}$ is $\NP$-complete, is $P_{2}$  $\NP$-complete?

\item If $P_{2}$ is $\NP$-complete, is $P_{1}$  $\NP$-complete?

\item If $P_{2}$ is polynomially transformable to $P_{1}$, are
$P_{1}$ and $P_{2}$ both $\NP$-complete?

\item If $P_{1}$ and $P_{2}$ are $\NP$-complete, is $P_{2}$
polynomially transformable to $P_{1}$?

\item If $P_{1}$ is in $\NP$, is $P_{2}$ $\NP$-complete?

\item If $P_{1}$ is not in $\NP$, is $P_{1}$ not in $\p$?

\item If $P_{2}$ is not in $\p$, is $P_{2}$ not in $\NP$?

\end{enumerate}

\item (7 Points) Show that the following problem known as {\sc Set
Partition} problem is $\NP$-Complete.

\noindent\textbf{Input:} A set of numbers, $X$.\\
\noindent\textbf{Question:} Is it possible to partition $X$ in to
subsets $Y$ and $Z$, such that $Y \bigcup Z = X$ and $Y \cap Z = {\O}$
so that summation of elements in $Y$ equals that of elements in $Z$;
that is $\Sigma_{a\in Y} a = \Sigma_{a\in Z} a$?

\item (7 Points) An independent set of $G = (V, E)$ is a subset $V'$
of $V$ such that $G$ has no edge between any pair of
vertices in $V'$. Consider the decision problem known as {\sc
Independent Set} problem.

\noindent\textbf{Input:} A  graph $G(V,E)$ and an integer $k > 0$\\
\noindent\textbf{Question:}Does $G$ have an
independent set of size $\geq k$?

Prove that {\sc Independent Set} Problem is NP-Complete. (Use Clique
problem described in the lecture to do so).

\item (5 Points) The {\sc Subgraph Isomorphism} problem takes
two graphs $G_{1}$ and $G_{2}$ and asks whether $G_{1}$ is
isomorphic to a subgraph of $G_{2}$. Show that the
subgraph-isomorphism problem is NP-complete.

\item (7 Points) Let $G = (V, E)$ be a directed graph. A set $F
\subseteq V$ is a feedback vertex set if every cycle of $G$ contains a
vertex in $F$. The {\sc Feedback Vertex Set} problem is defined as
follows:

\textbf{Instance:} Directed graph $G = (V, E)$ and positive integer $k$.\\
\textbf{Question:} Does $G = (V, E)$ have a feedback vertex set with at most $k$ vertices?

Use the {\sc Vertex Cover} problem described in the class to show that
{\sc Feedback Vertex Set} problem is NP-complete.

\end{enumerate}
\subsection*{\sc Advanced Problems}
\begin{enumerate}
\setcounter{enumi}{5}

\item (10 Points; Problem 34.5.3 of the text; page 1017). The
integer linear-programming problem is like the 0-1
integer-programming problem, except that the values of the vector
$x$ may be any integers rather than just 0 and 1. Assuming that
0-1 integer-programming problem is NP-Complete, show that the
integer linear-programming problem is NP-Complete.

\item (5 Points) The class Co-$\NP$ is the class of decision problems
whose {\em complement} problems are in \NP.  For example, consider the
\NP\ problem SAT whose complement problem is the decision problem
$\overline{\rm SAT}$ for which the ``Yes'' instances are those Boolean
formulae which are {\em not} satisfiable. Identical to the definition
of \NP-completeness we can define Co-$\NP$-completeness.

Show that $L$ is complete for NP if and only if $\overline{L}$ is
complete for Co-NP.

\comment{
\item Let $P_{1}$ and $P_{2}$ be two problems such that $P_{1}$ is
polynomially reducible to $P_{2}$. Suppose that $P_{2}$ can be
solved in $O(n^{k})$ time and the reduction can be done in
$O(n^{j})$ time. Is it possible to conclude the time complexity of
$P_{1}$? If yes, what is it? Reason your answer.

\end{enumerate}}
\end{enumerate}

\end{document}
