Is finding the smallest collection of subsets so that the number of elements among the subsets is <= the number of subsets NP-hard?

Question

Given a collection of non-empty subsets of $\{1,2,\ldots,N\}$ ($N$ not fixed), the problem is to find the smallest non-empty collection of subsets so that the number of distinct elements appearing among the union of subsets is less than or equal to the number of subsets chosen. This seems like an NP-hard problem but I can't prove it. Any help?

Answer 1

This is too long for a comment but is not really a full answer.

Let's re-formulate the problem setting slightly as a bipartite graph $G$, with $\{1,2,\ldots,N\} = X$ as one set of vertices and the collection of subsets (say, $Y$) as the other set of vertices, with an edge between $i \in X$ and $J \in Y$ iff $i \in J$. For any set of vertices $W$ in $Y$, define $N(W)$ to be the neighborhood of $W$ in $G$ -- namely, the set of all vertices in $X$ that are adjacent to at least one vertex in $W$.

Then, the problem asks to find a minimal subset $W \subseteq Y$ such that $|N(W)| \leq |W|$. However, if we change the criterion slightly to $|N(W)| \lt |W|$, we find that such a subset exists if and only if there does not exist a matching between $X$ and $Y$ that covers $Y$, for it is exactly equivalent to Hall's Marriage Theorem.

Since such matchings are findable in polynomial time (e.g.: via Hopcroft-Karp), I think this version of the problem should probably be relatively easy but I'd have to do some more work to figure out if and how the standard algorithms for bipartite matching expose these deficient sets and whether or not minimal deficient sets can also be obtained easily. Furthermore, I can't tell right away how much harder the original version of the problem (which allows $|N(W)| = |W|$) is than this modified version.

Answer 2

You can reduce from Clique. Create a set for each vertex, each with n-1 elements corresponding to the n-1 other vertices, with the element for v in set u being equal to the element for u in set v (but not equal to any other element) if {u, v} is an edge, and a unique element otherwise. Then we can choose k strings that together contain k(n-k) + k(k-1)/2 elements if an only if there is a clique of size k. We then only need to add the correct number of one-element sets containing the same element such that the number of sets selected and elements collected is the same.