0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – greybeard Feb 4 at 9:16
  • $\begingroup$ I've been testing with both unit weights and distance between navigation mesh face centroids as weights, but both $\endgroup$ – user3064869 Feb 4 at 9:28
  • $\begingroup$ 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. $\endgroup$ – user3064869 Feb 4 at 10:21
  • $\begingroup$ (I went the other way just to find connected mincut partitioning hard to find.) $\endgroup$ – greybeard Feb 4 at 10:24
  • $\begingroup$ Do you mean that mincut partitioning in academic context usually implies that the partitions are disconnected? $\endgroup$ – user3064869 Feb 4 at 16:50
1
$\begingroup$

The Kernighan-Lin algorithm tries to find a partition. As far as I can tell, the partition it finds might or might not be connected; I don't see any guarantee that it will output a connected partition. There is also no guarantee that it finds the optimal partition. Even if the optimal partition is connected, I don't think there is any guarantee that the Kernighan-Lin algorithm will output a connected partition.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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