5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's kinda confusing to have $\mathbb{N}$ right next to an $R$ that isn't the reals and a $Q$ that isn't the rationals. $\endgroup$ – David Richerby Jan 31 '15 at 19:54
  • $\begingroup$ cs.stackexchange.com/q/86848/755 $\endgroup$ – D.W. Jan 16 '18 at 16:41
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Not true. When you translate this problem to weighted independent set, information is lost. Namely, in the original problem, suppose the sets [{1,2}, 1] and [{3,4},1]. If there is a set [{1,2,3},3], then I do not need to consider including the first two sets together into my solution. That is, there are cut-offs to be made in the original problem. $\endgroup$ – AlwaysLearning Jan 16 '18 at 15:12
  • $\begingroup$ @AlwaysLearning, I've edited the answer to make the reasoning clearer. Information may be lost, but all of the statements in my answer remain correct. There is a reduction both ways between this problem and independent set. Therefore, this problem is NP-complete, so you shouldn't expect a polynomial-time algorithm. Also, it remains true that you can apply algorithms for maximum-weight independent set to this problem. $\endgroup$ – D.W. Jan 16 '18 at 16:33

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.