Kernighan–Lin algorithm

The Kernighan–Lin algorithm is a heuristic algorithm for finding partitions of graphs. The algorithm has important practical application in the layout of digital circuits and components in electronic design automation of VLSI.^{[1] [2]}

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(n² log n).

In more detail, for each ${\displaystyle a\in A}${\displaystyle a\in A}, let ${\displaystyle I_{a}}${\displaystyle I_{a}} be the internal cost of a, that is, the sum of the costs of edges between a and other nodes in A, and let ${\displaystyle E_{a}}${\displaystyle E_{a}} be the external cost of a, that is, the sum of the costs of edges between a and nodes in B. Similarly, define ${\displaystyle I_{b}}${\displaystyle I_{b}}, ${\displaystyle E_{b}}${\displaystyle E_{b}} for each ${\displaystyle b\in B}${\displaystyle b\in B}. Furthermore, let

${\displaystyle D_{s}=E_{s}-I_{s}}${\displaystyle D_{s}=E_{s}-I_{s}}

be the difference between the external and internal costs of s. If a and b are interchanged, then the reduction in cost is

${\displaystyle T_{old}-T_{new}=D_{a}+D_{b}-2c_{a,b}}${\displaystyle T_{old}-T_{new}=D_{a}+D_{b}-2c_{a,b}}

where ${\displaystyle c_{a,b}}${\displaystyle c_{a,b}} 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 ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B} which maximizes ${\displaystyle T_{old}-T_{new}}${\displaystyle T_{old}-T_{new}} and then executes the operations, producing a partition of the graph to A and B.^[1]

Source:^[2]

function Kernighan-Lin(G(V, E)) is
 determine a balanced initial partition of the nodes into sets A and B
 
 do
 compute D values for all a in A and b in B
 let gv, av, and bv be empty lists
 for n := 1 to |V| / 2 do
 find a from A and b from B, such that g = D[a] + D[b] − ×ばつc(a, b) is maximal
 remove a and b from further consideration in this pass
 add g to gv, a to av, and b to bv
 update D values for the elements of A = A \ a and B = B \ b
 end for
 find k which maximizes g_max, the sum of gv[1], ..., gv[k]
 if g_max > 0 then
 Exchange av[1], av[2], ..., av[k] with bv[1], bv[2], ..., bv[k]
 until (g_max ≤ 0)
 return G(V, E)

• Fiduccia–Mattheyses algorithm

• Combinatorial optimization
• Combinatorial algorithms
• Heuristic algorithms

• Articles with short description
• Short description is different from Wikidata