# Scalable Kernelization for Maximum Independent Sets

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Aug 2017.

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

- [What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization](https://mlsanity.com/paper/2201.10494/) (2022)
- [Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling](https://mlsanity.com/paper/2409.02135/) (2024)
- [Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set](https://mlsanity.com/paper/2502.03669/) (2025)
- [Mining Large Independent Sets on Massive Graphs](https://mlsanity.com/paper/2208.07777/) (2022)
- [Improved Exact and Heuristic Algorithms for Maximum Weight Clique](https://mlsanity.com/paper/2302.00458/) (2023)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)
- [On lower bounds of the density of planar periodic sets without unit distances](https://mlsanity.com/paper/2411.13248/) (2024)
- [Compute Time Scaling with Recursive Models for Combinatorial Optimization](https://mlsanity.com/paper/2609.34585/) (2026)

## Abstract (arXiv)

The most efficient algorithms for finding maximum independent sets in both theory and practice use reduction rules to obtain a much smaller problem instance called a kernel. The kernel can then be solved quickly using exact or heuristic algorithms---or by repeatedly kernelizing recursively in the branch-and-reduce paradigm. It is of critical importance for these algorithms that kernelization is fast and returns a small kernel. Current algorithms are either slow but produce a small kernel, or fast and give a large kernel. We attempt to accomplish both of these goals simultaneously, by giving an efficient parallel kernelization algorithm based on graph partitioning and parallel bipartite maximum matching. We combine our parallelization techniques with two techniques to accelerate kernelization further: dependency checking that prunes reductions that cannot be applied, and reduction tracking that allows us to stop kernelization when reductions become less fruitful. Our algorithm produces kernels that are orders of magnitude smaller than the fastest kernelization methods, while having a similar execution time. Furthermore, our algorithm is able to compute kernels with size comparable to the smallest known kernels, but up to two orders of magnitude faster than previously possible. Finally, we show that our kernelization algorithm can be used to accelerate existing state-of-the-art heuristic algorithms, allowing us to find larger independent sets faster on large real-world networks and synthetic instances.