Split a weighted graph into n graphs to minimize the sum of weights in each graph
What you are searching for is called weighted max-cut.
Suppose I have a graph of N nodes, and each pair of nodes have a weight associated with them. I would like to split this graph into n smaller graphs to reduce the overall weight.