Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have a set of nodes S where all the nodes of an arbitrary integer value. I Also have a set of pairs of nodes from S, indicating that those node cannot be in the same subset. Given a subset of S, how can I determine the largest possible Sum of that subset taking into account the exclusion pairs.
Example:
S = (x1:50, x2:20, x3:30, x4:15, x5:70)
Exclusion = {(x1,x2), (x4,x5), (x2,x4)}
Starting set = (x1,x2,x4,x5)
Best Possible Sum = (x1,x5)
Your problem is known as maximum-weight independent set (more often, simply maximum independent set). We think of the $x_i$ as vertices in a graph, each constraint corresponding to an edge $(x_i,x_j)$. An independent set is a set of vertices with no edges, which is exactly your condition.
Unfortunately, maximum-weight independent set is NP-complete, and $n^{1-\epsilon}$-hard to approximate (for every $\epsilon>0$) even when all weights are the same.
