2
$\begingroup$

Let's start from finding a minimum hitting set problem. Given a collection of sets $U=\{S_1,S_2,S_3,S_4,S_5,S_6\}=\{\{1, 2, 3\}, \{1, 3, 4\}, \{1, 4, 5\}, \{1, 2, 5\}, \{2, 3\}, \{4, 5\}\}$,
it is easy to know that a minimum hitting set is $\{2,4\}$.

I am thinking what this "hitting set" problem would be if the set $S$ is also a collection of sets.
For instance, given
$S_1=\{\{1,2,3\},\{3,4\},\{1,2\}\}$,
$S_2=\{\{3\},\{3,5\},\{1,3\}\}$,
$S_3=\{\{2,5\},\{4\},\{1,5\},\{1,10,6,7\}\}$,
and in this new problem, the "hitting set $H$" should be a set that:
1. For each $S_i$, there must exist an element $s$ which is a subset of $H$;
2. The cardinality of $H$ is as small as possible.

Therefore, we can see that $\{3,4\}$ is a solution.

It looks like I am trying to select an element from each set where each is a collection of sets, and then the cardinality of the union of these selected elements is as small as possible.

Does anyone have an idea to solve this problem? Do you think it is a variant of hitting set problem? Is it an NP-hard problem?

$\endgroup$
  • $\begingroup$ Can you share the context where you encountered this problem? It would also help to provide a general specification of the problem, a definition of what counts as a "hitting set" in this context. An example is not a substitute for a problem specification. $\endgroup$ – D.W. Apr 26 at 1:09
  • $\begingroup$ @D.W. Thanks for your reply. I edited my question to make it more clear. Btw, it looks like I am trying to find a minimum union set $H$ across a collection of sets where each set is also a collection of sets. $\endgroup$ – tryR Apr 26 at 10:37
1
$\begingroup$

The special case of your variant where every set $S_i$ contains only single-element sets are exactly the standard hitting set problem, so this variant is at least harder than the standard hitting set problem, thus is NP-hard.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer. $\endgroup$ – tryR Apr 26 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.