1
$\begingroup$

Define a universe $U$ containing $N$ elements. We are given $N$ sets, each of which is a set.

For example, $U = \{1, 2, 3, 4\}$ and sets \begin{align} S_1 &= \{\{1\}, \{2, 4\}\}, \\ S_2 &= \{\{2\}, \{1, 3\}\}, \\ S_3 &= \{\{3\}, \{2, 4\}\}, \\ S_4 &= \{\{4\}, \{1, 3\}\} \end{align}

The goal is to find the smallest subset of $U$ that contains at least one element of each of the $S_i$'s. So for example, the subset $\{1,3\}$ is a correct answer, while the subset $\{1,2\}$ is not, because it does not contain any set in $S_3, S_4$.

I tried to formulate the above as an instance of the hitting set problem (because it seemed closer to it in spirit), but failed to do so. One way I managed to cleanly reduce the problem is by expanding each set to include all supersets. Then the desired answer is the smallest sized set in the intersection of the expanded sets. But this approach is undesirable as the expanded set size grows exponentially.

Any thoughts on connections to a known complexity problem are much appreciated.

$\endgroup$
4
  • $\begingroup$ $\{1, 3\}$ also does not 'contain' one element of either $S_2$ or $S_4$. You need to be much more precise with your statements when you have sets nested inside sets. It is likely you meant $S_k$ contains a (non-strict) subset of $x$, where $x \subseteq U$ and trying to optimize $|x|$. $\endgroup$
    – orlp
    Oct 30 '20 at 4:08
  • $\begingroup$ That's a great exercise! If we solved it for you, that would take away the opportunity to learn from the experience of finding the solution on your own. I suggest you review cs.stackexchange.com/q/1240/755 and cs.stackexchange.com/q/11209/755, then edit the question to tell us which reduction partners you have already considered. It might help to consult a list of problems that you have already been taught are NP-complete. $\endgroup$
    – D.W.
    Oct 30 '20 at 4:09
  • $\begingroup$ Cross-posted: math.stackexchange.com/q/3886976/14578, cs.stackexchange.com/q/131724/755. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Oct 30 '20 at 4:11
  • 1
    $\begingroup$ I’m voting to close this question because it was already solved on math.se. $\endgroup$ Oct 30 '20 at 8:30