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. The code is maintained by Sebastian Lamm.

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.
August 2019: We integrated our faster kernelization techniques [3] framework.
November 2015: Initial Release of the framework.


The program is licenced under GPL 2.0. 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:

             AUTHOR = {Lamm, S. and Sanders, P. and Schulz, C. and Strash, D. and Werneck, R. F.},
             TITLE = {{Finding Near-Optimal Independent Sets at Scale}},
             BOOKTITLE = {18th Meeting on Algorithm Engineering and Exerpimentation (ALENEX'16)},
             YEAR = {2016}

             AUTHOR = {Hespe, D. and Schulz, C. and Strash, D.},
             TITLE = {{Scalable Kernelization for Maximum Independent Sets}},
             JOURNAL = {Journal of Experimental Algorithms},
             PUBLISHER = {ACM},
             PAGES = {1.16:1--1.16:22},
             VOLUME = {24},
             NUMBER = {1},
             YEAR = {2019}



  • 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!


  • [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

Other Open Source Frameworks

  • KaHIP -- Karlsruhe High Quality Partitioning
  • ParHIP -- Parallel High Quality Partitioning
  • KaDraw -- Karlsruhe Graph Drawing
  • KaLP -- Karlsruhe Longest Paths
  • VieM -- Vienna Mapping and Sparse Quadratic Assignment
  • VieClus -- Vienna Graph Clustering