0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – calveeen
    Oct 26, 2023 at 8:53
  • $\begingroup$ 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$). $\endgroup$
    – Steven
    Oct 26, 2023 at 9:05
  • $\begingroup$ Thanks for the clarification. Got it that the reduction does not need to reduce to all instances $\endgroup$
    – calveeen
    Oct 26, 2023 at 9:12

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.