# Finding Near-Optimal Independent Sets at Scale

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2015.

## Built on by (most cited first, 30 of 33)

- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization](https://mlsanity.com/paper/2502.02941/) (2025)
- [Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets](https://mlsanity.com/paper/2305.17010/) (2023)
- [What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization](https://mlsanity.com/paper/2201.10494/) (2022)
- [DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems](https://mlsanity.com/paper/2406.19705/) (2024)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling](https://mlsanity.com/paper/2409.02135/) (2024)
- [Moco: A Learnable Meta Optimizer for Combinatorial Optimization](https://mlsanity.com/paper/2402.04915/) (2024)
- [Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update](https://mlsanity.com/paper/2407.16468/) (2024)
- [LLM-Guided Search for Deletion-Correcting Codes](https://mlsanity.com/paper/2504.00613/) (2025)
- [A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks](https://mlsanity.com/paper/2203.08209/) (2022)
- [MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization](https://mlsanity.com/paper/2408.02207/) (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)
- [UniCO: Towards a Unified Model for Combinatorial Optimization Problems](https://mlsanity.com/paper/2505.06290/) (2025)
- [CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization](https://mlsanity.com/paper/2602.08210/) (2026)
- [Mining Large Independent Sets on Massive Graphs](https://mlsanity.com/paper/2208.07777/) (2022)
- [QAOA Parameter Transferability for Maximum Independent Set using Graph Attention Networks](https://mlsanity.com/paper/2504.21135/) (2025)
- [A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem](https://mlsanity.com/paper/2510.08627/) (2025)
- [BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Design](https://mlsanity.com/paper/2604.12898/) (2026)
- [Consistent and Distinctive: LLM Benchmark Efficiency via Maximum Independent Set Prompt Selection on Similarity Graphs](https://mlsanity.com/paper/2606.01400/) (2026)
- [Improved Exact and Heuristic Algorithms for Maximum Weight Clique](https://mlsanity.com/paper/2302.00458/) (2023)
- [On lower bounds of the density of planar periodic sets without unit distances](https://mlsanity.com/paper/2411.13248/) (2024)
- [Machine Learning-assisted High-speed Combinatorial Optimization with Ising Machines for Dynamically Changing Problems](https://mlsanity.com/paper/2503.23966/) (2025)
- [Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs](https://mlsanity.com/paper/2505.13754/) (2025)
- [Enabling Population-Based Architectures for Neural Combinatorial Optimization](https://mlsanity.com/paper/2601.08696/) (2026)
- [Neural Certificate Pricing for Combinatorial Optimization Problems](https://mlsanity.com/paper/2607.01185/) (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)
- [Compute Time Scaling with Recursive Models for Combinatorial Optimization](https://mlsanity.com/paper/2609.34585/) (2026)

## Abstract (arXiv)

The independent set problem is NP-hard and particularly difficult to solve in large sparse graphs. In this work, we develop an advanced evolutionary algorithm, which incorporates kernelization techniques to compute large independent sets in huge sparse networks. A recent exact algorithm has shown that large networks can be solved exactly by employing a branch-and-reduce technique that recursively kernelizes the graph and performs branching. However, one major drawback of their algorithm is that, for huge graphs, branching still can take exponential time. To avoid this problem, we recursively choose vertices that are likely to be in a large independent set (using an evolutionary approach), then further kernelize the graph. We show that identifying and removing vertices likely to be in large independent sets opens up the reduction space---which not only speeds up the computation of large independent sets drastically, but also enables us to compute high-quality independent sets on much larger instances than previously reported in the literature.