2015/12/30 by Sebastian Schlag, Vitali Henne, Tobias Heuer +3 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Benchmark (surveying) #Computer science #Discrete mathematics #Graph #Graph partition #Hypergraph #Interconnection Networks and Systems #Mathematics #Parallel computing #Range (aeronautics) #Set (abstract data type) #Theoretical computer science #VLSI and FPGA Design Techniques #Very-large-scale integration
paper · pdf · doi:10.1137/1.9781611974317.5
openalex publication_date 2015/12/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We develop a multilevel algorithm for hypergraph partitioning that contracts the vertices one at a time. Using several caching and lazy-evaluation techniques during coarsening and refinement, we reduce the running time by up to two-orders of magnitude compared to a naive n-level algorithm that would be adequate for ordinary graph partitioning. The overall performance is even better than the widely used hMetis hypergraph partitioner that uses a classical multilevel algorithm with few levels. Aided by a portfolio-based approach to initial partitioning and adaptive budgeting of imbalance within recursive bipartitioning, we achieve very high quality. We assembled a large benchmark set with 310 hypergraphs stemming from application areas such VLSI, SAT solving, social networks, and scientific computing. Experiments indicate that our algorithm is the method of choice for a wide range of hypergraph partitioning tasks. The algorithm presented in this work forms the basis of our hypergraph partitioning framework KaHyPar (Karlsruhe Hypergraph Partitioning).