mlsanityData to 14 Oct 2026

Exact Algorithms for Maximum Independent Set

arXiv 1312.6260 ↗First posted 21 Dec 2013cs.DScited by 10

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 1; 2024: 2; 2025: 1; 2026: 3.

10 papers.

  1. 2022What's Wrong with Deep Learning in Tree Search for Combinatorial Optimizationcited by 37
  2. 2024Learning-augmented Maximum Independent Setcited by 11
  3. 2022Listing Maximal k-Plexes in Large Real-World Graphscited by 3
  4. 2023Fast Maximum k-Plex Algorithms Parameterized by Small Degeneracy Gapscited by 2
  5. 2022Mining Large Independent Sets on Massive Graphscited by 1
  6. 2024A Faster Branching Algorithm for the Maximum k-Defective Clique Problemcited by 0
  7. 2025Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphscited by 0
  8. 2026Problem Reductions at Scale: Agentic Integration of Computationally Hard Problemscited by 0
  9. 2026frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Studycited by 0
  10. 2026Dual-GNN Multilevel Coarsening for Maximum Independent Setcited by 0