Apologies if this question exists somewhere. I'm sure it's been asked, but I don't know how to search for it. This is not a homework question but rather a scientific problem I ran into. If this is a standard CS exercise, just mark it as duplicate and point me where I need to go.
Problem statement: Consider an undirected graph with positive integral values on the nodes and negative integral values on the edges. Find the subset of nodes such that the sum of node and edge values is minimized. An edge is only counted if both of its nodes are part of the subset.
- Node values may be >= 0
- In my specific case, the graph is bipartite: nodes are separated into two sets and edges only exist between the sets (I don't think fact is necessary though to create an algorithm)
- The resulting subset does not need to be connected. See the right example.
- It's fine if net-zero nodes are included, also fine if they aren't.
Simple greedy algorithms fail here because if you look at the bottom of the right example. All 3 nodes are required for that subset to become negative. Any two results in a zero/positive score.