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.

  • 2
    $\begingroup$ Possible duplicate of Reduce Vertex Cover with size k to Vertex Cover with size n/2 $\endgroup$
    – xskxzr
    Sep 25 '19 at 2:53
  • $\begingroup$ @xskxzr While the technique to get a reduction there is similar to what can be done here, I don't think it is a duplicate. In particular, the other question is only about a specific part of a particular reduction, while this question is about finding the entire reduction, including what problem to reduce from. $\endgroup$
    – Discrete lizard
    Sep 25 '19 at 6:37
  • $\begingroup$ If k<n/2, it seems k-hitting set can be reduced to n/2-hitting set, by adding new elements to V, where each element is added as a singleton set to E. Similarly if k>n/2, we can add a new element to V and add it as a new set of size >2 to E with all elements new. $\endgroup$ Sep 25 '19 at 6:55

I think the easiest way is to reduce

$ VC_{n/2}=\{G∣G=(V,E) $ has a vertex cover of size $|V(G)|/2\}.$ ( https://cs.stackexchange.com/a/90487/72705)


$ HS_{n/2}=\{(S,F)∣\exists H\subseteq S: $$H$ is a HS of $F$ of size at most $|S|/2 $$\}$.

In https://cs.stackexchange.com/a/90487/72705 , they show that $VC_{n/2}$ is $NP$-hard.

Now, we reduce $VC_{n/2}$ to $HS_{n/2}$, which is the standard reduction from normal $VC$ to $HS$:

  • $S = V$
  • $F = E$, where $E:= \{e_1,e_2,\ldots,e_m\}$ with $e_i = \{v_j, v_k\}$ and $v_j, v_k \in V$

Clearly, this reduction can be done in poly. time and is correct, as one element in $F$ corresponds to one edge in $E$, so the HS can be mapped one to one to the vertex cover set and vice versa.

As you can see, the vertex cover set has the same number of elements as the corresponding hitting set (if there exists one). Also, $|S| = |V|$. Therefore, the Vertex Cover Set of size $|V|/2$ gives a HS of size $|S|/2$. To get a HS of size $(|S|/2) -1$, one could add two completely new elements $\alpha, \beta$ to $S$ (let this be $S'$) without changing $F$. Therefore, $\alpha$ and $\beta$ will never be in the HS of $F$, but the Hitting Set now has a size of $|S|/2 = (|S'| -2) / 2 = (|S'|/2) -1$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.