Kernighan–Lin algorithm
- 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 Kernighan–Lin algorithm is a heuristic algorithm for finding partitions of graphs. The algorithm has important applications in the layout of digital circuits and components in VLSI.[1][2]
Description
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, 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. Furthermore, let
be the difference between the external and internal costs of a. 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]
Pseudocode
See [2]
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*E(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[1],...,gv[k]
14 if (g_max > 0) then
15 Exchange av[1],av[2],...,av[k] with bv[1],bv[2],...,bv[k]
16 until (g_max <= 0)
17 return G(V,E)
References
- 1 2 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.
- 1 2 Ravikumār, Si. Pi; Ravikumar, C.P (1995). Parallel methods for VLSI layout design. Greenwood Publishing Group. p. 73. ISBN 978-0-89391-828-6.