Is finding the union of all minimum hitting sets NP-hard?

Question

Let's start with the well-known minimum hitting set problem (known to be NP-hard): given some collection of sets: $U = \{S_1, S_2, S_3\} = \{\{1, 2, 5, 9\}, \{1,2,7\}, \{42, 13, 23, 1, 2\}\}$ for example, we wish to find some minimum cardinality set $H$ composed of elements from the union of all elements of $U$ of such that $H \cap S \neq \emptyset, \forall S \in U$. In the above example, it's easy to see that $H = \{1\}$ or $H = \{2\}$.

Now, suppose that instead of returning a minimum hitting set, we wish to return a union of all minimum hitting sets. In the above example, that would be $\{1,2\}$. Note that this is itself a hitting set, but it is no longer a minimum hitting set. Given that finding a minimum hitting set is NP-hard, is finding the union of all minimum hitting sets also NP-hard?

I personally think the answer is yes because in the case where we know there is exactly one minimum hitting set, finding the union of all such sets is equivalent to finding the minimum hitting set (and thus NP-hard). Thus, I think the union problem is at least NP-hard, since a special case of it can clearly be reduced to a known NP-hard problem. However, I'm not sure that this reasoning is sound and so wanted some confirmation.

Any input is much appreciated!

Answer 1

Your logic isn't sound, because it could be that the minimum hitting set (MHS) problem where there is a unique hitting set is much easier. In general you can't assume a problem is hard because it solves a specific subset of a known hard problem, only if it could solve all instances of a known hard problem.

But the answer to your question is still yes, by a proper reduction valid for all instances.

Suppose we could solve the union MHS variant efficiently, we can choose an arbitrary element $x$ of its solution and augment $U \leftarrow U \cup \{\{x, u_1\}, \{x, u_2\}\}$ where $u_1, u_2$ are arbitrary unique values previously not found in $U$. Our augmentation guarantees that all MHS of the augmented $U$ will contain $x$, as the alternative, $\{u_1, u_2\}$, would be less efficient. Also note that $x$ was part of at least one MHS before this augmentation, so any MHS of the augmented collection is also a MHS of the original. Thus by augmenting $U$ we have constrained our problem to just those MHS containing $x$.

We repeat this procedure with different choices of $x$, only modestly increasing the size of $U$, until all our choices of $x$ equals the union MHS. When this happens we have found a MHS of the original collection of sets.

So union MHS is also NP-hard because MHS is, and any efficient algorithm for union MHS would prove MHS easy.