Finding the maximum disjoint weight in a weighted node graph I have a graph of nodes that reflect resource allocation. Each node has a weight to reflect this. A well formed graph is disjoint, so there will be no edges, and the weight of the graph is just the sum of the nodes. Any graph that contains edges needs to be reduced by removing one of the two nodes on an edge, until all edges are removed and the graph becomes disjoint. After reducing a graph the total weight should be the maximum possible.

I have already tried an algorithm that simply picks the largest node and discards the connected nodes. This has the problem that it may give a total that is too low.

So I need to find a new algorithm that will be accurate more consistently. My current idea is to look at the graph around each node and determine the difference between that node's weight and the total weight of the connected nodes.


Select the node with the largest difference
A positive difference means select the node and ignore the others
A negative difference means ignore this node and select the others
For a difference of zero it's not as clear which side to select
Repeat


At each stage, at least one node (and it's related edges) will be discarded from the graph. Eventually the graph will be made fully disjoint.

Are there any other approaches, and what are the differing costs in terms of time and memory?

Below are some simple examples

Case 1

AA:2, AB:3

No edges, so total weight is 5.

Case 2

BA:3, BB:2, BC:5, BD:2

BB &lt;> BC, BC &lt;> BD

Total weight is 8 (BA + BC)

Case 3

CA:2, CB:3, CC:5, CD:3

CB &lt;> CC, CC &lt;> CD

Total weight is 8 (CA + CB + CD)

My current approach would report 7 (CA + CC)

Case 4

DA:4, DB:3, DC:3, DD:3, DE:4

DA &lt;> DB, DA &lt;> DC, DA &lt;> DD, DC &lt;> DE, DC &lt;> DE

Total weight is 9 (DB + DC + DD)

My current approach would report 8 (DA + DE)

Case 5:

EA:4, EB:3, EC:3, ED:3, EE:4

EA &lt;> EB, EA &lt;> EC, EA &lt;> ED, EB &lt;> EC, EC &lt;> EE, EC &lt;> EE

Note there is complete sub graph between nodes EA, EB, and EC

Total weight is 8 (EA + EE)
The problem that you are trying to solve is called "maximum weight independent set". It is NP-hard so not much hope for exactly solving it efficiently. There exist efficient approximation algorithms though (see e.g. this question).