I have a graph where I want to select a subset of the nodes subject to a particular constraint: An edge between nodes A and B indicates that I cannot select BOTH A and B to belong to the subset. I want to select the largest set of nodes that obeys the constraint, where "largest" can either be a count of nodes or a sum of node weights.
My question is: What is this problem called? I tried Googling "maximum subgraph avoiding certain edges" but didn't find anything (in the first couple of responses) that resembled my problem. Is there a name for this problem? Is there an algorithmic solution other than enumerating the power set and find the largest subset that satisfies the constraint?
The object you are describing is a so-called "Independent Set". Formally, an independent set is a set of nodes such that none of them are adjacent. This corresponds to your constraint that if there is an edge between $A$ and $B$, only one of them can be part of the set.
If you want the largest independent set in terms of count of the nodes, then you just search for "Maximum Independent Set", where "maximum" indicates that you mean the largest in terms of size. For the weighted vesion, just google "maximum weight independent set".
It is a fairly common (hard) problem, so there should be a lot of research on it.