# Can weighted problem have polynomial complexity if non-weighted problem is NP-complete: hitting set

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?

• 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 – Nikos M. Jun 5 '14 at 19:21
• 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. – user18195 Jun 5 '14 at 20:35
• 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) – Nikos M. Jun 5 '14 at 20:38
• i totally agree the question is not trivial – Nikos M. Jun 5 '14 at 20:39