Hitting set problem variant

Question

Given any collection $\mathcal{C} = \{E_1, E_2, ..., E_m\}$ of finite and nonempty discrete sets, is there a set $I$ such that $$ \forall E_k \in \mathcal{C}, \; E_k \cap I \neq \emptyset,$$ and $$ \forall i \in I, \; \exists E_k \in \mathcal{C}, E_{k} \cap I = \{i\} $$ ?

For example, for $E_1 = \{1,2\}$, $E_2 = \{2,3\}$ and $E_3 = \{1,3\}$ with $m = 3$, a possible $I$ is $\{1,2\}$.

I've been trying to answer this question ever since stumbling upon it in my research, under a different form. I'm hardly a real mathematician so I submitted this problem to some nearby theoretical computer scientists hoping they'd tell me it was trivial, but no such luck.

All I've found until now are a few of rather trivial observations. To begin with, the second property to be verified by $I$ is equivalent to there being an injection $g$ from $I$ to $\{1, ..., m\}$ such that $E_{g(i)} \cap I = \{i\}$ for all $i \in I$. Also, the problem can be formulated as a graph problem using a bipartite graph with $m$ vertices on one side representing the sets in the collection and vertices on the other side for each element in the union set $\bigcup_{i=1}^m E_k$, but graph theory isn't my forte either. Finally, notice that we only really need to consider the collections where $E_1, ..., E_m$ also verify the following properties:

• any one set $E_j$ is not included in any other $E_k$;
• there exists no element $e$ in exactly one set $E_k$, in other words $e$ is either in none or in at least two sets of $\mathcal{C}$.

Answer 1

Let $I$ be a minimal set that intersects each $E_j$, where minimal means that no point can be removed from $I$ without it no longer intersecting each $E_j$. Take any $i\in I$. We know $i$ lies in some $E_j$, otherwise $I$ was not minimal. If every $E_j$ that contains $i$ also contains another element of $I$, then we can remove $i$ from $I$ and it still intersects each $E_j$, so again $I$ would not be minimal. So some $E_j$ that includes $i$ contains no other element of $I$.

Answer 2

Let $\mathcal{E} = \bigcup_{k=1}^m E_k.$

For each $j\in\mathcal{E}$, let $A_j = \{ k\in [1,m] : j\in E_k \}$. Then the anticipated subset $I\subset\mathcal{E}$ should satisfy the following requirements: $$\bigcup_{i\in I} A_i = \{ 1, 2, \dots, m \}$$ and $$\forall i\in I\quad A_i\not\subset \bigcup_{j\in I\atop j\ne i} A_j.$$ (the latter means that there exists $k\in A_i$ such that $k\not\in A_j$ for all $j\in I\setminus\{i\}$, that is, $E_k\cap I=\{i\}$)

That is, the collection $\{ A_i : i\in I\}$ forms a minimal cover of the set $\{ 1, 2, \dots, m\}$. Such cover always exists -- one can start with the collection $\{ A_j : j\in\mathcal{E} \}$ and iteratively remove $A_i$ that is a subset of the union of the remaining sets until no such sets left.

In the example with $E_1=\{1,2\}$, $E_2=\{2,3\}$ and $E_3=\{1,3\}$ we have $A_1 = \{1,3\}$, $A_2 = \{ 1,2\}$, $A_3=\{2,3\}$. Clearly, removing any set from the collection $\{ A_1, A_2, A_3 \}$ leaves us with a solution.