# Exact Algorithms for Maximum Independent Set

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Dec 2013.

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

- [What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization](https://mlsanity.com/paper/2201.10494/) (2022)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Listing Maximal k-Plexes in Large Real-World Graphs](https://mlsanity.com/paper/2202.08737/) (2022)
- [Fast Maximum k-Plex Algorithms Parameterized by Small Degeneracy Gaps](https://mlsanity.com/paper/2306.13258/) (2023)
- [Mining Large Independent Sets on Massive Graphs](https://mlsanity.com/paper/2208.07777/) (2022)
- [A Faster Branching Algorithm for the Maximum k-Defective Clique Problem](https://mlsanity.com/paper/2407.16588/) (2024)
- [Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs](https://mlsanity.com/paper/2505.13754/) (2025)
- [Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems](https://mlsanity.com/paper/2604.11535/) (2026)
- [frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study](https://mlsanity.com/paper/2609.02804/) (2026)
- [Dual-GNN Multilevel Coarsening for Maximum Independent Set](https://mlsanity.com/paper/2609.25149/) (2026)

## Abstract (arXiv)

We show that the maximum independent set problem (MIS) on an n-vertex graph can be solved in 1.1996nnO(1) time and polynomial space, which even is faster than Robson's 1.2109nnO(1)-time exponential-space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7, which run in time of 1.1893nnO(1) and 1.1970nnO(1), respectively. Our algorithms are obtained by using fast algorithms for MIS in low-degree graphs in a hierarchical way and making a careful analyses on the structure of bounded-degree graphs.