# Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 21 references that are in the map.
- First posted on arXiv 16 Sep 2026.

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

- [Improved approximation for 3-dimensional matching via bounded pathwidth local search](https://mlsanity.com/paper/1304.1424/) (2013)
- [A recursive theta body for hypergraphs](https://mlsanity.com/paper/2206.03929/) (2022)
- [Large Neighborhood Local Search for the Maximum Set Packing Problem](https://mlsanity.com/paper/1302.4347/) (2013)
- [Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs](https://mlsanity.com/paper/2602.10781/) (2026)

## Abstract (arXiv)

We study the maximum strong independent set problem in a finite hypergraph: find the largest vertex set that intersects every hyperedge in at most one vertex. This objective arises whenever each observed block is a local incompatibility constraint but transitive closure across overlapping blocks is not justified. A motivating example is multi-band LSH-MinHash deduplication, where each collision bucket gives local evidence, while connected-component contraction can impose spurious global equivalences. The paper develops an incidence-structural toolkit for this problem. We prove exact reductions for dominance, incidence twins, and weight-1 blocks; derive closed-form and low-weight upper bounds; introduce puncturing and covering certificates that sharpen those bounds; and analyze a layered greedy clustering algorithm driven by block weights and residual incidence. The algorithmic analysis includes feasibility, maximality, conditional optimality, a layered witness-matching upper bound, and incidence-local complexity bounds. The results give correctness, termination, fixed-point, and optimality certificates for broad incidence families, together with examples showing when different certificates separate or coincide.