Algorithm for graph with nodes grouped into sets
The special case of zero-one weights is already NP-hard. In fact, even determining whether there is a choice such that the total weight is zero is NP-hard. See this question on cstheory.se. (You can arrange that all the weights are, say, $1$ or $2$, and then the condition that two connected parts are fully connected is satisfied.)