# Is this set covering problem NP-Hard?

Consider this variant of set covering problem.

Input: a collection of sets $$S = \{s_1, s_2, \ldots, s_n\}$$ and a universal set $$U$$, in which $$s_k \subseteq U$$ for all $$k$$.

The problem is, divide $$S$$ into two subcollections $$S'$$ and $$S''$$ (i.e. $$S' \cup S'' = S$$, $$S' \cap S'' = \emptyset$$) to maximize $$|U'| + |U''|$$ where $$U'$$ is the union of all sets in $$S'$$, and $$U''$$ is the union of all sets in $$S''$$.

Is the above problem NP-Hard?

• Note that maximizing |U'| + |U''| is equivalent to minimizing |U' ∩ U''|, because |U'| + |U''| - |U' ∩ U''| = |U' ∪ U''| is a constant (equal to the cardinal of the union of all sets in S)
– Stef
Dec 6, 2021 at 15:43