The Kernighan–Lin algorithm is a
heuristic algorithm
In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for solving a problem more quickly when classic methods are too slow for finding an approximate solution, or whe ...
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
Very large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit (Metal Oxide Semiconductor) ...
.
Description
The input to the algorithm is an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
with vertex set , edge set , and (optionally) numerical weights on the edges in . The goal of the algorithm is to partition into two disjoint subsets and of equal (or nearly equal) size, in a way that minimizes the sum of the weights of the subset of edges that cross from to . 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
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
to pair up vertices of with vertices of , 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 .
Given a graph with vertices, each pass of the algorithm runs in time .
In more detail, for each
, 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''. Similarly, define
,
for each
. Furthermore, let
:
be the difference between the external and internal costs of ''s''. 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''.
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
+ D
− 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
..., gv
if g_max > 0 then
Exchange av
av
..., av
with bv
bv
..., bv
until (g_max ≤ 0)
return G(V, E)
See also
*
Fiduccia–Mattheyses algorithm
References
{{DEFAULTSORT:Kernighan-Lin algorithm
Combinatorial optimization
Combinatorial algorithms
Heuristic algorithms