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?
Can weighted problem have polynomial complexity if non-weighted problem is NP-complete: hitting set
complexity theory;time complexity;np complete;optimization