# Heuristics for graph bisection

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 ^^

• 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
• 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

(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.

Take a look at the Kerninghan-Lin heuristic algorithm.

• 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

Besides basic Kerninghan-Lin algorithm (complexity $O(n^2 log(n))$), there's also Fiduccia-Mattheyses (1982) heuristic, which is a variant of Kerninghan-Lin with linear complexity $O(E)$, where $E$ is number of edges. It also starts with a random bisection and iteratively improves it by swapping the nodes from one partition to the other. In contrast to K-L, Fiduccia-Mattheyses swaps only one node at a time, the one with the highest difference.

Yet another approach chooses METIS which is a multi-level graph partitioning algorithm by Karypis and Kumar (1999). You can find an open-source implementation of METIS Karypis Labs website.

"A Fast and Highly Quality Multilevel Scheme for Partitioning Irregular Graphs". George Karypis and Vipin Kumar. SIAM Journal on Scientific Computing, Vol. 20, No. 1, pp. 359—392, 1999.