Is there any (free) software out there that can perform the Kernighan-Lin partitioning algorithm on a small graph?
I'm aware of Chaco which is an open-source graph partitioning package written in C language. Chaco can do KL as well as many other partitioning heuristics. You can download it from
And user's guide is here