2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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) $\endgroup$
    – Stef
    Dec 6, 2021 at 15:43

1 Answer 1

Reset to default
3
$\begingroup$

This problem is NP-Hard.

Consider a decision problem of this problem: Whether there exists a partition of S, such that |U'| + |U''| = 2|U|? This problem is equal to the problem of 2-DSC, which has been proved to be NP-Complete in paper https://link.springer.com/article/10.1007/s11276-005-6615-6. (Cardei M and Du DZ. "Improving wireless sensor network lifetime through power aware organization." Wireless networks 11.3 (2005): pp333-340.) Thus, this problem is NP-Hard.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Hi! Great answer. Could you please include the name of the paper and the name of the authors explicitly in the answer, so that the paper can still be found even if that link breaks in the future? Cardei M and Du DZ. "Improving wireless sensor network lifetime through power aware organization." Wireless networks 11.3 (2005): pp333-340. $\endgroup$
    – Stef
    Dec 7, 2021 at 10:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.