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?
$\begingroup$
$\endgroup$
asked May 11, 2023 at 14:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
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.
