Given many sets, what algorithm finds the minimum set(s) of members present in all those sets?
For example, given these sets:
{1,2} {1,2,44} {2,5,6} {5,6} The minimum set(s) of members are:
{1,5} {1,6} {2,5} {2,6} The problem is similar to Set Cover, except I want to cover the sets and not the elements.
Let $\mathcal{U} = \{e_1,\dots,e_n\}$ be the universe and $\mathcal{S} = \{S_1,\dots, S_m\}$ be the collection of sets such that $\mathcal{U} := \bigcup_{j=1}^m S_j$.
Getting one minimum cover set:
Take a collection of singleton sets $s_1,\dots,s_n$ where $s_i = \{e_i\}~\forall i=1,\dots,n$. We need to take the minimum of these singleton sets to cover $\mathcal{S}$. Now consider any solution strategy for the classical set-cover problem (note that it is NP-hard as well as APX-hard). Here, we just need to patch the element covering condition to meet our needs. Note that, when we take $s_i$ into our solution, then all $S_j$ containing $e_i$ is covered. This will give us one of the minimum sized covers.
Getting all minimum cover sets:
We make two key observations here. First, all minimum size covers are of the same cardinality, say $k$. Second, any such cover would, of course, be a subset of $\mathcal{U}$. Thus, there can be at most $n\choose k$ solutions. We can certainly evaluate all of them. We may not need to bother with optimizing this step (which can very well be exponential in $n$) since comutational time for finding one solution (which is NP-hard) would anyway dominate this step.
