# Does Kernighan-Lin algorithm guarantee its partitions to be a connected graph?

Currently I am experimenting with Kernighan-Lin algorithm to produce coarse representation of navigation mesh for hierarchical pathfinding.

Based on the use case, my requirement is that partitions produced are a connected graph on its own.

For example, a bisection of the below grid

x--x--x--x--x--x
|  |  |  |  |  |
x--x--x--x--x--x
|  |  |  |  |  |
x--x--x--x--x--x


Should produce something along the lines of

a--a--a--b--b--b
|  |  |  |  |  |
a--a--a--b--b--b
|  |  |  |  |  |
a--a--a--b--b--b


where all nodes in partition A can be reached from a node in partition A without crossing a node in partition B.

However in quite a number of tests, I am getting disconnected partitions such as.

a--b--b--b--a--a
|  |  |  |  |  |
a--b--b--b--a--a
|  |  |  |  |  |
b--b--b--a--a--a


I am not able to judge if this is a bug in my code or whether the Kernighan-Lin algorithm by nature does not guarantee connected partitions.

I know that KL algorithm works towards a locally optimal solution for minimum cut, but does the algorithm not guarantee connected partitions?

• Do your edges have an elaborate cost model, or are all of them same/unit cost? If you can, refer to a description of the Kernighan-Lin algorithm - in en.wikipedia, nothing suggesting connected partitions caught my eye. – greybeard Feb 4 at 9:16
• I've been testing with both unit weights and distance between navigation mesh face centroids as weights, but both – user3064869 Feb 4 at 9:28
• Ran out of time for above comment... I've been testing with both unit weights and distance between navigation mesh face centroids as weights, but both approach yielded disconnected partitions. I have read the Wikipedia page but "partitioning" intuitively suggests that a partition is a single contained partition... It would be unintuitive if Kernighan-Lin bisection can produce more than two disconnected groups. If it is the case that KL can produce disconnected single partition, I am surprised I can't seem to find any resources describing its limitations. – user3064869 Feb 4 at 10:21
• (I went the other way just to find connected mincut partitioning hard to find.) – greybeard Feb 4 at 10:24
• Do you mean that mincut partitioning in academic context usually implies that the partitions are disconnected? – user3064869 Feb 4 at 16:50