0
$\begingroup$

$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$?

$\endgroup$
  • $\begingroup$ What do you mean by "$X\iff Y$"? WHat are $X$ and $Y$? $\endgroup$ – David Richerby Jun 10 '18 at 12:32
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.