# Shared-Memory n-level Hypergraph Partitioning

arXiv: https://arxiv.org/abs/2104.08107 · HTML: https://mlsanity.com/paper/2104.08107/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2021.

## Built on by (most cited first, 1 of 1)

- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)

## Abstract (arXiv)

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 fine-grained 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 an order of magnitude faster on average. Moreover, we show that recent non-multilevel algorithms specifically designed to partition large instances have considerable quality penalties and no clear advantage in running time.