Skip to content
Algorithm Atlas
OptimizationAll categories
ExtendedSource checked

Kernighan-Lin Algorithm

Improves a graph bisection by swapping vertex pairs to reduce cut cost.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Optimization
Difficulty
Advanced
Family
Graph partitioning
Tier
Extended
Status
Verified
Review
Source Checked
Sources
2
Formulas
0
Relationships
2
Code example
Not ready
Visualization
Not ready
Aliases
Kernighan-Lin graph partitioning, KL partitioning

Overview

Kernighan-Lin is a local-search graph partitioning heuristic that repeatedly chooses vertex swaps between two partitions to reduce the number or weight of crossing edges.

Core Concepts

graph partitioninglocal searchbisectioncut cost

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n^2) per pass in common bisection implementations

Average

O(n^2) per pass in common bisection implementations

Worst

O(n^2) per pass in common bisection implementations

Space

O(n + m)

When to Use

  • Use when a balanced graph partition needs local improvement.

When Not to Use

  • Do not expect a global optimum from a local-search heuristic.

What It Does

  • Computes graph partitioning within Graph partitioning workloads (O(n^2) per pass in common bisection implementations time, O(n + m) space).
  • Works by Improves a graph bisection by swapping vertex pairs to reduce cut cost.
  • Maintains key invariants across graph partitioning, local search, bisection.

Use Cases

  • Circuit partitioning
  • Graph clustering
  • Parallel workload partitioning

Inputs

  • A graph and an initial balanced bisection or partition.

Outputs

  • A locally improved graph partition with lower cut cost.

Pseudocode

  1. 1.Start with a balanced bisection.
  2. 2.Compute swap gains.
  3. 3.Lock and record best swaps.
  4. 4.Apply the best improving prefix.

Canonical Example

Input
A weighted graph split into two equal-size vertex sets.
Output
An improved bisection with lower crossing-edge cost.
Explanation
The method selects beneficial swaps and commits the best prefix of a swap sequence.

Implementation Notes

  • The algorithm maintains gain values for candidate swaps between two partitions.

Common Pitfalls

  • Confusing Kernighan-Lin graph partitioning with Lin-Kernighan for traveling-salesperson tours.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show two graph partitions, candidate vertex swaps, and the cut-cost changes from selected moves.

Kernighan-Lin Algorithm mechanism walkthrough step 1 of 4x₀x₁x₂x*
Step 1 of 4: Start with a balanced bisection.
partition-refinement

Notes

Kernighan-Lin is a graph partitioning heuristic, distinct from Lin-Kernighan for TSP tours.

Sources (2)

What each reference supports for this entry.

Kernighan and Lin (1970)

Paper

Supports the graph partitioning heuristic, bisection objective, and vertex-swap local improvement mechanism.

Open source

Princeton publication record

Documentation

Institutional metadata confirming the title, authors, venue, DOI, and graph-partitioning abstract for the Kernighan-Lin paper.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Used byFiduccia-Mattheyses Algorithm

Optimization · Extended

Fiduccia-Mattheyses builds on Kernighan-Lin-style partition refinement with single-vertex moves and gain buckets.

Compare with this

Relationships

View full relationship page
Used byFiduccia-Mattheyses Algorithm

Fiduccia-Mattheyses builds on Kernighan-Lin-style partition refinement with single-vertex moves and gain buckets.

Related Algorithms

Fiduccia-Mattheyses Algorithm

Tags

GraphOptimizationLocal Search