Optimal Hypergraph Partitioning

Optimal hypergraph partitioning is an interesting problem from both theoretical and practical aspects. The problem is NP-Hard and it is computationally expensive. This is why the problem is of interest only for small number of parts. Since todays’ parallel systems have thousands of processors, at first, the problem seems to be only theoretical. However, the partitioners we have today repetitively perform 2-way partitioning to partition a hypergraph into any number of parts. Hence, its practical impact is also significant. 
 

There is an algorithm in the literature to partition a hypergraph into two in an optimal way. However, the algorithm only support hypergraphs produced from matrices and it is only designed for a single objective function. Furthermore, it can take hours to produce the optimal partitioning even for small matrices. In the project, we will develop an optimal generic hypergraph- partitioning algorithm that can also utilize CPUs and GPUs. In this way, we can understand the dynamics of an optimal partitioning which may lead us a better partitioning algorithm.