Multilevel Algorithms for Multi-Constraint Hypergraph Partitioning

Abstract

Traditional hypergraph partitioning algorithms compute a bisection a graph such that the number of hyperedges that are cut by the partitioning is minimized and each partition has an equal number of vertices. The task of minimizing the cut can be considered as the objective and the requirement that the partitions will be of the same size can be considered as the constraint. In this paper we extend the partitioning problem by incorporating an arbitrary number of balancing constraints. In our formulation, a vector of weights is assigned to each vertex, and the goal is to produce a bisection such that the partitioning satisfies a balancing constraint associated with each weight, while attempting to minimize the cut. We present new multi-constraint hypergraph partitioning algorithms that are based on the multilevel partitioning paradigm. We experimentally evaluate the effectiveness of our multi-constraint partitioners on a variety of synthetically generated problems.