---
title: "Kernighan-Lin Algorithm | Combinatorics"
description: "Kernighan-Lin Algorithm is a heuristic for splitting a graph into two balanced parts while minimizing edge cut, a core combinatorics tool in graph partitioning."
canonical: "https://fiveable.me/combinatorics/key-terms/kernighan-lin-algorithm"
type: "key-term"
subject: "Combinatorics"
unit: "Unit 16"
---

# Kernighan-Lin Algorithm | Combinatorics

## Definition

The Kernighan-Lin Algorithm is a heuristic for graph partitioning in combinatorics. It improves a two-way split of a graph by swapping vertex pairs to lower the edge cut while keeping the parts balanced.

## What It Is

The Kernighan-Lin Algorithm is a graph partitioning heuristic in combinatorics that tries to split the vertices of a graph into two groups so the number, or total weight, of edges crossing between the groups is as small as possible. You usually start with some initial split, then the algorithm looks for swaps that make the cut cheaper.

The basic move is not to move one vertex at a time at random. Instead, it evaluates pairs of vertices, one from each side of the partition, and asks whether swapping them reduces the edge cut enough to justify the change. That pairing matters because a good partition needs more than a small cut, it also needs the two sides to stay balanced.

A useful way to think about the method is local search. The algorithm makes the current partition slightly better, checks the new cost, and keeps going until no swap gives improvement. That means it can get stuck at a local minimum, which is a partition that looks good compared with nearby swaps but is not necessarily the best possible split of the whole graph.

This is why Kernighan-Lin shows up in combinatorial optimization rather than exact counting. Many graph partitioning problems are too large for brute force or exact search, so you trade certainty for speed and a better-than-random result. In a course setting, that makes the algorithm a clean example of how combinatorial methods use structure, cost functions, and iterative improvement.

A small example helps: if you have a graph with two clusters connected by only a few edges, a bad initial partition might cut through the middle of both clusters. Kernighan-Lin will try swapping vertices so the groups line up more with the natural cluster structure, which usually lowers the cut. The final answer is the best partition the heuristic found, not a proof of the global optimum.

## Why It Matters

Kernighan-Lin matters because it shows how combinatorics handles optimization problems on graphs when exact methods are too slow. Graph partitioning comes up whenever you want to split a network into pieces that talk mostly inside the piece and as little as possible across pieces. That shows up in circuit layout, clustering, parallel processing, and data organization.

It also gives you a concrete example of an edge cut, which is one of the main quantities students track in graph partitioning problems. If you can count how many edges cross between two sets, you can compare two partitions and decide which one is better. Kernighan-Lin turns that counting idea into a repeated improvement process.

The algorithm also reinforces a big idea in combinatorial optimization: the best practical answer is not always the mathematically exact answer. In large graphs, exact partitioning can be expensive, so heuristics are used to get a good solution quickly. That tradeoff is a recurring theme in combinatorics and computer science.

If you are reading a problem about data structures or graph algorithms, Kernighan-Lin helps you recognize when the task is not just to describe a graph, but to optimize its structure under constraints. The balance requirement is just as important as the cut size, so you are usually judging two things at once: how many edges cross and whether the parts stay comparable in size.

## Connections

### Graph Partitioning

Kernighan-Lin is one specific method for graph partitioning. The broader topic asks how to divide vertices into parts that satisfy some goal, often a small cut and a balanced split. If you see a problem asking for a partition of a graph, this is the general framework, and Kernighan-Lin is one heuristic you might use to improve an initial guess.

### Edge Cut

The edge cut is the score Kernighan-Lin tries to reduce. Every swap is judged by how many edges stop crossing between the two sides, so you need to count crossing edges carefully. If you mix up the cut with the number of vertices in a part, you will miss the actual optimization target.

### Heuristic Method

Kernighan-Lin is a heuristic because it aims for a good answer fast, not a guaranteed best answer. That distinction matters in combinatorics whenever a problem is too large for exhaustive search. Heuristics are common when the graph is big and the point is to improve a solution, not prove optimality.

### [spectral partitioning](/combinatorics/key-terms/spectral-partitioning)

Spectral partitioning is another way to split a graph, but it uses eigenvalues and eigenvectors instead of local swaps. Comparing it with Kernighan-Lin helps you see two different strategies for the same goal. One is algebraic and global, while the other is iterative and local.

## On the AP Exam

A problem set question might give you a graph and ask how Kernighan-Lin would improve an initial partition, or which swap lowers the edge cut. Your job is to identify the two sides of the partition, count crossing edges, and compare candidate swaps by their effect on the cut and balance. If the question is conceptual, explain that the method is iterative and heuristic, so it can improve a partition without guaranteeing the global optimum. If a graph is shown in class or on a quiz, you may be asked to mark a better split or justify why a partition is a local minimum. The key move is always the same: track the crossing edges, test swaps, and describe the improvement step by step.

## Kernighan-Lin Algorithm vs spectral partitioning

Kernighan-Lin and spectral partitioning both split graphs, but they use different tools. Kernighan-Lin improves a partition by swapping vertex pairs and checking the edge cut after each move. Spectral partitioning uses matrix methods and eigenvectors to suggest a cut. If a question asks about local swapping, it is Kernighan-Lin, not spectral partitioning.

## Key Takeaways

- The Kernighan-Lin Algorithm is a heuristic for splitting a graph into two balanced parts with a small edge cut.
- It improves an initial partition by swapping pairs of vertices and keeping the changes that reduce the cut cost.
- The method is iterative, so it keeps making local improvements until no better nearby swap is found.
- Because it is a heuristic, it can find a very good partition without proving it is the absolute best one.
- In combinatorics, it is a useful example of how graph structure and optimization work together.

## FAQs

### What is Kernighan-Lin Algorithm in Combinatorics?

It is a heuristic method for graph partitioning. The algorithm tries to divide the vertices of a graph into two balanced groups while minimizing the number of edges that cross between them. You use it when you want a better partition, not necessarily the exact best one.

### How does the Kernighan-Lin Algorithm reduce edge cut?

It starts with an initial split of the graph, then checks pairs of vertices on opposite sides and swaps them if the swap lowers the edge cut. After each round of swaps, it keeps the best improvement found. This local-search approach is what makes it efficient on larger graphs.

### Is Kernighan-Lin Algorithm exact or heuristic?

It is heuristic, not exact. That means it aims for a good partition quickly, but it does not guarantee the global optimum. In combinatorics, that tradeoff matters a lot when the graph is large and exact search would be too slow.

### What is a common mistake with Kernighan-Lin Algorithm?

A common mistake is focusing only on reducing the edge cut and forgetting the balance requirement. A tiny cut is not enough if one partition becomes much larger than the other. The algorithm is trying to improve both the cut and the quality of the split at the same time.

## Related Study Guides

- [16.4 Combinatorial aspects of data structures](/combinatorics/unit-16/combinatorial-aspects-data-structures/study-guide/w6GWahbuHeUwQxeC)

## About This Document

Canonical Fiveable pages are available as Markdown at the same path plus `.md`.

- [llms.txt](https://fiveable.me/llms.txt): index of Fiveable's sections and URL patterns
- [llms-full.txt](https://fiveable.me/llms-full.txt): complete subject and unit listing
- [MCP server](https://fiveable.me/mcp): call Fiveable as tools instead of fetching pages (`https://fiveable.me/api/mcp`)
- [MCP server for AP teachers](https://fiveable.me/mcp/teachers): a teacher's classes, assignments and AP-rubric grading (`https://fiveable.me/api/mcp/teacher`)

## Structured Data

```json
{"@context":"https://schema.org","@graph":[{"@type":"LearningResource","@id":"https://fiveable.me/combinatorics/key-terms/kernighan-lin-algorithm#resource","name":"Kernighan-Lin Algorithm | Combinatorics","url":"https://fiveable.me/combinatorics/key-terms/kernighan-lin-algorithm","learningResourceType":"Concept explainer","educationalLevel":"AP® / High School","about":{"@id":"https://fiveable.me/combinatorics/key-terms/kernighan-lin-algorithm#term"},"audience":{"@type":"EducationalAudience","educationalRole":"student"},"dateModified":"2026-07-03T02:21:06.613Z","isPartOf":{"@type":"Collection","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"},"publisher":{"@type":"Organization","name":"Fiveable","url":"https://fiveable.me"}},{"@type":"DefinedTerm","@id":"https://fiveable.me/combinatorics/key-terms/kernighan-lin-algorithm#term","name":"Kernighan-Lin Algorithm","description":"The Kernighan-Lin Algorithm is a heuristic for graph partitioning in combinatorics. It improves a two-way split of a graph by swapping vertex pairs to lower the edge cut while keeping the parts balanced.","url":"https://fiveable.me/combinatorics/key-terms/kernighan-lin-algorithm","inDefinedTermSet":{"@type":"DefinedTermSet","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"}},{"@type":"FAQPage","mainEntity":[{"@type":"Question","name":"What is Kernighan-Lin Algorithm in Combinatorics?","acceptedAnswer":{"@type":"Answer","text":"It is a heuristic method for graph partitioning. The algorithm tries to divide the vertices of a graph into two balanced groups while minimizing the number of edges that cross between them. You use it when you want a better partition, not necessarily the exact best one."}},{"@type":"Question","name":"How does the Kernighan-Lin Algorithm reduce edge cut?","acceptedAnswer":{"@type":"Answer","text":"It starts with an initial split of the graph, then checks pairs of vertices on opposite sides and swaps them if the swap lowers the edge cut. After each round of swaps, it keeps the best improvement found. This local-search approach is what makes it efficient on larger graphs."}},{"@type":"Question","name":"Is Kernighan-Lin Algorithm exact or heuristic?","acceptedAnswer":{"@type":"Answer","text":"It is heuristic, not exact. That means it aims for a good partition quickly, but it does not guarantee the global optimum. In combinatorics, that tradeoff matters a lot when the graph is large and exact search would be too slow."}},{"@type":"Question","name":"What is a common mistake with Kernighan-Lin Algorithm?","acceptedAnswer":{"@type":"Answer","text":"A common mistake is focusing only on reducing the edge cut and forgetting the balance requirement. A tiny cut is not enough if one partition becomes much larger than the other. The algorithm is trying to improve both the cut and the quality of the split at the same time."}}]},{"@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Combinatorics","item":"https://fiveable.me/combinatorics"},{"@type":"ListItem","position":2,"name":"Key Terms","item":"https://fiveable.me/combinatorics/key-terms"},{"@type":"ListItem","position":3,"name":"Unit 16","item":"https://fiveable.me/combinatorics/unit-16"},{"@type":"ListItem","position":4,"name":"Kernighan-Lin Algorithm"}]}]}
```