# Accelerating Local Search for the Maximum Independent Set Problem

arXiv: https://arxiv.org/abs/1602.01659 · HTML: https://mlsanity.com/paper/1602.01659/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2016.

## Built on by (most cited first, 5 of 5)

- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [A Dual-mode Local Search Algorithm for Solving the Minimum Dominating Set Problem](https://mlsanity.com/paper/2307.16815/) (2023)
- [Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set](https://mlsanity.com/paper/2502.03669/) (2025)
- [Consistent and Distinctive: LLM Benchmark Efficiency via Maximum Independent Set Prompt Selection on Similarity Graphs](https://mlsanity.com/paper/2606.01400/) (2026)
- [On the Dataless Training of Neural Networks](https://mlsanity.com/paper/2510.25962/) (2025)

## Abstract (arXiv)

Computing high-quality independent sets quickly is an important problem in combinatorial optimization. Several recent algorithms have shown that kernelization techniques can be used to find exact maximum independent sets in medium-sized sparse graphs, as well as high-quality independent sets in huge sparse graphs that are intractable for exact (exponential-time) algorithms. However, a major drawback of these algorithms is that they require significant preprocessing overhead, and therefore cannot be used to find a high-quality independent set quickly. In this paper, we show that performing simple kernelization techniques in an online fashion significantly boosts the performance of local search, and is much faster than pre-computing a kernel using advanced techniques. In addition, we show that cutting high-degree vertices can boost local search performance even further, especially on huge (sparse) complex networks. Our experiments show that we can drastically speed up the computation of large independent sets compared to other state-of-the-art algorithms, while also producing results that are very close to the best known solutions.