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.

Kernighan–Lin is a O(n³ ) heuristic algorithm for solving the graph partitioning problem. The algorithm has important applications in the layout of digital circuits and components in VLSI.

Description

Let $G(V,E)$ be a graph, and let $V$ be the set of nodes and $E$ the set of edges. The algorithm attempts to find a partition of $V$ into two disjoint subsets $A$ and $B$ of equal size, such that the sum $T$ of the weights of the edges between nodes in $A$ and $B$ is minimized. Let $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 $E_{a}$ be the external cost of a, that is, the sum of the costs of edges between a and nodes in B. Furthermore, let

$D_{a}=E_{a}-I_{a}$

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

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

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

Pseudocode

See

 1  function Kernighan-Lin(G(V,E)):
 2      determine a balanced initial partition of the nodes into sets A and B
 3      A1 := A; B1 := B
 4      do
 5         compute D values for all a in A1 and b in B1
 6         for (n := 1 to |V|/2)
 7            find a[i] from A1 and b[j] from B1, such that g[n] = D[a[i]] + D[b[j]] - 2*c[a[i]][b[j]] is maximal
 8            move a[i] to B1 and b[j] to A1
 9            remove a[i] and b[j] from further consideration in this pass
 10           update D values for the elements of A1 = A1 \ a[i] and B1 = B1 \ b[j]
 11        end for
 12        find k which maximizes g_max, the sum of g[1],...,g[k]
 13        if (g_max > 0) then
 14           Exchange a[1],a[2],...,a[k] with b[1],b[2],...,b[k]
 15     until (g_max <= 0)
 16  return G(V,E)

Directed graph

For a directed graph, the reduction in cost of interchanging a and b is

$T_{old}-T_{new}=D_{a}+D_{b}$

We drop the term of twice the edge cost, because $E_{a}+E_{b}$ and $I_{a}+I_{b}$ no longer count these double. This reflects itself on line 7 of the algorithm where the term $2*c[a[i]][b[j]]$ is dropped.