Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
