# Is Weighted Vertex Cover NP-Complete? [duplicate]

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

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

• 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. – Juho Apr 8 '15 at 19:55
• 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 – Dimitar Stratiev Apr 8 '15 at 20:08
• Even easier, you can reduce unweighted vertex cover to weighted vertex cover. – Yuval Filmus Apr 8 '15 at 20:17
• 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. – Dimitar Stratiev Apr 8 '15 at 20:28
• It is the casw that "Wv" is intended to stand for $W_v$. If yes, maybe you should use LaTeX. – babou Apr 8 '15 at 20:57

Input: A graph $G$ and an integer $k$.
Question: Does $G$ have a vertex cover of size at most $k$?
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$?