KIT | KIT-Bibliothek | Impressum | Datenschutz

High-Quality Hypergraph Partitioning

Schlag, Sebastian; Heuer, Tobias ORCID iD icon 1; Gottesbüren, Lars 1; Akhremtsev, Yaroslav; Schulz, Christian; Sanders, Peter ORCID iD icon 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)


Hypergraphs are a generalization of graphs where edges (aka nets) are allowed to connect more than two vertices. They have a similarly wide range of applications as graphs. This paper considers the fundamental and intensively studied problem of balanced hypergraph partitioning, which asks for partitioning the vertices into k disjoint blocks of bounded size while minimizing an objective function over the hyperedges. Here, we consider the two most commonly used objectives: the cut-net metric and the connectivity metric.

We describe our open source hypergraph partitioner KaHyPar which is based on the successful multi-level approach – driving it to the extreme of using one level for (almost) every vertex. Using carefully designed data structures and dynamic update techniques, this approach turns out to have a very good time–quality tradeoff. We present two preprocessing techniques – pin sparsification using locality sensitive hashing and community detection based on the Louvain algorithm. The community structure is used to guide the coarsening process that incrementally contracts vertices. Portfolio-based partitioning of the contracted hypergraph then already achieves a good initial solution. ... mehr

DOI: 10.1145/3529090
Zitationen: 15
Zitationen: 26
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2022
Sprache Englisch
Identifikator ISSN: 1084-6654
KITopen-ID: 1000152818
HGF-Programm 46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups
Erschienen in ACM Journal of Experimental Algorithmics
Verlag Association for Computing Machinery (ACM)
Band 27
Seiten Art.Nr. 1.9
Vorab online veröffentlicht am 21.04.2022
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page