[Solved]: Proving that Max Weighted Independent Set is in NP

Problem Detail: 

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

Asked By : Allan

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22360