Prove that Weighted Independent Set is NP Complete using Independent Set?

Question

$k$-Weight Independent Set
Input: A vertex weighted graph $G=(V,E,w)$ and an integer $k$.
Question: Is the a set $V'\subset V$ such that $V'$ is an independent set and $\sum_{v\in V'} w(v) \geq k$?

Showing that this problem is in NP is trivial, but I'm suck on showing that $X \Longleftrightarrow Y$. The forward direction is simple I think.

$\Longrightarrow$ If you have a $k$-Independent Set, then we know that each node has a weight that is a natural number ( $\ge 1$ ), so the graph has weighted independent set of at least $k$.

But how would you show the reverse direction $\Longleftarrow$?

Answer 1

You reduce to this problem quite easily from the Independent Set problem.

Given a graph $G=(V,E)$ and a natural number $k$ define a simple weight function $w:V\to\mathbb{R}$ by

$$\forall v\in V:w(v)=1$$

The output of the reduction is $\langle G'=(V,E,w),k\rangle$.

If $G$ has an Independent set $S$ of size at least $k$ then $S$ is an independent set in $G'$ and

$$\sum\limits_{v\in S}w(v)=\sum\limits_{v\in S}1=|S|\geq k$$

So, $G'$ has an independent set of weight at least $k$, as needed.

If $G'$ has an Independent set $S'$ such that

$$\sum\limits_{v\in S'}w(v)\geq k$$

Then, observe that $S'$ is an independent set in $G$ also and

$$|S'|=\sum\limits_{v\in S'}1=\sum\limits_{v\in S'}w(v)\geq k$$

So, $G$ has an Independent set of size at least $k$, as needed.