<p>The answer is yes - the problem is still NP-Complete. for every set $S_i$ create a fake elements $e_i&#39;, e_i&#39;&#39;$ and create a new sets $S_i&#39; = S_i \cup \{ e_i&#39;\}$ and $S_i&#39;&#39; = S_i \cup \{e_i&#39;&#39;\}$. 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.</p>

<p>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. </p>

<p>Without any further restrictions the problem looks as hard as the original problem.</p>

<p>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&#39;$ or $e_i&#39;&#39;$, 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.</p>

CC BY-SA 3.0
2011-04-15T14:18:44.367Z
Thanks for your nice proof. I thought the restriction might make the problem easy, and I was wrong.
Yota Otachi
CC BY-SA 3.0
2011-04-15T04:11:06.590Z
2011-04-15T04:28:58.570Z
2011-04-15T04:28:58.570Z
Sariel Har-Peled
<p>A <em>hitting set</em> 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:</p>

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

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

<cc.complexity-theory><np-hardness><approximation-hardness>
Hitting set of pairwise intersecting families
Yota Otachi
# Hitting set of pairwise intersecting families

(Asked by: username_0 on 2011-04-15)

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.

**Tags:** cc.complexity-theory, np-hardness, approximation-hardness

---

## 1 answers

### Answer by username_1 on 2011-04-15. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks for your nice proof. I thought the restriction might make the problem easy, and I was wrong.  

---

