Which complexity problem is this related to?

Question

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

S1 = {{1}, {2, 4}}, 
S2 = {{2}, {1, 3}}, 
S3 = {{3}, {2, 4}},
S4 = {{4}, {1, 3}}

The goal is to find the smallest subset of U that contains at least one element from each of the N sets. 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 S3, S4.

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.

Answer 1

Thinking of the hitting set problem is the right idea. This problem (let's call it CONTAINMENT) is NP complete. It is clearly in NP, and

Theorem: $\text{CONTAINMENT}$ is NP-hard.

Proof: We reduce the minimal vertex cover problem$^1$ (known to be NP-hard) to an instance of $\text{CONTAINMENT}$. Given a graph $G$ with vertices $V$ (WLOG assume they are numbered from $1$ to $|V|$) and edges $E$, for each edge $e_i = (u,v) \in E$, we create the set $S_i = \{\{u\}, \{v\}\}$. Since you seem to require that the number of sets $S_i$ is the same as the number of elements in $U$, we can do the following. Set $U = \{1, 2, \cdots, \max(|V|, |E|)\}$. If $n = |E|$, then last $|E| - |V|$ elements will never appear in a set that is an element of any $S_i$ (they are in essence irrelevant to the reduction and are only present to satisfy the demands for the input of your problem). If $n = |V|$, then in addition to the $S_i$ we created above (there are $|E|$ such sets) we can add $|V| - |E|$ extra sets $S_i$ where $S_i = \{ \emptyset \}$ (the set where its only element is the empty set). (The condition for these $S_i$ will be trivially satisfied.) Note that the output of this reduction has size $O(\max(|E|, |V|))$.

Running $\text{CONTAINMENT}$ on this reduction will return a set of vertices corresponding to minimal vertex cover of $G$. A minimal vertex cover must cover at least one of the singleton sets in each of the $S_i$, which is exactly what your problem demands. $\square$

Footnotes:

1. The minimum vertex cover problem asks of a graph $G = (V, E)$ to find $U \subseteq V$, with $|U|$ as minimal as possible, such that every edge in $E$ is incident to a vertex in $U$.