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.