0
$\begingroup$

I'm doing practice problems for an upcoming exam and I'm unsure if the following problem is NP-complete. If it is can you please give me a hint as to what problem I should reduce to it. I believe it's NP-Complete and maybe the knapsack problem can be reduced to it but I'm not sure.

WEIGHTED VERTEX COVER:
Input: A weighted graph $G$ with integer weight $Wv>1$ on each vertex $v$ and an integer $T$.
Question: Does $G$ have a vertex cover with total weight at most $T$?

$\endgroup$

marked as duplicate by D.W., David Richerby, Pål GD, hengxin, Juho Apr 9 '15 at 13:25

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Yes, weighted vertex cover is hard (the minimum cardinality vertex cover, i.e. unweighted vertex cover, is a special case of it). You can reduce independent set to vertex cover. $\endgroup$ – Juho Apr 8 '15 at 19:55
  • $\begingroup$ Well if I reduce independent set to vertex cover, then that will just guarantee I have a vertex cover of size, say K, but that doesn't mean the total weight is at most T $\endgroup$ – Dimitar Stratiev Apr 8 '15 at 20:08
  • $\begingroup$ Even easier, you can reduce unweighted vertex cover to weighted vertex cover. $\endgroup$ – Yuval Filmus Apr 8 '15 at 20:17
  • $\begingroup$ What is unweighted vertex cover? My prof only referred to the problem vertex cover which takes a graph G and an integer K and answers the question: Does G have a vertex cover of size K? Maybe I'm understanding reduction wrong,but from what I've seen in examples, If the problem you are reducing has a solution then that solution could be easily transformed/interpreted as a solution to your other problem without additional computations. $\endgroup$ – Dimitar Stratiev Apr 8 '15 at 20:28
  • $\begingroup$ It is the casw that "Wv" is intended to stand for $W_v$. If yes, maybe you should use LaTeX. $\endgroup$ – babou Apr 8 '15 at 20:57
2
$\begingroup$

Expanding on Pål GD's hint, you can reduced from the normal, unweighted version of VERTEX COVER.

VERTEX COVER
Input: A graph $G$ and an integer $k$.
Question: Does $G$ have a vertex cover of size at most $k$?

So in this case, you're just counting the number of vertices in the cover. Now to transform this to the weighted version, we just need to add weights to all the vertices such that we can recover the size of the vertex cover from the weight of the vertex cover.

Bigger hint under the spoiler tag, don't mouse over unless you're really stuck.

What happens if we assign each vertex the same weight (doesn't really matter what it is, as long as they're all the same)? If each vertex has weight $c>1$, what's the weight of a vertex cover of size $k$? What's the size of a vertex cover of weight $T$?

$\endgroup$

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