Overview

The graph partitioning problem asks for a division of a graph's node set into k equally sized blocks such that the number of edges that run between the blocks is minimized. An example graph that is partitioned into four blocks:

A mesh around an airfoil.


KaHIP - Karlsruhe High Quality Partitioning - is a family of graph partitioning programs. It includes KaFFPa (Karlsruhe Fast Flow Partitioner), which is a multilevel graph partitioning algorithm, in its variants Strong, Eco and Fast, KaFFPaE (KaFFPaEvolutionary) which is a parallel evolutionary algorithm that uses KaFFPa to provide combine and mutation operations, as well as KaBaPE which extends the evolutionary algorithm. Moreover, specialized techniques are included to partition road networks (Buffoon) and to output a vertex separator from a given partition.

News:
3rd March 2014: We added huge max-flow min-cut instances created with our partitioning framework. The max-flow min-cut instances stem from the local search algorithms within KaFFPa that are used to improve a bipartition of the graph. They contain up to 2.6 billion edges and can be found in the miscellaneous section.
19th February 2014: We now integrated the size-constrained label propagation clustering algorithm as an alone standing program.
14th February 2014: Version 0.6 is out! We integrated improved algorithms for social networks and web graphs. The algorithms integrated are from the paper "Partitioning Complex Networks via Size-constrained Clustering" (see below).

For regular project updates follow us on Twitter.


Licence

The program is licenced under GPL 3.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{sandersschulz2013,
             AUTHOR = {Sanders, Peter and Schulz, Christian},
             TITLE = {{Think Locally, Act Globally: Highly Balanced Graph Partitioning}},
             BOOKTITLE = {Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13)},
             SERIES = {LNCS},
             PUBLISHER = {Springer},
             YEAR = {2013},
             VOLUME = {7933},
             PAGES = {164--175}
}


The algorithms that are included for download are mainly based on the following publications:

  • Peter Sanders and Christian Schulz. Engineering Multilevel Graph Partitioning Algorithms. In Proceedings of the 19th European Symposium on Algorithms (ESA'11), volume 6942 of LNCS, pages 469--480. Springer, 2011. Download PDF.

  • Peter Sanders and Christian Schulz. Distributed Evolutionary Graph Partitioning. In Proceedings of the 12th Workshop on Algorithm Engineering and Experimentation (ALENEX'12), pages 16--19, 2012. Download PDF.

  • Peter Sanders and Christian Schulz. High Quality Graph Partitioning. In Proceedings of the 10th DIMACS Implementation Challenge Workshop: Graph Partitioning and Graph Clustering, pages 1--17, AMS, 2013. Download PDF.

  • Peter Sanders and Christian Schulz. Think Locally, Act Globally: Highly Balanced Graph Partitioning. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of LNCS, pages 164--175, 2013. Download PDF.

  • Christian Schulz. High Quality Graph Partitioning. PhD thesis. Karlsruhe Institute of Technology, 2013.
    ISBN 978-3844264623, epubli GmbH. Download PDF.

  • Roland Glantz and Henning Meyerhenke and Christian Schulz. Tree-based Coarsening and Partitioning of Complex Networks. Technical Report, Karlsruhe Institute of Technology, February 2014. Download PDF.

  • Henning Meyerhenke and Peter Sanders and Christian Schulz. Partitioning of Complex Networks via Size-constrained Clustering. Technical Report, Karlsruhe Institute of Technology, February 2014. Download PDF.

Download

  • KaHIP_0.61.tar.gz (or available on GitHub here)
  • User Guide to KaHIP v0.6
  • Note: this release does NOT contain natural cuts due to an US software patent. If you want to use specialized techniques for road networks, e.g. Buffoon, please send us an email.

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!

Miscellaneous