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

Improve this question
$\endgroup$
6
  • $\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
    Commented Apr 8, 2015 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
    Commented Apr 8, 2015 at 20:08
  • $\begingroup$ Even easier, you can reduce unweighted vertex cover to weighted vertex cover. $\endgroup$
    – Yuval Filmus
    Commented Apr 8, 2015 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
    Commented Apr 8, 2015 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
    Commented Apr 8, 2015 at 20:57

1 Answer 1

Reset to default
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$?

Improve this answer
$\endgroup$

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