Consider the unweighted and weighted versions of the vertex cover problem (UVC and WVC for short, respectively). As UVC is a special case of WVC, is it true that $$\text{UVC} \leq_\mathrm{m} \text{WVC}$$ but $$\text{UVC} \not \equiv_\mathrm{m} \text{WVC} \enspace ?$$

I think the first part is easy to prove, since one can construct an instance of WVC by taking an instance of UVC and letting the weight of all of its vertices be the same.

I find not that easy to prove the second part though. As WVC is a generalization of UVC, intuitively $\text{WVC} \leq_\mathrm{m} \text{UVC}$ can't hold, but I'd appreciate some help to demonstrate it in a formal way.

  • $\begingroup$ If weights are encoded in unary then the problems might be p-equivalent. $\endgroup$ – Yuval Filmus Mar 29 '16 at 15:23
  • $\begingroup$ How would unary coding help the problems be p-equivalent? $\endgroup$ – Cromack Mar 29 '16 at 17:30
  • $\begingroup$ You will be able to duplicate vertices. $\endgroup$ – Yuval Filmus Mar 29 '16 at 17:31
  • $\begingroup$ @YuvalFilmus For example, consider the complete graph $\mathrm{K}_4$, where the weight function is defined as $w(v_i) = i$, with $i$ encoded by using unary coding, i.e., $w(v_1) = 10$, $w(v_2) = 110$, $w(v_3) = 1110$ and $w(v_4) = 11110$. Now, how does this reduce to an undirected graph? Thank you very much for your help. $\endgroup$ – Cromack Mar 29 '16 at 19:42
  • $\begingroup$ You duplicate vertex $v_i$, $w(v_i)$ times. I believe that if you connect the edges in the correct way, you get an equivalent problem. $\endgroup$ – Yuval Filmus Mar 29 '16 at 20:56

If you're talking about determining whether there exists a cover of weight $\le T$, then the problem is obviously in NP and thus reduces to unweighted vc (since $VC$ is NP complete).

If however were talking about whether the minimal cover is of weight $\le T$, then the problem is $\Sigma_2$ complete, and is therefore not reducible to vc unless the hierarchy collapses to the first level.

| cite | improve this answer | |
  • $\begingroup$ I'm talking about the optimization problem: finding the minimum number of vertices that make the graph disjoint (in the unweighted case) and finding the minimum weight vertex cover (in the weighted case). So, I suppose the problem is $\Sigma_2$ complete, but I'm afraid I don't know what you mean with "unless the hierarchy collapses to the second level". Thank you! $\endgroup$ – Cromack Mar 29 '16 at 11:20
  • $\begingroup$ If the decision problem is not in $\mathsf{NP}$, then so is the optimization problem (In addition, for natural $T$ we can reduce the optimization problem to the decision problem using binary search), so we can restrict our conversation to the decision version I mentioned. Explanations on the polynomial hierarchy can easily be found on the web, for a more complete review i would suggest Computational Complexity by Arora and Barak (chapter 5). $\endgroup$ – Ariel Mar 29 '16 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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