Finding set of disjoint sets with additional value optimization

Question

I've got a set $Q$ of pairs $[S, v]$ where $S$ is a nonempty set and $v$ is a value ($v \in \mathbb{N}_{+}$). I need to find a subset $R$ of $Q$ with following properties:

• Sum of all $v$'s is maximum
• $S$ from all pairs construct a disjoint set

Example. For given set $Q$:

$Q = \{[\{1, 2\}, 5], [\{2, 3\}, 8], [\{3, 4\}, 2], [\{5\}, 1]\}$

Result $R$ should be:

$R = \{[\{2, 3\}, 8], [\{5\}, 1]\}$

I came up with an obvious algorithm which constructs every possible set of pairs whose $S$ constructs disjoint set:

T = {}
foreach (q in Q)
  foreach (t in T)
    if (union of all S from t and S from q constructs a disjoint set)
      add copy of t to T
      add q to t
  add {q} to T

Then I would find t with highest sum of all it's v's.

This is worst case $O(2^n)$. Can I do better than this? I will appreciate any additional information regarding this problem.

Answer 1

Your problem is polynomially equivalent to the maximum-weight independent set problem problem, and the standard results for that problem apply directly to your problem as well.

If all the values were the same (say, $v=1$ for all pairs), then your problem would equivalent to the independent set problem. In particular, treat each pair as its own vertex, and build an undirected graph $G$ where you have an edge between two pairs if they are disjoint. Then the solution to your problem is exactly the largest independent set in $G$. One can also construct a reduction the other way as well: given any undirected graph $G$, we can form an instance of your problem by construct a set corresponding to each vertex of $G$ (namely, the set of edges incident on that vertex), each of value 1; then the solution to your problem is the maximum independent set of $G$.

The independent set problem is NP-complete, so it follows that your problem is NP-complete as well. Therefore, you should not expect any polynomial-time solution to your problem.

Because you allow arbitrary values to be associated with each set, your problem is basically equivalent to a slight generalization of the independent set problem, namely, the maximum-weight independent set problem. Each vertex has a weight associated with it, and the weight of an independent set is the sum of the weights of the vertices in the independent set, and the problem is to find the heaviest independent set in the graph. This is obviously at least as hard as the standard independent set problem, so also NP-complete.

Fortunately, there are standard algorithms for the independent set problem, and they can be extended to the maximum-weight independent set problem as well. For instance, you can formulate the problem as an integer linear programming (ILP) instance and then try to solve it using an off-the-shelf ILP solver. There are also exponential-time algorithms for independent set whose running time is asymptotically faster than $\Theta(2^n)$; I don't know whether they extend to the maximum-weight independent set problem as well, but you could check the literature to see, if this is of interest. You could try applying them to your problem.

Unfortunately, the independent set problem is known to be hard to approximate to within a constant factor (unless P = NP), so you should not expect efficient approximation algorithms for your problem, either.