

\documentclass[11pt]{article}
\setlength{\parskip}{0.5em}
\setlength{\parindent}{0em}


\marginparwidth 0pt
\oddsidemargin -0.4in
\marginparsep 0pt
\topmargin  -0.6in
\textwidth   7.2in
\textheight  9.1in

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[xdvi,dvips]{graphics}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{array}
\usepackage{float}
\usepackage{dsfont}
\usepackage{xspace}

\input{preamble}
%\input{special}

\newcounter{jump}

\newcounter{tbl}
\newcounter{fgr}[section]

\renewcommand{\thefgr}{\thesection.\arabic{fgr}}

\newcounter{mdl}
\newcounter{prp}
\newcounter{action}
\newcounter{priority}
\newcounter{benchmark}


\renewcommand{\theaction}{{\rm{\Alph{mdl}}\arabic{action}}}

\renewcommand{\Label}{\label}
\renewcommand{\Ref}{\ref}

\renewcommand{\today}{}

\begin{document}


\title{Reduction of the Independent Set Problem to the Knapsack Problem}


\author{}

\maketitle

%{\tt
%\vskip 0.2in
%\input{tempdt}
%}

\date{}

\vskip 0.4in

We define an instance of the {\em knapsack problem\/} to consist of
a number $C$, and a list of positive numbers $X = x_\malyone, \ldots x_\malyp$.
The ordered pair $(C,X)$ is a member of the language {\em Knapsack\/} if
there is some set of numbers $S$ in the range $\braced{1,\ldots p}$ such
that $\sum\braced{x_\malyi\suchthat i\in S}=C$.

We first prove that Knapsack is $\calN\calP$, using the certificate method.
If $(C,X)\in$Knapsack, then the set $S$ itself is a certificate, and
verification program is straightforward: simply add the weights.

We define a $\calP$-{\sc time} reduction $R$ of IND to Knapsack, where
IND is the independent set problem.

We assume that all of our languages (problems) are over $\Sigma=\braced{0,1}$,
the binary alphabet.  and each reduction must be a function
$$R:\Sigma^*\to\Sigma^*$$.
When we define $R(w)$ below, we will assume that $w$ is
an instance of the independent set problem.  If $w$ is any other string,
we define $R(w)=\varepsilon$, the empty string.  No further discussion of
this case is necessary.

Let $G=(V,E)$ be a graph, and $k$ a number.  Then $\angled{G}\angled{k}$
is an instance of the independent set problem.
We define $R\parend{\angled{G}\angled{k}}$, an instance of the
knapsack problem, as follows.

Write $V=\braced{v_\malyone, \ldots v_\malyn}$ and
$E=\braced{e_\malyone, \ldots e_\malym}$,
the vertices and edges of $G$, respectively.
We say that $v_\malyi$ {\em meets\/}
$e_\malyi$ if $v_\malyi$ is one of the two end points of $e_\malyj$.
%Without loss of generality, $k\le n$, since if $k>n$, no set of size $n$
%can have a subset of size $k$.  

We will have two classes of entries in our list $X$, those derived from
vertices of $G$, and those derived from edges of $G$.  We call these
$Y=y_\malyone, \ldots y_\malyn$ and $z_\malyone\ldots z_\malym$.
We will then let $p=n+m$, and $X=Y+Z$, the concatenation of the two lists.
More formally:

\begin{itemize}
\item
For any $1\le i\le n$,
let $y_i=10^{m+1}+\sum\braced{10^j\suchthat v_\malyi\spacedromn{meets}e_\malyj}$.
\item
For any $1\le j\le m$, let $z_\malyj = 10^j$

\item
For any $1\le \ell \le n+m$, we define
$x_\maly{\ell} = \leftbracedtwo{y_\maly{\ell} \spacedromn{if} \ell\le n}
{z_\maly{n+\ell} \spacedromn{otherwise}}$
Then, let $X = x_\malyone, \ldots x_{\malyn+\malym}$.
\item
Let $C = k\,10^{m+1}+\sum_{j=1}^m10^j$
\end{itemize}

By the following two lemmas, $R$ is a reduction of IND to Knapsack.

\begin{lemma}\label{lem: IND implies Knapsack}
If $G$ has an independent set of size $k$, then
$(C,X)\in Knapsack$.
\end{lemma}

\begin{proof}
Suppose $\calI$ is a set consisting of $k$ vertices of $G$.
Let $\calJ$ be the set of edges which do not meet any of the vertices
in $\calI$.
Define
\begin{itemize}
\item
$Y=\braced{y_i\suchthat v_i\in\calI}$
\item
$Z=\braced{z_j\suchthat e_j\in\calJ}$
\item
$X=Y\cup Z$
\end{itemize}
We claim that
 $\sum X = C$.  We analyze the sum by examining ``places,"
just like we did in elementary school.

We first examine places 1 through $m$, namely the coefficients of $10^j$
for each $j$.  If there is some vertex $v_\malyi$ that meets $e_\malyj$,
$y_\malyi$ contributes 1 to that place.  Since $\calI$ has at most one
vertex which meets $e_\malyj$, and since $e_\malyj\notin\calJ$, the coefficient
of $X$ in the $j^\tH$ place is 1, just as in $C$.
On the other hand, if there is no vertex that meets $e_\malyj$, then
there is no $y_\malyi$ which contributes to the $j^\tH$ place of $\sum X$,
but $z_\malyj$ does contribute a 1 in that place.  In either case, $\sum X$
and $C$ agree in the $j^\tH$ place.

Finally, we note that, disregarding those first $m$ places, $\sum X$ has
$k$ copies of $10^{m+1}$, as does $C$, and we are done.
\end{proof}

\subsection*{Example}
Let $G$ be the graph illustrated below, where $n=6$ and $m=8$.  Let $k=3$.
The set $\calI=\braced{v_\malyone,v_\malythree,v_\malysix}$ is an independent
set of vertices of $G$ of size $k$.
In our reduction, $\calJ=\braced{e_\malyfour,e_\malyseven}$.
We write $k$ and all the weights in base $10$.  The first array
shows the weights of all items, while the second array shows that the
weights of the selected items sum to $C$

\vskip 0.11in
$\begin{array}{lc cccccccccc}
C & = &3&1 &1 &1 &1 &1 &1 &1 &1 &0 \\
y_\malyone   & = &1&0 &0 &1 &0 &0 &1 &0 &1 &0 \\
y_\malytwo   & = &1&0 &0 &0 &0 &1 &0 &1 &1 &0 \\
y_\malythree & = &1&0 &0 &0 &1 &0 &0 &1 &0 &0 \\
y_\malyfour  & = &1&0 &0 &0 &1 &0 &0 &1 &0 &0 \\
y_\malyfive  & = &1&1 &1 &1 &0 &0 &0 &0 &0 &0 \\
y_\malysix   & = &1&1 &0 &0 &0 &0 &0 &0 &0 &0 \\
z_\malyone   & = &0&0 &0 &0 &0 &0 &0 &0 &1 &0 \\
z_\malytwo   & = &0&0 &0 &0 &0 &0 &0 &1 &0 &0 \\
z_\malythree & = &0&0 &0 &0 &0 &0 &1 &0 &0 &0 \\
z_\malyfour  & = &0&0 &0 &0 &0 &1 &0 &0 &0 &0 \\
z_\malyfive  & = &0&0 &0 &0 &1 &0 &0 &0 &0 &0 \\
z_\malysix   & = &0&0 &0 &1 &0 &0 &0 &0 &0 &0 \\
z_\malyseven & = &0&0 &1 &0 &0 &0 &0 &0 &0 &0 \\
z_\malyeight & = &0&1 &0 &0 &0 &0 &0 &0 &0 &0 \\
\end{array}$
\hspace*{0.2in}
\begin{minipage}{2.6in}
\centerline{\epsfig{file=knpsck.eps,width=1.8in}}
\vskip 0.47in
$\begin{array}{lc cccccccccc}
x_\malyone   & = &1&0 &0 &1 &0 &0 &1 &0 &1 &0 \\
x_\malythree & = &1&0 &0 &0 &1 &0 &0 &1 &0 &0 \\
x_\malysix   & = &1&1 &0 &0 &0 &0 &0 &0 &0 &0 \\
y_\malyfour  & = &0&0 &0 &0 &0 &1 &0 &0 &0 &0 \\
y_\malyseven & = &0&0 &1 &0 &0 &0 &0 &0 &0 &0
\rule[-0.08in]{0in}{0.04in} \\
\hline
C & = &3&1 &1 &1 &1 &1 &1 &1 &1 &0
\rule{0in}{0.16in}
\end{array}$
\end{minipage}

\end{document}

