Question

In Hitting Set problem we are given a collection E of subsets of V and we want to find smallest subset H of V which intersects (hits) every set in E.

In decision version of the problem, we are asked if there exists a hitting set H of size at most k.

This problem is known to be NP-hard. However, I wonder if the problem is still NP-Hard when are asked if there exists a hitting set whose size is strictly less than n/2, i. e., at most n/2 - 1, (where n is the size of V).

I'm currently working on another problem and I'm convinced that the problem is NP-hard. So I'm trying to find a reduction. I've realized that if the above problem is NP-hard, then I am done.

Any help is appreciated.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top