High-Quality Multi-Constraint Hypergraph Partitioning via Greedy Rebalancing
Nikolai Maas · 2026
Read High-Quality Multi-Constraint Hypergraph Partitioning via Greedy Rebalancing by Nikolai Maas (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-28333.txt.
Introduction
Nikolai Maas lifts multi-constraint hypergraph splitting by fixing one step alone: rebalancing. His greedy local hunt restores balance with a score that always offers a balance-raising move, proven for two limits under capped weights. Plugged into the Mt-KaHyPar splitter, it cut link counts by over eleven percent on average against the next best rival.
Catalog record
| CREATOR | Nikolai Maas |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56018 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.28333
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
High-Quality Multi-Constraint Hypergraph Partitioning via Greedy Rebalancing Nikolai Maas Abstract Multi-constraint hypergraph partitioning is a generalization of balanced partitioning, where the vertex set of a hypergraph is partitioned such that the inter-block connectivity of hyperedges is minimized while balancing the vertices with regard to d d distinct constraints. A prominent class of applications is data distribution tasks, where this allows to achieve good load balance for d d different kinds of resources and simultaneously minimize the communication volume. Although the best approaches for single-constraint partitioning are usually complex (multilevel) algorithms with many components, we show that replacing only one component already leads to high-quality multi-constraint partitions: the rebalancing step, which restores balance for a partition that has (hopefully) small connectivity but violates the constraints. We design a multi-constraint rebalancing algorithm based on greedy local search, proving that balance is always restored for d = 2 d=2 and bounded maximum weight. The key is to ensure monotonically decreasing global imbalance by choosing an imbalance metric where there is always a balance-improving move available. Integrating our algorithm into the state-of-the-art partitioner Mt-KaHyPar, we demonstrate an 11.5 % geometric mean connectivity reduction compared to the next best competitor (Metis) and better reliability regarding partition balance, even though the majority of inputs is outside of the theoretical guarantee. Karlsruhe Institute of Technology, Karlsruhe, [email protected]://orcid.org/0009-0002-6959-417X ccs Theory of computation Design and analysis of algorithms keywords Hypergraph Partitioning, Multi-Constraint Partitioning, Graph Algorithms, Multilevel Algorithms, Local Search, Vector Scheduling, Multidimensional Load Balancing † † runningauthor: N. Maas † † copyright: Nikolai Maas † † supplement: Source Code: https://github.com/kahypar/mt-kahypar/tree/esa2026 † † supplement: Benchmark Set & Experimental Results: https://zenodo.org/records/19630135 1 Introduction Traditional balanced hypergraph partitioning asks for a partition of the vertices of a hypergraph H=(V,E) into k disjoint blocks V_{1},\dots,V_{k}\subseteq V of roughly equal size |V_{i}|\leq(1+\varepsilon)\frac{|V|}{k} (the balance constraint) while minimizing the inter-block connectivity of the hyperedges. This is an essential task for many applications, including distributed databases [ 3 , 13 ] , VLSI circuit design [ 16 , 26 ] , and scientific simulations [ 18 ] . However, a single balance constraint is often insufficient to model application requirements. For example, multi-phase simulations balance the compute load in each phase while minimizing dependencies between processors. If phases are treated as separate partitioning problems, expensive data migrations are required in between—which can be avoided by computing a global partition with multiple distinct balance constraints [ 32 , 40 ] . Another application is distributed processing tasks that need to balance both compute and memory requirements. As a concrete example, high-quality partitions significantly improve the efficiency of distributed GNN training [ 33 , 47 ] . Multi-constraint partitioning models these use cases with d -dimensional vertex weights, thereby expressing d different kinds of balance constraints at once. Despite its practical relevance, there is not much existing work on multi-constraint partitioning. Current approaches mostly use straightforward adjustments of single-constraint partitioning algorithms and restrict local search procedures to disregard moves that violate any of the d constraints [ 5 , 7 , 29 , 39 ] . We believe that these constrained search algorithms have a severe limitation; since d balance constraints shrink the subspace of feasible solutions significantly, it becomes hard for the search to escape from local minima. Instead, we propose to use unconstrained search algorithms that allow temporary balance violations, guiding the search through regions of infeasible solutions instead of around them. We already achieved improvements for traditional partitioning via unconstrained search techniques [ 31 , 34 ] , with similar findings by other authors [ 19 , 38 ] . In this work, we will show the effectiveness of this technique in the multi-constraint setting. However, allowing balance violations means that the algorithm must restore balance afterwards, thereby alternating between feasible and infeasible solutions. This step is known as rebalancing and it is a much more difficult task in the multi-constraint setting than with a single constraint [ 29 ] . At its core, it is equivalent to a multi-dimensional job scheduling problem—but we must simultaneously consider the optimization objective. We therefore develop a rebalancing algorithm that efficiently and reliably restores partition balance. The algorithm quantifies the current imbalance with a metric based on the L_{1} -norm and greedily performs single-vertex moves that minimize the impact on quality while monotonically reducing imbalance. In addition, we use a secondary heuristic to handle cases where the greedy approach can not make progress. It moves a small set of vertices in a way that reduces block-internal imbalances between dimensions, thereby unlocking new move options. Contributions. We propose a new rebalancing algorithm for multi-constraint partitioning and integrate it into the state-of-the-art parallel hypergraph partitioner Mt-KaHyPar [ 21 ] , while also implementing multi-constraint support for all components of Mt-KaHyPar. We prove that our rebalancing always restores balance for d=2 and bounded maximum weights. Experiments on 77 hypergraph instances and 67 graph instances show that our algorithm still finds a feasible solution with over 99 % reliability for d>2 and larger weights, whereas state-of-the-art competitors are below 90 %. Our algorithm computes the best solution for 79 % of instances, achieves an 11.5 % geometric mean quality improvement compared to the next best competitor, and it is the fastest multilevel algorithm when using 16 threads. 2 Preliminaries Hypergraphs and Multi-Constraint Partitioning. For a given dimensionality d\in\mathbb{N} , let H=(V,E,c,\omega) be a weighted hypergraph with a vertex set V , a set of hyperedges E\subseteq\mathcal{P}(V) , multi-dimensional vertex weights c\colon V\mapsto\mathbb{[}0,1]^{d} , and edge weights \omega\colon E\mapsto\mathbb{R}_{>0} . We extend c and \omega to sets, i.e., c(V^{\prime}\subseteq V)\coloneqq\sum_{v\in V^{\prime}}c(v) and \omega(E^{\prime}\subseteq E)\coloneqq\sum_{e\in E^{\prime}}\omega(e) . The vertices of a hyperedge e are called the pins of e . A k -way partition \Pi=\{V_{1},\dots,V_{k}\} of a hypergraph H is a set of k disjoint blocks that partition V , i.e., V=V_{1}\cup\cdots\cup V_{k} . When considering a k -way partition \Pi , we always assume that the vertex weights are normalized such that \frac{1}{k}c(V)_{j}=1 for each dimension j\in[d] , as this simplifies notation. We say that \Pi is \varepsilon -balanced if c(V_{i})_{j}\leq 1+\varepsilon for each i\in[k] and j\in[d] . The connectivity of a hyperedge e is \lambda(e)\coloneqq|\{V_{i}\in\Pi\mid V_{i}\cap e\neq\emptyset\}| . Multi-constrained balanced hypergraph partitioning asks for an \varepsilon -balanced k -way partition of H that minimizes the connectivity (\lambda-1)(\Pi)\coloneqq\sum_{e\in E}(\lambda(e)-1)\omega(e) . We also refer to the connectivity as the solution quality of the partition. The problem of finding any balanced partition, ignoring quality, is equivalent to the vector scheduling problem with k identical machines. Vector scheduling admits an EPTAS for constant d [ 6 ] (with doubly-exponential dependence on d ), but constant factor approximations for arbitrary d are hard [ 12 ] . Multilevel Algorithms. A common approach for (hyper-)graph partitioning in practice is the multilevel scheme. Multilevel algorithms construct a sequence of increasingly smaller hypergraphs by contracting clusters or matchings ( coarsening phase ), followed by computing an initial partition on the smallest hypergraph. Afterwards, the contractions are undone in reverse order while projecting the current partition to the next larger hypergraph ( uncoarsening phase ). At each step, the partition is further improved via local search algorithms ( refinement ). While approximating balanced partitioning within a constant factor is NP-hard in