Finding the smallest set with non-empty intercept with of a collection of sets

417 Views Asked by At

I have some sets $\mathcal S_1$, $\mathcal S_2$, $\dots$, $\mathcal S_n$. I am looking for a tractable algorithm that finds the lowest cardinality non-empty subset(s) of the union $$A\subseteq\bigcup\limits_{i=1}^n \mathcal S_i$$

such that $A\cap \mathcal S_i \neq \emptyset$ $\forall$ $\mathcal S_i$. For example, if $x\in \mathcal S_i$ $\forall$ $i$, then the set $A = \{ x \}$ satisfies the criteria, and the solution is 1. For example, for $\mathcal S_1= \{a, b, c\}$, $\mathcal S_2 = \{c, d\}$ and $\mathcal S_3 = \{d, e\}$, $A = \{c, d\}$ and so the answer is $2$. In general there will be multiple $A$ satisfying $A\cap \mathcal S_i \neq \emptyset$ $\forall$ $\mathcal S_i$. Im interested in calculating the smallest $A$, and if possible finding all $A$ with this cardinality.

1

There are 1 best solutions below

0
On BEST ANSWER

By defining for each $x$ the set $T_x = \{i \in [n] : x \in \mathcal S_i\}$, we can turn this problem into a set cover problem: the problem of covering $[n] = \{1,2,\dots,n\}$ by the smallest collection of sets $T_x$.

For example, for $\mathcal S_1= \{a, b, c\}$, $\mathcal S_2 = \{c, d\}$ and $\mathcal S_3 = \{d, e\}$, we can define $T_a = \{1\}$, $T_b = \{1\}$, $T_c = \{1,2\}$, and $T_d = \{2,3\}$, and we are looking for the minimum set cover of $\{1,2,3\}$ by a subset of $T_a, T_b, T_c, T_d$.

Similarly, given an instance of the set cover problem - a collection of sets $T_1, T_2, \dots, T_m$ with union $U$, for which we want to find a smallest subcollection that still covers $U$ - we can define $\mathcal S_i = \{j \in [m] : i \in T_j\}$. Now finding a smallest set $A$ such that every $S_i$ contains an element of $A$ is equivalent to the set cover problem, since the collection $\{T_a : a \in A\}$ is the set cover we wanted.

Since the set cover problem is NP-complete, if I could tell you an efficient algorithm for it, I would be claiming my million dollars and not revealing the method in an MSE answer.