# Graph Partitioning for Independent Sets

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

## Key facts

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

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

- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set](https://mlsanity.com/paper/2502.03669/) (2025)

## Abstract (arXiv)

Computing maximum independent sets in graphs is an important problem in computer science. In this paper, we develop an evolutionary algorithm to tackle the problem. The core innovations of the algorithm are very natural combine operations based on graph partitioning and local search algorithms. More precisely, we employ a state-of-the-art graph partitioner to derive operations that enable us to quickly exchange whole blocks of given independent sets. To enhance newly computed offsprings we combine our operators with a local search algorithm. Our experimental evaluation indicates that we are able to outperform state-of-the-art algorithms on a variety of instances.