Part of the KarlsruheMIS organization.

Given a hypergraph $H = (V, \mathcal{E})$, a strong independent set is a subset $S \subseteq V$ such that each hyperedge contains at most one vertex from $S$. Finding a maximum strong independent set is NP-hard. HyperMIS provides an ILP-based exact solver with data reduction preprocessing that shrinks instances to approximately 22% of their original size, achieving average speedups of 3.84× and up to 53× on real-world instances.

The solver implements nine reduction rules — including degree-one, twin, sunflower, clique, domination, and unconfined reductions — as a preprocessing step for any solver. Applications include constructing perfect minimal hash functions and other combinatorial optimization tasks on hypergraphs.

This is joint work by Ernestine Großmann, Christian Schulz, Darren Strash, and Antonie Wagner.

• GCC (g++) with C++17 support
• CMake 3.13+
• GUROBI ILP solver — set GUROBI_HOME in CMakeLists.txt to match your installation

mkdir build && cd build
cmake ..
make

This produces the following executables:

The output without the -v option is a single CSV line:

instance_name,algo,#vertices,#edges,avg_edge_size,#vertices_reduced,#edges_reduced,avg_edge_size_reduced,offset,time,seed

./run_ilp -g instance.hgr -r -t 3600

./run_reduce -g instance.hgr -p -o reduced.hgr

./run_ilp_graph -g graph.graph -r -t 3600

./hypergraph_to_graph -g instance.hgr -o graph.graph

./run_experiment.sh

This runs the code on instances in the hypergraphs/ folder and stores results in a CSV file.

HyperMIS expects hypergraphs in the extended METIS format. A hypergraph with M edges is stored using M + 1 lines. The first line lists the number of edges, the number of vertices, and optionally a weight type. Each subsequent line lists the vertices of that edge (with an optional leading edge weight).

A hypergraph with 4 edges and 3 vertices, where the third edge contains all three vertices:

4 3
1 3
2 3
1 2 3
1 3

The same hypergraph with edge weights (20, 30, 40, 50) and vertex weights (all 5). The weight type 11 indicates both edge and vertex weights:

4 3 11
20 1 3
30 2 3
40 1 2 3
50 1 3
5
5
5

Vertices are 1-indexed.

The project is released under the MIT License. If you publish results using our algorithms, please acknowledge our work by citing the following paper:

@article{grossmann2026hypermis,
  title     = {Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs},
  author    = {Gro{\ss}mann, Ernestine and Schulz, Christian and Strash, Darren and Wagner, Antonie},
  journal   = {arXiv preprint arXiv:2602.10781},
  year      = {2026},
  url       = {https://arxiv.org/abs/2602.10781}
}