1
$\begingroup$

I am confronted with task to find polynomial time complexity solution for weighted hitting set problem. I have found that usual hitting set problem is NP-complete and therefore the task seems to be contradictory.

But there are several other reformulations of this problem. E.g. d-Hitting set problem can be solved in polynomial time (when each class or set contains no more than d elements).

Maybe the weighted case has completely different algorithms and complexity estimation? Apparently the non-weighted problem is the special case of weighted one and therefore there should not be different complexity estimation, isn't so?

$\endgroup$
  • $\begingroup$ it seems this requires a proof that weighted hitting set problem in NP-hard or reducable to some NP-complete problem. If there is such a proof, it is indeed NP-complete, if there is not such a proof it might be np-complete unless a polynomial algorithm is found to solve it $\endgroup$ – Nikos M. Jun 5 '14 at 19:21
  • $\begingroup$ Here is one proof lca.ceid.upatras.gr/courses/sttcc/projects2013/… of NP-completeness and there are several others on the net, mostly using reduction to set cover problam. My question is not trivial, at least intuitively. If elements have weights then this can greatly reduce the search space - one should check only elements with the least weight. From the other hand - weighted problem is still the special case. $\endgroup$ – user18195 Jun 5 '14 at 20:35
  • $\begingroup$ i meant a proof that weighted hitting set is np-complete or not, not the hitting set, sine this is already mentioned in th question. Just pointed out that the question in effect requires such a proof (for weighted hitting set problem) $\endgroup$ – Nikos M. Jun 5 '14 at 20:38
  • $\begingroup$ i totally agree the question is not trivial $\endgroup$ – Nikos M. Jun 5 '14 at 20:39
3
$\begingroup$

The unweighted case is a special case of the weighted case, corresponding to all weights being equal. Therefore the unweighted case is easier or as hard as the weighted case. The reason is that given an algorithm for the weighted case, you can use it to solve an unweighted problem by endowing the relevant objects with unit weight.

| cite | improve this answer | |
$\endgroup$

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.