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?


2 Answers 2


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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