Kernighan–Lin algorithm

Template:About 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.

Description

The input to the algorithm is an undirected graph Template:Math with vertex set Template:Mvar, edge set Template:Mvar, and (optionally) numerical weights on the edges in Template:Mvar. The goal of the algorithm is to partition Template:Mvar into two disjoint subsets Template:Mvar and Template:Mvar of equal (or nearly equal) size, in a way that minimizes the sum Template:Mvar of the weights of the subset of edges that cross from Template:Mvar to Template:Mvar. 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 Template:Mvar with vertices of Template:Mvar, 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 Template:Mvar. Given a graph with Template:Mvar vertices, each pass of the algorithm runs in time Template:Math.

In more detail, for each $a\in A$, 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. Similarly, define $I_b$, $E_b$ for each $b\in B$. Furthermore, let

$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

$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

Source:

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] − 2×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)

See also

• Fiduccia–Mattheyses algorithm