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]

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

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.^[1]

Pseudocode

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

References

^ ^a ^b 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.
^ ^a ^b Ravikumar, C. P (1995). Parallel methods for VLSI layout design. Greenwood Publishing Group. p. 73. ISBN 978-0-89391-828-6.

[kl-1] 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-2] Ravikumar, C. P (1995). Parallel methods for VLSI layout design. Greenwood Publishing Group. p. 73. ISBN 978-0-89391-828-6.

[1]

[2]

Description

Pseudocode

See also

References