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] 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.


News:
November 2015: Initial Release of the framework.

Licence

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 the following paper:

@inproceedings{kamis2015,
             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 = {Proceedings of the 16th Meeting on Algorithm Engineering and Exerpimentation (ALENEX'16)},
             YEAR = {2016}
}


Download

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 16th 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

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