Algorithm to select sets of objects while maximizing number of objects covered

Question

If we have different objects,

[A1, A2, A3, B1, B2, B3, B4, B5]

Some calculations will be performed to find compatible objects. For example, lets assume following 3 sets were formed and every set contains compatible objects:

 1. {A1, B2} 
 2. {A3, B2}
 3. {A1, A3, B4, B5}

Now we need to perform filtering. One node can participate only once. For example, if B2 has made a pair with A1, then B2 can not participate in any other set. Which means, if we select set 1, then set 2 will be deleted because B2 has already participated. And set 3 will be deleted because A1 has already participated.

Now we need to do filtering such that we maximize number of objects being utilized. If we select set 1, then we are only utilizing A1 and B2. Thus, optimal way would be to select set 3 which is utilizing 4 objects. And discard sets 1 and sets 2

Right now, i have a complex function which goes through list of sets recursively and keeps on adjusting until no changes are made to existing sets. This is not only inefficient, but it might not work in cases where changing sets can cause ripple effect.

I am not looking for coded solution, but just a guidance that is there any graph algorithm which I should study?

Answer 1

The problem you're describing can be seen as the weighted independent set problem, as follows: Construct a graph $G=(V,E),ドル where every node $v$ in $V$ corresponds to your sets of objects. The nodes $v,w$ have an edge in $E$ if and only if they share an object. The weight of each node is the number of objects contained within the corresponding set.

Now, observe that maximizing the amount of objects used corresponds to finding a set of nodes in $G$ such that 1. none of the nodes are adjacent and 2. the sum of weights over these nodes is maximized. This is precisely the weighted independent set problem.

Unfortunately, this problem is NP-hard, which means an exact efficient algorithm is unlikely to exist (and even less likely to be found). This means that, unless you only have to deal with small values, you would either have to resort to heuristic or approximation algorithms, of which there are a few in the literature. It may be possible that only a particular kind of graphs arise (e.g. trees). In that case, there may be an efficient algorithm, but that depends on your input.