I am confronted with task to find polynomial time complexity solution for weight

Question

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.