KIT | KIT-Bibliothek | Impressum | Datenschutz

Shared-Memory n-level Hypergraph Partitioning

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


We present a shared-memory algorithm to compute high-quality solutions to the balanced k-way hypergraph partitioning problem. This problem asks for a partition of the vertex set into k disjoint blocks of bounded size that minimizes the connectivity metric (i.e., the sum of the number of different blocks connected by each hyperedge). High solution quality is achieved by parallelizing the core technique of the currently best sequential partitioner KaHyPar: the most extreme n-level version of the widely used multilevel paradigm, where only a single vertex is contracted on each level. This approach is made fast and scalable through intrusive algorithms and data structures that allow precise control of parallelism through atomic operations and finegrained locking. We perform extensive experiments on more than 500 real-world hypergraphs with up to 140 million vertices and two billion pins (sum of hyperedge sizes). We find that our algorithm computes solutions that are on par with a comparable configuration of KaHyPar while being a factor of 9 faster using 10 threads.

DOI: 10.1137/1.9781611977042.11
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsmonat/-jahr 01.2022
Sprache Englisch
Identifikator ISBN: 978-1-61197-704-2
KITopen-ID: 1000152816
HGF-Programm 46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups
Erschienen in 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). Ed.: C. Phillips, Meeting on Algorithm Engineering and Experiments (ALENEX 2022 2022) Online, 09.01.2022–10.01.2022
Veranstaltung SIAM Symposium on Algorithm Engineering and Experiments (ALENEX 2022), Online, 09.01.2022 – 10.01.2022
Verlag Society for Industrial and Applied Mathematics (SIAM)
Seiten 131–144
Vorab online veröffentlicht am 05.01.2022
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page