# Maximizing the Sum of a Subset with Excluding pairs

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.