Direct graph kk-partitioning with a Kernighan–Lin like heuristic

We show that the Kernighan–Lin like linear time heuristic for bipartitioning unweighted graphs by Fiduccia and Mattheyses can be generalized to kk-partitioning with the same time bounds, avoiding the logarithmic increase incurred by recursive bipartitioning. Furthermore, the direct heuristic allows a better control of the cut.