Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

i'm trying to find an algorithm that will divide my graph in 2 parts by telling me what connections should be broken but the 2 parts should contain about the same number of nodes

its for a practical problem that i'm implementing. the graph will never have more then 64 nodes.

edit

this will be applied to a 64 nodes graph every time the program runs. the connections have distances from 0-90, where 90 is far apart

the described algorithm sounds good is it an existing one? can you get a link to pseudo code? or should i try implementing it myself ^^

share|improve this question
5  
The problem you want to solve is called Graph Bisection and is NP-hard. A simple heuristic that might work well in your case is to find two nodes that are as far apart as possible, and then grow out their neighborhoods till you get roughly equal sizes on both. Another local improvement heuristic is to take a candidate solution, and find two vertices to swap that will reduce the cut size. – Suresh Venkat♦ May 11 '11 at 16:55
2  
A couple questions: Do the edges have weights or is the cut minimal on the number of edges? What do you mean by "about the same number of nodes"? Also, will you be implementing this algorithm for many graphs of 64 nodes or for a single graph of 64 nodes? – bbejot May 11 '11 at 16:57
If this is based on a piratical problem then you should explain the motivation a little more. – Kaveh♦ May 12 '11 at 0:51
@Suresh, do you know if the local improvement algorithm you describe is a good worst-case approximation? It sounds like it should be, but I can't think of why. – bbejot May 12 '11 at 3:54
I don't think it is. in general bisection is hard: a hard result was to get a bisection that splits the graph 1/3-2/3 and is within log n of the optimal 1/2-1/2 split. – Suresh Venkat♦ May 12 '11 at 4:13
show 1 more comment

2 Answers

up vote 6 down vote

(transferred from a comment above)

The problem you want to solve is called Graph Bisection and is NP-hard. A simple heuristic that might work well in your case is to find two nodes that are as far apart as possible, and then grow out their neighborhoods till you get roughly equal sizes on both. Another local improvement heuristic is to take a candidate solution, and find two vertices to swap that will reduce the cut size.

share|improve this answer
up vote 4 down vote

Take a look at the Kerninghan-Lin heuristic algorithm.

share|improve this answer
ah duh. the swap algorithm is indeed Kernighan-Lin. Thanks! – Suresh Venkat♦ May 13 '11 at 8:02
Not quite, it is somewhat more sophisticated. – Kristoffer Arnsfelt Hansen May 13 '11 at 9:39
thx, implementing now, gonna add it to the JGraphT opensource graph library – Berty May 13 '11 at 11:00
given that Ker-Lin is very popular for various applications of min bisection, the theory thing to ask is, has anyone been able to prove guarantees for it in some special case: e.g. for random graphs (related:expanders), for graphs arising from probabilistic models of social networks, something else? – Sasho Nikolov May 13 '11 at 20:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.