# Minimizing the number of distinct elements by picking one set from each set of sets

I have a problem as follows. Given a set of sets $$U = \{S_1, S_2, … S_N\}$$ where $$S_i = \{s_1, s_2, ... s_m\}$$. Each $$s_j \in S_i$$ contains a set of distinct elements. I need to pick one $$s_j \in S_i$$ to form $$N$$ sets in total such that $$|\bigcup_{j=1}^N s_j|$$ is minimized.

Is there an efficient algorithm to solve this problem. I feel that this problem is $$NP-hard$$ as it is somewhat similar to the maximum coverage problem. I have yet to be able to formally prove this intuition by reduction from the maximum coverage problem.

Your problem is NP-hard by a reduction from the (decision version of the) hitting set problem. Given a set $$X = \{x_1, \dots, x_n\}$$ of elements, a collection $$A_1, A_2, \dots, A_h$$ of subsets of $$X$$, and an integer $$k$$, is there a subset $$X'$$ of at most $$k$$ elements from $$X$$ such that $$A' \cap A_i \neq \emptyset$$ for all $$i=1, \dots, h$$?
To reduce an instance of hitting set to an instance of your problem you can choose $$N=h$$ and $$S_i = \{ \{ a \} \mid a \in A_i \}$$.
If there is a hitting set $$A'$$ of size at most $$k$$, then each set $$S_i$$ contains at least one set $$\{a\}$$ for some $$a \in A'$$. Choosing one such set per $$S_i$$ yields a solution to your problem of size at most $$k$$.
If there is a solution to your problem of size at most $$k$$, then the union of the selected sets contains at least one element in each $$A_i$$ (since the sets in $$S_i$$ contain only elements in $$A_i$$), i.e., it is a hitting set.
• Thank you for the explanation. What if $S_i$ contained sets with more than one element each ? the hitting set problem never reduces to such instances. Commented Oct 26, 2023 at 8:53
• I'm not sure I understand your comment. If instances in which each set in $S_i$ can have a single element are valid for your problem then the reduction is valid. A reduction $f$ from $A$ to $B$ does not need to generate all instances of $B$ (think of it this way: if you have an algorithm for $B$ you can use it to solve all instances $x\in A$ by solving $f(x)\in B$). If such instances are not valid for your problem then you can modify the above reduction by adding a common new element $x$ to all sets (the size of all sets becomes $2$ and the size of the solution increases by $1$). Commented Oct 26, 2023 at 9:05