Hitting set problem variant - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T02:10:42Z http://mathoverflow.net/feeds/question/76235 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76235/hitting-set-problem-variant Hitting set problem variant Postamar 2011-09-23T20:46:18Z 2011-09-24T19:05:52Z <p>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\}$$ ? </p> <p>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\}$.</p> <p>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.</p> <p>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:</p> <ul> <li>any one set $E_j$ is not included in any other $E_k$;</li> <li>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}$.</li> </ul> http://mathoverflow.net/questions/76235/hitting-set-problem-variant/76267#76267 Answer by Brendan McKay for Hitting set problem variant Brendan McKay 2011-09-24T11:27:44Z 2011-09-24T11:27:44Z <p>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$.</p> http://mathoverflow.net/questions/76235/hitting-set-problem-variant/76281#76281 Answer by Max Alekseyev for Hitting set problem variant Max Alekseyev 2011-09-24T18:59:55Z 2011-09-24T19:05:52Z <p>Let $\mathcal{E} = \bigcup_{k=1}^m E_k.$</p> <p>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\}$)</p> <p>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.</p> <p>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.</p>