Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910018979233792 |
|---|---|
| author | Großmann, Ernestine Schulz, Christian Strash, Darren Wagner, Antonie |
| author_facet | Großmann, Ernestine Schulz, Christian Strash, Darren Wagner, Antonie |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10781 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs Großmann, Ernestine Schulz, Christian Strash, Darren Wagner, Antonie Data Structures and Algorithms 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. |
| title | Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.10781 |