<p><em>(transferred from a comment above)</em></p>

<p>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.</p>

CC BY-SA 3.0
2011-05-12T04:14:00.117Z
2011-05-12T04:14:00.117Z
Suresh Venkat
<p>Take a look at the <a href="http://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm">Kerninghan-Lin</a> heuristic algorithm.</p>

CC BY-SA 3.0
2011-05-13T08:02:32.507Z
ah duh. the swap algorithm is indeed Kernighan-Lin. Thanks!
Suresh Venkat
CC BY-SA 3.0
2011-05-13T09:39:31.713Z
Not quite, it is somewhat more sophisticated.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2011-05-13T11:00:58.907Z
thx, implementing now, gonna add it to the JGraphT opensource graph library
Berty
CC BY-SA 3.0
2011-05-13T20:57:06.150Z
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
CC BY-SA 3.0
2011-05-13T08:00:50.007Z
2011-05-13T08:00:50.007Z
Kristoffer Arnsfelt Hansen
<p>Besides basic <a href="https://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm" rel="nofollow">Kerninghan-Lin</a> algorithm (complexity $O(n^2 log(n))$), there's also <a href="https://en.wikipedia.org/wiki/Fiduccia-Mattheyses_algorithm" rel="nofollow">Fiduccia-Mattheyses</a> (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.</p>

<p>Yet another approach chooses <a href="http://glaros.dtc.umn.edu/gkhome/metis/metis/overview" rel="nofollow">METIS</a> which is a multi-level graph partitioning algorithm by Karypis and Kumar (1999). You can find an open-source implementation of METIS <a href="http://glaros.dtc.umn.edu/gkhome/metis/metis/download" rel="nofollow">Karypis Labs website</a>.</p>

<p>"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.</p>

CC BY-SA 3.0
2015-09-09T13:00:31.477Z
2015-09-09T13:00:31.477Z
Tombart
<p>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</p>

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

<p><em>edit</em></p>

<p>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</p>

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

CC BY-SA 3.0
2011-05-11T16:55:17.340Z
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
CC BY-SA 3.0
2011-05-11T16:57:40.743Z
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
CC BY-SA 3.0
2011-05-12T00:51:51.430Z
If this is based on a piratical problem then you should explain the motivation a little more.
Kaveh
CC BY-SA 3.0
2011-05-12T03:54:39.753Z
@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
CC BY-SA 3.0
2011-05-12T04:13:16.700Z
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
CC BY-SA 3.0
2011-05-13T07:15:59.193Z
@Berty, I think you should try implementing it yourself for now. I'm not aware of pseudocode. However, you should also take a look at the METIS library for graph partitioning. While the methods there are spectral, they might serve your purpose.
Suresh Venkat
<ds.algorithms><graph-algorithms><heuristics>
Heuristics for graph bisection
Berty
# Heuristics for graph bisection

(Asked by: username_0 on 2011-05-11)

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

**Tags:** ds.algorithms, graph-algorithms, heuristics

> **Comments:**
> **username_1**: 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.  
> **username_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?  
> **username_3**: If this is based on a piratical problem then you should explain the motivation a little more.  
> **username_2**: @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.  
> **username_1**: 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.  
> **username_1**: @username_0, I think you should try implementing it yourself for now. I'm not aware of pseudocode. However, you should also take a look at the METIS library for graph partitioning. While the methods there are spectral, they might serve your purpose.  

---

## 3 answers

### Answer by username_1 on 2011-05-12. Score: 6

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


---

### Answer by username_4 on 2011-05-13. Score: 5

Take a look at the [Kerninghan-Lin](http://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm) heuristic algorithm.

> **Comments:**
> **username_1**: ah duh. the swap algorithm is indeed Kernighan-Lin. Thanks!  
> **username_4**: Not quite, it is somewhat more sophisticated.  
> **username_0**: thx, implementing now, gonna add it to the JGraphT opensource graph library  
> **username_5**: 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?  

---

### Answer by username_6 on 2015-09-09. Score: 2

Besides basic [Kerninghan-Lin](https://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm) algorithm (complexity $O(n^2 log(n))$), there's also [Fiduccia-Mattheyses](https://en.wikipedia.org/wiki/Fiduccia-Mattheyses_algorithm) (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](http://glaros.dtc.umn.edu/gkhome/metis/metis/overview) 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](http://glaros.dtc.umn.edu/gkhome/metis/metis/download).

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


---

