0
$\begingroup$

What I'm trying to do is to show a problem in NP can be reduced to the min weight vertex cover problem

I've chosen the max independent weight problem = input: A graph G with weights on each vertex, output: An independent set with the max total weight

Before reducing, I've tried to show that the max indep. weight problem is in NP (which is usually the first step in these reductions). I'm trying to construct a verification algorithm for this problem; but I'm stuck on trying to show that the verification algorithm can check if a certificate is the max indep. set in polynomial time.

Any guidance or comments would be greatly appreciated. Thanks

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Max weighted independent set is the decision problem whose instances are pairs $(G,B)$ such that $G = (V,E,w)$ is a vertex-weighted graph that has an independent set of weight at least $B$. Nowhere is it claimed that $B$ is the maximum weight of an independent set. The problem (like many others) is defined in this way precisely so that it be in NP.

Also, in order to show that your problem is NP-hard, it might be easier to reduce from max independent set.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks very much for your swift response. The reason I phrased the max indep. problem that way was because the min vertex problem I'm provided is phrased the same way (i.e. input: a graph G with weights on each vertex, output: the vertex cover with the smallest weight). I'll try and use the independent set you described above for my reduction. Thanks again! $\endgroup$
    – Allan
    Commented Mar 7, 2014 at 3:36
  • $\begingroup$ Vertex cover is defined in the same way: the problem is to decide whether there is a vertex cover of weight at most a given weight. You're confusing the decision problem (what I describe) with the optimization problem (what you quote). $\endgroup$
    – Yuval Filmus
    Commented Mar 7, 2014 at 3:42
3
$\begingroup$

The issue is with the version of the problem you are using. Note that as you define it, the output is required to be the maximum weight independent set, i.e. the optimum answer. $NP$ however is a class of decision problems, so the only valid outputs are Yes and No.

So if you want to show the problem is in $NP$ you first need to convert it to a decision problem:

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

It should be easier to see that this version is in $NP$. There is an optimization class - $NPO$ - that corresponds to $NP$, but the normal definition is that a problem is in $NPO$ if its decision variant is in $NP$ - so you're still in the position where you want to deal with the decision variant.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! This cleared up a lot of confusion for me with regards to problems in NP $\endgroup$
    – Allan
    Commented Mar 7, 2014 at 3:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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