Pergunta

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).

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top