Karlsruhe Maximum Independent Sets

Overview

This is the open source project KaMIS - Karlsruhe Maximum Independent Sets. Given a graph G=(V,E), the goal of the maximum independent set problem is to compute a maximum cardinality set of vertices I, such that no vertices in the set are adjacent to one another. Such a set is called a maximum independent set. The problem is NP-hard and particularly difficult to solve in large sparse graphs.
So far our framework contains the ReduMIS [1,2] as well as the FastKer [3] algorithm which is an advanced evolutionary algorithm based on graph partitioning (using the KaHIP framework) and incorporates kernelization techniques to compute large independent sets in huge sparse networks. Our algorithm uses reduction techniques and recursively chooses vertices that are likely to be in a large independent set (using an evolutionary approach), to then further kernelize the graph. This opens up the reduction space---which not only speeds up the computation of large independent sets drastically, but also enables us to compute high-quality independent sets on massive instances. Lastly, we now include online mis [6] (which applies reductions on the fly) as well as our codes to solve weighted independent set problems [5]. The code is maintained by Sebastian Lamm.

News:
October 2023: We released a scalable solver for the 2-packing set problem. You can find it here.
May 2020: We integrated weighted independent set code, online mis, switched to MIT licences and now use cmake as a build system. The new version of KaMIS is 2.0.
October 2019: The paper describing the PACE 2019 winning algorithm has been accepted for publication at CSC'20.
July 2019: Our codes won the PACE 2019 challenge, vertex cover track. You can find our PACE Challenge solver here.
August 2019: We integrated our faster kernelization techniques [3] framework.
November 2015: Initial Release of the framework.

Download

Available on GitHub here
User Guide
Branch-and-reduce code that won the PACE challenge is here

Licence

The program is licenced under MIT. Please let us know if you need a commercial licence.
If you publish results using our algorithms, please acknowledge our work by quoting one or more of the following papers:

@article{DBLP:journals/heuristics/LammSSSW17,
  author    = {Sebastian Lamm and
               Peter Sanders and
               Christian Schulz and
               Darren Strash and
               Renato F. Werneck},
  title     = {Finding near-optimal independent sets at scale},
  journal   = {J. Heuristics},
  volume    = {23},
  number    = {4},
  pages     = {207--229},
  year      = {2017},
  url       = {https://doi.org/10.1007/s10732-017-9337-x},
  doi       = {10.1007/s10732-017-9337-x},
  timestamp = {Fri, 27 Dec 2019 21:13:52 +0100},
  biburl    = {https://dblp.org/rec/journals/heuristics/LammSSSW17.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

If you use fast kernelization routines (note that this is the default), the please also cite the following:

@article{DBLP:journals/jea/Hespe0S19,
  author    = {Demian Hespe and
               Christian Schulz and
               Darren Strash},
  title     = {Scalable Kernelization for Maximum Independent Sets},
  journal   = {{ACM} Journal of Experimental Algorithmics},
  volume    = {24},
  number    = {1},
  pages     = {1.16:1--1.16:22},
  year      = {2019},
  url       = {https://doi.org/10.1145/3355502},
  doi       = {10.1145/3355502},
  timestamp = {Fri, 27 Mar 2020 08:38:35 +0100},
  biburl    = {https://dblp.org/rec/journals/jea/Hespe0S19.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

If you use OnlineMIS, then please also cite the following:

@inproceedings{DBLP:conf/wea/DahlumLS0SW16,
  author    = {Jakob Dahlum and
               Sebastian Lamm and
               Peter Sanders and
               Christian Schulz and
               Darren Strash and
               Renato F. Werneck},
  title     = {Accelerating Local Search for the Maximum Independent Set Problem},
  booktitle = {15th International Symposium on Experimental Algorithms {SEA}},
  pages     = {118--133},
  year      = {2016},
  series    = {Lecture Notes in Computer Science},
  volume    = {9685},
  publisher = {Springer},
  url       = {https://doi.org/10.1007/978-3-319-38851-9\_9}
}

If you use the weighted independents set algorithms, please also cite the following:

@inproceedings{DBLP:conf/alenex/Lamm0SWZ19,
  author    = {Sebastian Lamm and
               Christian Schulz and
               Darren Strash and
               Robert Williger and
               Huashuo Zhang},
  title     = {Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs},
  booktitle = {Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, {ALENEX} 2019},
  pages     = {144--158},
  year      = {2019},
  url       = {https://doi.org/10.1137/1.9781611975499.12},
  doi       = {10.1137/1.9781611975499.12},
  publisher = {{SIAM}},
  year      = {2019}
}

Support

Write us an email if you need support!
We are glad for any comments and error reports (or even bug fixes or feature requests) that you send us.
Graphs used in our papers will be provided to you on request!

References

[1] Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, Renato F. Werneck. Finding Near-Optimial Independent Sets at Scale. Proceedings of the 18th Meeting on Algorithm Engineering and Experimentation (ALENEX'16). 2016. PDF here
[2] Sebastian Lamm, Peter Sanders, Christian Schulz. Graph Partitioning for Independent Sets. In Proceedings of the 14th Symposium on Experimental Algorithms (SEA’15), volume 8504 of Lecture Notes in Computer Science, pages 68–81. Springer, 2015. PDF here
[3] Demian Hespe, Christian Schulz and Darren Strash. Scalable Kernelization for Maximum Independent Sets. In Proceedings of the 20th Meeting on Algorithm Engineering and Experimentation (ALENEX'18). 2018. PDF here
[4] Demian Hespe, Sebastian Lamm, Christian Schulz and Darren Strash. WeGotYouCovered: The Winning Solver from the 2019 PACE Implementation Challenge, Vertex Cover Track. SIAM Workshop on Combinatorial Scientific Computing 2020, To appear, 2020. PDF here
[5] Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs. Sebastian Lamm, Christian Schulz, Darren Strash, Robert Williger and Huashuo Zhang. In Proceedings of the 21th Workshop on Algorithm Engineering and Experimentation (ALENEX), pages 144--158, SIAM, 2019. PDF here
[6] Accelerating Local Search for the Maximum Independent Set Problem. Jakob Dahlum, Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash and Renato F. Werneck. In Proceedings of the 15th Symposium on Experimental Algorithms (SEA), volume 9685 of LNCS, pages 118--133. Springer, 2016. PDF here
[7] Finding Near-Optimal Independent Sets at Scale. Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F. Werneck. ACM Journal of Heuristics, Volume 23, Issue 4, pages 207--229, 2017. https://doi.org/10.1007/s10732-017-9337-x.
[8] Scalable Kernelization for Maximum Independent Sets. Demian Hespe, Christian Schulz and Darren Strash. ACM Journal of Experimental Algorithms. Volume 21, Article No. 1, 2019. http://doi.acm.org/10.1145/3355502.

Other Open Source Frameworks

KaHIP -- Karlsruhe High Quality Partitioning
ParHIP -- Parallel High Quality Partitioning
KaMIS -- Karlsruhe Maximum Independent Sets
KaLP -- Karlsruhe Longest Paths
VieClus -- Vienna Graph Clustering
KaDraw -- Karlsruhe Graph Drawing
VieM -- Vienna Process Mapping
KaGen -- Karlsruhe Graph Generation
KaHyPar -- Karlsruhe Hypergraph Partitioning