algorithm - Partitioning graph into 2 sets of vertices -

i want partition connected graph 2 sets of vertices, such difference of sum of edge-weights among vertices of each set minimized.

for example, if graph consists of vertices 1,2,3,4,5, consider partition:

set - {1,2,3}

set b - {4,5}

sum = {w(1 2) + w(2 3) + w(1 3)}

sum b = {w(4 5)}

diff = abs(sum - sum b) ... (this 1 possible partition difference.)

so, how find partition such difference minimized?

this problem np hard because @ least hard partition problem.

sketch of proof

consider partition problem have numbers {1,2,3,4,5} wish partition 2 sets small difference possible.

construct graph shown below:

if comes algorithm solve problem can use algorithm partition graph 2 sets such sum of weights within each set minimized.

in optimal solution blue , green nodes must placed different sets (because have edge weight infinity connecting them). remaining nodes connected either blue or green nodes. call ones connected blue set1, , ones connected green set2. partition give optimal answer partition problem.

greedy algorithm

however, depending on structure of graph , values of weights may able reasonable job.

for example, try:

1. choose random permutation of vertices
2. loop through each vertex , assign set 1 or 2 according whichever minimises objective function (which evaluated on vertices assigned far)

repeat algorithm few times , keep track of best score.

when down few vertices left assigned, try brute force evaluation of possible partitions of remaining vertices search solution.