- This article is about the heuristic algorithm for the graph partitioning problem. For a heuristic for the traveling salesperson problem, see Lin–Kernighan heuristic.
The input to the algorithm is an undirected graph G = (V,E) with vertex set V, edge set E, and (optionally) numerical weights on the edges in E. The goal of the algorithm is to partition V into two disjoint subsets A and B of equal (or nearly equal) size, in a way that minimizes the sum T of the weights of the subset of edges that cross from A to B. If the graph is unweighted, then instead the goal is to minimize the number of crossing edges; this is equivalent to assigning weight one to each edge. The algorithm maintains and improves a partition, in each pass using a greedy algorithm to pair up vertices of A with vertices of B, so that moving the paired vertices from one side of the partition to the other will improve the partition. After matching the vertices, it then performs a subset of the pairs chosen to have the best overall effect on the solution quality T. Given a graph with n vertices, each pass of the algorithm runs in time O(n2 log n).
In more detail, for each , let be the internal cost of a, that is, the sum of the costs of edges between a and other nodes in A, and let be the external cost of a, that is, the sum of the costs of edges between a and nodes in B. Similarly, define , for each . Furthermore, let
be the difference between the external and internal costs of s. If a and b are interchanged, then the reduction in cost is
where is the cost of the possible edge between a and b.
The algorithm attempts to find an optimal series of interchange operations between elements of and which maximizes and then executes the operations, producing a partition of the graph to A and B.
1 function Kernighan-Lin(G(V,E)): 2 determine a balanced initial partition of the nodes into sets A and B 3 4 do 5 compute D values for all a in A and b in B 6 let gv, av, and bv be empty lists 7 for (n := 1 to |V|/2) 8 find a from A and b from B, such that g = D[a] + D[b] - 2*c(a, b) is maximal 9 remove a and b from further consideration in this pass 10 add g to gv, a to av, and b to bv 11 update D values for the elements of A = A \ a and B = B \ b 12 end for 13 find k which maximizes g_max, the sum of gv,...,gv[k] 14 if (g_max > 0) then 15 Exchange av,av,...,av[k] with bv,bv,...,bv[k] 16 until (g_max <= 0) 17 return G(V,E)
- Kernighan, B. W.; Lin, Shen (1970). "An efficient heuristic procedure for partitioning graphs". Bell System Technical Journal. 49: 291–307. doi:10.1002/j.1538-7305.1970.tb01770.x.
- Ravikumar, C. P (1995). Parallel methods for VLSI layout design. Greenwood Publishing Group. p. 73. ISBN 978-0-89391-828-6.