Kernighan-Lin Partitioning

The idea

Split a graph's vertices into two equal halves so that as few edges as possible cross. Kernighan and Lin's 1970 heuristic starts from any balanced split and improves it in passes. Within a pass: compute for every vertex its gain (cut edges removed minus cut edges created if it switched sides). Pick the pair of unlocked vertices, one per side, whose swap has the best combined gain; swap them tentatively; lock them; recompute gains; repeat until everything is locked. Now look back over the sequence of tentative swaps and keep the prefix whose cumulative gain was maximal, undoing the rest. Run passes until one yields no improvement.

The prefix trick is the essential mechanism of the method: individual swaps in the middle of a pass may be losing moves, but committing to the best prefix lets the algorithm walk through a bad region to a better one, which pure greedy improvement cannot do.

Cost and character

Each pass costs roughly O(n²·log n) with the classic implementation (choosing the best pair dominates). Quality is respectable on small graphs; on large ones it is slow and myopic, which is what its descendants fixed. Fiduccia-Mattheyses reformulated it for hypergraphs at linear time per pass; multilevel methods wrapped it in coarsening.

Where you meet it today

As the ancestor invoked in every partitioning lecture, in interview questions, and conceptually inside every refinement pass of modern partitioners: the gain-bucket sweep with a best-prefix rollback is still recognizably Kernighan-Lin.