# Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations

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

## Key facts

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

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

- [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)
- [Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks](https://mlsanity.com/paper/2505.04674/) (2025)

## Abstract (arXiv)

Given a vertex-weighted graph, the maximum weight independent set problem asks for a pair-wise non-adjacent set of vertices such that the sum of their weights is maximum. The branch-and-reduce paradigm is the de facto standard approach to solve the problem to optimality in practice. In this paradigm, data reduction rules are applied to decrease the problem size. These data reduction rules ensure that given an optimum solution on the new (smaller) input, one can quickly construct an optimum solution on the original input. We introduce new generalized data reduction and transformation rules for the problem. A key feature of our work is that some transformation rules can increase the size of the input. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later throughout the algorithm. In experiments, our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than heuristic solvers DynWVC and HILS on many instances. While the increasing transformations are only efficient enough for preprocessing at this time, we see this as a critical initial step towards a new branch-and-transform paradigm.