1
$\begingroup$

I would like to know whether the following problem is a standard problem that has been considered in the research literature. I performed some searches, which have not produced results. I call this problem the Maximum Weighted Disjoint Set Union, which is obviously not the name by which the problem is known (if it is known).

In this post, the problem (stated slightly differently) is related to Weighted Independent Set. However, I will show below that this problem is simpler than independent set and, even if it possesses the same time complexity, it may allow for a solution with smaller run-time requirements.

The problem is as follows. We are given a set $U$ of elements (the universe, e.g., $U=\{1,2,3,4,5\}$). We're also given a set $S=\{S_1,S_2,\ldots,S_n\}$, where $\forall_iS_i\subseteq U$. Furthermore, each set $S_i$ is assigned a weight $w_i$. The task is to find a set $S'\subseteq S$, such that the sets in $S'$ are disjoint and the sum of their weights is maximal.

One might think that this problem corresponds to weighted independent set. Namely, the vertices in the graph correspond to the sets in $S$ and there is an edge between two vertices if the corresponding sets have non-empty intersection.

Note, however, that important information is lost in the process of translation. For an example of such a loss, suppose $S_1=\{1,2\}$ with $w_1=1$, $S_2=\{3,4\}$ with $w_2=1$, $S_3=\{1,2,3\}$ with $w_3=3$. Note that we do not need to consider a cover $S'$ that contains both $S_1$ and $S_2$. This is because $S_3\subseteq S_1\cup S_2$ and $w_3>w_1+w_2$. The information needed to perform this cut-off is not present in the corresponding instance of the weighted independent set problem.

If I am correct in this reasoning, then this problem deserves attention and I am wondering whether it received any. In addition, I am hoping to get an off-the-shelf implementation in C++ which I can use (this problem happens to be a sub-problem of the research problem in a different field that I am trying to solve).

Improve this question
$\endgroup$
5
  • $\begingroup$ This is a weighted version of Exact Cover. (Unweighted Exact Cover is already NP-complete, so this is too.) Also, in your example, you do need to consider a cover $S'$ that contains both $S_1$ and $S_2$, since $S_1 \cup S_2$ includes the element $4$ while $S_3$ does not -- and since your stated requirements include "their union is $U$", element $4$ must be covered by something, but with $S_3$ included that is impossible. To eliminate a set from contention, you need a stronger condition: it needs to be equal to (not just a subset of) the union of other sets whose weights sum to less. $\endgroup$
    – j_random_hacker
    Jan 16, 2018 at 16:30
  • $\begingroup$ @j_random_hacker You are right. I missed this, because in my original problem, $S$ contains all the singleton sets, e.g. $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$ and $\{5\}$ in the example. So there I have the cut-off condition as described. I updated the problem to be exactly as in the quoted post, i.e. to not require the union to be the entire universe. $\endgroup$
    – AlwaysLearning
    Jan 16, 2018 at 18:02
  • $\begingroup$ OK, in that case this is a weighted version of Set Packing (also NP-hard I'm afraid). $\endgroup$
    – j_random_hacker
    Jan 16, 2018 at 18:49
  • $\begingroup$ @j_random_hacker Correct! Interestingly, when I looked for an implementation, people suggest using independent set, which totally misses on the opportunities for cut-offs. In any case, your last comment should be a reply. If you can cite a paper (the Wikipedia article says that a citation is required), that would be awesome. $\endgroup$
    – AlwaysLearning
    Jan 16, 2018 at 19:28
  • $\begingroup$ I don't understand why "The information needed to perform this cut-off is not present in the corresponding instance of the weighted independent set problem.". In that corresponding instance, any neighbour of the vertex $S_3$ is either a neighbour of the vertex $S_1$ or a neighbour of the vertex $S_2$ and $w(S_1)+w(S_2) < w(S_3)$ so any independent set $I$ containing both the vertex $S_1$ and $S_2$ can be replaced by $I \cup \{S_3\} - \{S_1, S_2\}$ which is still an independent set with a greater total weight. Exact same argument applies. Am I missing something ? [edit: same as j_random_hacker] $\endgroup$
    – Caninonos
    Jan 16, 2018 at 20:31

1 Answer 1

Reset to default
2
$\begingroup$

This is a weighted version of Set Packing, which was one of the 21 classic problems proven NP-hard by Richard Karp:

Richard M. Karp (1972). "Reducibility Among Combinatorial Problems" (PDF). In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.

As the unweighted version is already NP-hard, your weighted version is too, so it's unlikely that any algorithm will solve every instance of it in polynomial time.

Improve this answer
$\endgroup$
8
  • $\begingroup$ A note for future readers. The linked Wikipedia article cites reduction to weighted independent set, which misses the opportunities for cut-offs as stated in the question... So, if one actually needs to solve instances optimally, (s)he probably should not use a weighted independent set solver. $\endgroup$
    – AlwaysLearning
    Jan 16, 2018 at 19:51
  • 2
    $\begingroup$ Well, I'm not sure about that... I think your dominance rule translates into a very similar rule for Weighted Independent Set: "If there is a vertex $v_3$ that has 2 neighbours $v_1$ and $v_2$ such that (a) $N(v_3) \setminus \{ v_2, v_3 \} \subseteq (N(v_1) \cup N(v_2)) \setminus \{ v_1, v_2, v_3 \}$and (b) $w(v_3) > w(v_1) + w(v_2)$, then delete $v_1$ and $v_2$, since including either one prevents including $v_3$, while including $v_3$ gives a higher weight than including both and does not introduce any further constraints." (Here $N(v)$ is the set of neighbouring vertices of a vertex $v$.) $\endgroup$
    – j_random_hacker
    Jan 16, 2018 at 20:22
  • $\begingroup$ In fact, I suspect it could even make those opportunities clearer in some cases. Suppose $S_3$ was $\{1,2,3,5\}$ instead of $\{1,2,3\}$ but that each other set $S_i$ which contains $5$ also contains either $1$, $2$, $3$ or $4$ (ie has a non-empty intersection with either $S_1$, $S_2$ or both). Then your "cutoff" condition doesn't apply (as $S_3 \not \subseteq S_1 \cup S_2$) but @j_random_hacker's rule applies (as any neighbour of $v_3$ corresponding to a set containing $5$ would also be a neighbour of either $v_1$ or $v_2$ because of the previous implication) $\endgroup$
    – Caninonos
    Jan 16, 2018 at 20:51
  • $\begingroup$ @Caninonos Suppose $S_4=\{1, 5\}$. Then we have $S_3\cup S_4\subseteq S_1\cup S_2\cup S_4$ and my condition applies. $\endgroup$
    – AlwaysLearning
    Jan 17, 2018 at 15:58
  • $\begingroup$ @j_random_hacker This is very interesting. You are right, but I think that my condition can be verified much more efficiently during state-space search... I think this deserves a research article. Would you like to collaborate? $\endgroup$
    – AlwaysLearning
    Jan 17, 2018 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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