# Is it NP-hard to decide the existence of n subsets picked from n lists of subsets the union of which contains at most s elements?

You are given $$n$$ lists. The $$i$$-th list contains $$k_i$$ subsets of $$\{1, \ldots, m\}$$. You are also given an integer $$s$$. You should decide whether it's possible to pick up exactly one element (that is subset of $$\{1, \ldots, m\}$$) from each list, such that the cardinality of a union of all picked subsets is at most $$s$$. Is this decision problem NP-hard?

Call the decision problem in the question the bounded-union problem.

Yes, the bounded-union problem is NP-hard. The following is a proof.

Consider (the decision version of) the hitting set problem, "Given $$S=\{1,2,\cdots, m\}$$, a list of $$n$$ subsets of $$S$$ $$S_1, \cdots, S_n$$ and an integer $$s$$, decide whether there is a hitting set of at most $$s$$ elements, where a hitting set means a subset of $$S$$ that has a nonempty intersection with each given subset."

Given an instance $$h$$ of the hitting set problem as described above, we can construct an instance of the bound-union problem where each subset is a singleton. Specifically, if $$S_i=\{a_1, \cdots, a_{k_i}\}$$, we construct the $$i$$-th list as the list of singleton sets $$\{a_1\},\cdots, \{a_{k_i}\}$$. We also have integer $$s$$. So we have an instance $$b$$ of the bounded-union problem.

If for $$h$$ there is a hitting subset $$T$$ of $$S$$ with at most $$s$$ elements, then for $$b$$ we can pick up $$\{a_{\beta_i}\}$$ from the $$i$$-th list, where $$a_{\beta_i}$$ is any number in in $$T\cap S_i$$. The cardinality of the union of all picked singleton sets is at most $$s$$.

If for $$b$$ we can pick up singleton set $$\{a_{\beta_i}\}$$ from the $$i$$-th list such that the cardinality of the union of all such elements is $$s$$, for $$h$$ the subset $$\{a_{\beta_i}\mid 1\le i\le n\}$$ is a hitting set of size $$s$$.

Hence we have constructed a reduction from the hitting set problem to the bound-union problem. Since the reduction is polynomial-time, and the hitting set problem is NP-hard, so is the bounded-union problem.

Suppose we have an undirected graph $$(V, E)$$ and we want to know whether or not it has a vertex cover with at most $$s$$ vertices.

Let $$m = |V|$$ and $$n = |E|$$, and for each edge $$e_i = \{u, v\} \in E$$ let the $$i$$th list be $$\{\{u\}, \{v\}\}$$. Then there is a vertex cover of size at most $$s$$ if and only if there is a choice of one (singleton) set from each list such that the union of those (singleton) sets has size at most $$s$$ ─ because these unions are exactly the vertex covers of the original graph.