0
$\begingroup$

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.

  1. Select the node with the largest difference
  2. A positive difference means select the node and ignore the others
  3. A negative difference means ignore this node and select the others
  4. For a difference of zero it's not as clear which side to select
  5. 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 <> BC, BC <> BD

Total weight is 8 (BA + BC)

Case 3

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

CB <> CC, CC <> 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 <> DB, DA <> DC, DA <> DD, DC <> DE, DC <> 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 <> EB, EA <> EC, EA <> ED, EB <> EC, EC <> EE, EC <> EE

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

Total weight is 8 (EA + EE)

Improve this question
$\endgroup$
3
  • $\begingroup$ What is your question? $\endgroup$
    – Evil
    Jun 7, 2019 at 9:28
  • $\begingroup$ You haven't defined the quantity you're trying to compute, so we can't possibly come up with an algorithm to compute it. We're not going to play "guess the pattern" from your examples. However, it sounds like it's just the total weight of the vertices, minus some amount determined by the edges. Why don't you just compute those two things and subtract them? $\endgroup$
    – David Richerby
    Jun 7, 2019 at 11:16
  • $\begingroup$ I've updated the initial paragraph, so hopefully it is clearer. $\endgroup$
    – David Driver
    Jun 7, 2019 at 11:46

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.