6
$\begingroup$

I have this problem that is very similar to the minimum k-union problem:

Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category. The problem is to select at least one $c$ from each category such that the size of their union is minimized.

Is this problem NP-hard?

| cite | improve this question | | | | |
$\endgroup$
2
$\begingroup$

Nice question! Let us call this problem the minimum label-covering problem.

We will reduce the hitting set problem, a well-known $\mathsf{NP}$-hard problem to the minimum label-covering problem, thus proving it is also $\mathsf{NP}$-hard. Our strategy is simply translating "intersecting the $i$-th set" in the hitting set problem to "labelled with the $i$-th label" in the minimum label-covering problem.

Given $V=\{V_1, V_2,\cdots, V_m\}$, which is a collection of subsets of a finite set $U$ and a number $k$, the hitting set problem is to find the smallest subset of $U$ which intersects (hits) every set in $V$. Let $S$ be the disjoint union of $U$ and $\{l_1,l_2,\cdots, l_m\}$, a set of $m$ labels. Let $C$ be the set of all subsets of $S$ of the form $\{u, l_i\}$ where $u\in V_i$. Let the label for $\{u, l_i\}$ be $l_i$. Suppose we have solved the minimum label-covering problem for $C$, $S$ and the specified labelling, that is, we have selected at least one set from each category such that their union is minimized. Let $U'$ be the set of all elements of $U$ that are members of the selected sets. It is easy to verify that $U'$ is the smallest subset of $U$ that hits every set in $V$. Our proof is done.

An exercise

Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category, the maximum label-covering problem is to select at most one $c$ from each category such that the size of their union is maximized. Show the maximum label-covering problem is $\mathsf{NP}$-hard.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy