We develop scalable algorithms for independence problems on graphs: Maximum Independent Set (MIS), Maximum Weight Independent Set (MWIS), 2-Packing Set, and Vertex Cover. Developed at the Algorithm Engineering Group, Heidelberg University.

An independent set of a graph is a set of vertices with no two vertices adjacent. The Maximum Independent Set (MIS) problem asks for the largest such set; the Maximum Weight Independent Set (MWIS) problem generalizes this by assigning weights to vertices and maximizing total weight. The closely related Vertex Cover problem asks for the smallest set of vertices that touches every edge — its complement is a maximum independent set.

A 2-packing set strengthens the independence condition: no two vertices in the set may share a common neighbor (i.e., they must be at distance at least 3). Finding a maximum 2-packing set is NP-hard and closely related to MIS — our solvers reduce it to an equivalent independent set instance after applying specialized data reduction rules.

All these problems are NP-hard and among the hardest in practice. Large sparse graphs with millions of vertices, as they arise in network analysis, computational biology, and route planning, make exact and near-exact solutions especially challenging.

A key ingredient across all our solvers is data reduction: polynomial-time rules that shrink the input graph while preserving the optimal solution. Our DataReductions framework provides a comprehensive reference implementation of all known exact reduction rules for MWIS — usable as a standalone tool or as a library to integrate into your own solver.

Applications include map labeling, computer vision, combinatorial auctions, coding theory, molecular docking, facility location, and any setting that reduces to finding a maximum conflict-free selection.

brew install KarlsruheMIS/kamis/kamis
redumis network.graph --output independent_set.txt --time_limit 60 --console_log

brew install KarlsruheMIS/chils/chils
CHILS -g network.graph -p 16 -t 60 -o solution.txt

git clone https://github.com/KarlsruheMIS/LearnAndReduce.git && cd LearnAndReduce
./get_dep.sh && ./compile_all.sh
./deploy/reduce_and_chils network.graph --output=solution.txt --time_limit=60

git clone https://github.com/KarlsruheMIS/DataReductions.git && cd DataReductions && make
./mwis_reduce -g network.graph --degree_one --domination --twin -v

git clone https://github.com/KarlsruheMIS/HyperMIS.git && cd HyperMIS
mkdir build && cd build && cmake .. && make
./run_ilp -g instance.hgr -r -t 3600

brew install KarlsruheMIS/kamis/red2pack
red2pack_branch_and_reduce network.graph --output=packing.txt --time_limit=60    # exact (unweighted)
red2pack_heuristic network.graph --time_limit=60                                 # heuristic (unweighted)
redw2pack_rnt_exact network.graph --output=packing.txt --time_limit=60           # exact (weighted)