# On the Power of Simple Reductions for the Maximum Independent Set Problem

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

## Key facts

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

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

- [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)

## Abstract (arXiv)

Reductions---rules that reduce input size while maintaining the ability to compute an optimal solution---are critical for developing efficient maximum independent set algorithms in both theory and practice. While several simple reductions have previously been shown to make small domain-specific instances tractable in practice, it was only recently shown that advanced reductions (in a measure-and-conquer approach) can be used to solve real-world networks on millions of vertices [Akiba and Iwata, TCS 2016]. In this paper we compare these state-of-the-art reductions against a small suite of simple reductions, and come to two conclusions: just two simple reductions---vertex folding and isolated vertex removal---are sufficient for many real-world instances, and further, the power of the advanced rules comes largely from their initial application (i.e., kernelization), and not their repeated application during branch-and-bound. As a part of our comparison, we give the first experimental evaluation of a reduction based on maximum critical independent sets, and show it is highly effective in practice for medium-sized networks.