# Improved Exact and Heuristic Algorithms for Maximum Weight Clique

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 49 references that are in the map.
- First posted on arXiv 1 Feb 2023.

## Builds on (most cited first, 8 of 8)

- [Finding Near-Optimal Independent Sets at Scale](https://mlsanity.com/paper/1509.00764/) (2015)
- [Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs](https://mlsanity.com/paper/1810.10834/) (2018)
- [Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover](https://mlsanity.com/paper/1411.2680/) (2014)
- [Scalable Kernelization for Maximum Independent Sets](https://mlsanity.com/paper/1708.06151/) (2017)
- [Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations](https://mlsanity.com/paper/2008.05180/) (2020)
- [Temporal Map Labeling: A New Unified Framework with Experiments](https://mlsanity.com/paper/1609.06327/) (2016)
- [On the Power of Simple Reductions for the Maximum Independent Set Problem](https://mlsanity.com/paper/1608.00724/) (2016)
- [Recent Advances in Practical Data Reduction](https://mlsanity.com/paper/2012.12594/) (2020)

## Abstract (arXiv)

We propose improved exact and heuristic algorithms for solving the maximum weight clique problem, a well-known problem in graph theory with many applications. Our algorithms interleave successful techniques from related work with novel data reduction rules that use local graph structure to identify and remove vertices and edges while retaining the optimal solution. We evaluate our algorithms on a range of synthetic and real-world graphs, and find that they outperform the current state of the art on most inputs. Our data reductions always produce smaller reduced graphs than existing data reductions alone. As a result, our exact algorithm, MWCRedu, finds solutions orders of magnitude faster on naturally weighted, medium-sized map labeling graphs and random hyperbolic graphs. Our heuristic algorithm, MWCPeel, outperforms its competitors on these instances, but is slightly less effective on extremely dense or large instances.