SOURCE-LINKED INTELLIGENCE

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

arXiv · AI, language, vision and robotics · article · Sep 16, 2026 · UTC

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

Read original source ↗ Open in workspace

recordType: paper
region: Global

Evidence & attribution

arXiv · AI, language, vision and robotics · 2026-09-16T00:23:23.000Z

First collected: 2026-09-20T08:20:57.646Z. This is not the publication date.