# Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs

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

## Key facts

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

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

- [Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates](https://mlsanity.com/paper/2609.17951/) (2026)

## Abstract (arXiv)

This work addresses the well-known Maximum Independent Set problem in the context of hypergraphs. While this problem has been extensively studied on graphs, we focus on its strong extension to hypergraphs, where edges may connect any number of vertices. A set of vertices in a hypergraph is strongly independent if there is at most one vertex per edge in the set. One application for this problem is to find perfect minimal hash functions. We propose nine new data reduction rules specifically designed for this problem. Our reduction routine can serve as a preprocessing step for any solver. We analyze the impact on the size of the reduced instances and the performance of several subsequent solvers when combined with this preprocessing. Our results demonstrate a significant reduction in instance size and improvements in running time for subsequent solvers. The preprocessing routine reduces instances, on average, to 22% of their original size in 6.76 seconds. When combining our reduction preprocessing with the best-performing exact solver, we observe an average speedup of 3.84x over not using the reduction rules. In some cases, we can achieve speedups of up to 53x. Additionally, one more instance becomes solvable by a method when combined with our preprocessing.