A hitting set of a family $\mathcal{S} = \{S_1, \dots, S_n\}$ is a subset $H$ of $\bigcup_{i=1}^{n} S_i$ such that $H \cap S_i \ne \emptyset$ for $1 \le i \le n$. The problem to find a minimum hitting set of a given family is NP-hard in general, since it generalizes the vertex cover problem. Now my question is:

Does the hitting set problem remain NP-hard when the elements of $\mathcal{S}$ pairwise intersect?

I am also interested in the approximation hardness (or tractability) of this problem.

up vote 11 down vote accepted

The answer is yes - the problem is still NP-Complete. for every set $S_i$ create a fake elements $e_i', e_i''$ and create a new sets $S_i' = S_i \cup \{ e_i'\}$ and $S_i'' = S_i \cup \{e_i''\}$. It is easy to verify that any hitting set of the old system is a hitting set of the new system. Furthermore, except for the fake elements, every element now hit at least three sets.

Next, for every pair of sets in the new system (lets call them $T_i$ and $T_j$ to avoid confusion), create a fake element $x_{ij}$ and add it to both $T_i$ and $T_j$. Clearly, in the resulting set system all sets pairwise intersect, but the original optimal hitting set is still the optimal hitting set for this newest system.

Without any further restrictions the problem looks as hard as the original problem.

BTW, proving that indeed the optimal solution would not use any of the fake elements is not trivial. First, we can assume that a given hitting set for the new system does not include any $e_i'$ or $e_i''$, since otherwise we can move the elements to the original elements of the sets, and get a hitting set of similar size. It is slightly more subtle to see why the elements $x_{ij}$ are not in the optimal hitting set. Since it is tedious I would just leave a hint: build a graph connecting two sets $S_i$ and $S_j$ in the original system if $x_{ij}$ connects two sets that are derived from these sets. Argue that this graph in the minimal hitting set must be $3$ regular, and as such the number of edges in it strictly exceeds the number of sets present as vertices. As such, one can find a smaller hitting set for these sets.

  • Thanks for your nice proof. I thought the restriction might make the problem easy, and I was wrong. – Yota Otachi Apr 15 '11 at 14:18

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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