n-Level Hypergraph Partitioning

Understand

We develop a multilevel algorithm for hypergraph partitioning that contracts the vertices one at a time and thus allows very high quality.

• This includes a rating function that avoids nonuniform vertex weights, an efficient "semi-dynamic" hypergraph data structure, a very fast coarsening algorithm, and two new local search algorithms.
• One is a $k$-way hypergraph adaptation of Fiduccia-Mattheyses local search and gives high quality at reasonable cost.
• The other is an adaptation of size-constrained label propagation to hypergraphs.