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?