# Select at least one from each category to minimize union, NP-hard problem?

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?

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.