Hypergraph partitioning archive
Welcome to the Hypergraph partitioning archive. The goal of this archive is to provide a benchmark for comparing the quality of hypergraph partitioning algorithms. This archive includes partitioning results by some of the most popular hypergraph partitioning packages. The researchers are welcome to submit their own partitionings to this archive.
Problem definition
Let \(H=(V,E)\) be a hypergraph with a set of vertices \(V\) and the set of hypergredges \(E\). The goal of k-way hypergraph partitioning is to assign elements of \(V\) to mutually disjoint partitionings \(P_1, \ldots , P_k\) such that the partitionings are of mostly equal size and a metric on the cut is minimized. Here cut is a set of hyperedges that span more than one partition: \(E_{cut}\subset E\) such that for \(e\in E\) holds \(e\in E_{cut}\) if and only if \(\exists i, j\in \mathbb{N}: e\cap V_i \neq \emptyset, e\cap V_j\neq\emptyset\) such that \(i\neq j\).
The constraint that partitionings should be of about the same size is called imbalance constraint. In this benchmark it is defined as follows:
\[ imbal=\dfrac{\sum_{v\in V_{max}}w(v)}{\frac{1}{k}\sum_{v\in V}w(v)}\text{, where } V_{max}: \sum_{v\in V_{max}}w(v) = \max_i(\sum_{v\in V_{i}}w(v)) \]
Cut metric used by this benchmark is the number of cut hyperedges (i.e. \(|E_{cut}|\)). All vertices and hyperedges have unit weight. However, in general hypergraph partitioning problem allows many cut metrics, as well as weighted vertices and hyperedges.
A quick introduction into the hypergraph partitioning problem can be found here.
How to submit your algorithm
In order to have your algorithm included in this benchmark, you’ll have to download the hypergraphs from here, compute your partitioning and submit it in the following format.
File with the partitioning should be named [graph name].[number of parts].[imbalance factor], where imbalance factor is an integer (number of percents). For example, file lp_ken_07.2.10 should contain partitioning of the hypergraph lp_ken_07 into two parts with 10% imbalance factor.
Each line of file contains two integers: number of the vertex and number of the partition to which the vertex is assigned. For example, line 10 2 would indicate that the vertex 10 is assigned to the partition 2. Vertices and partitionings should be numbered from one (and not from zero).
The files should be sent to rshaydu@g.clemson.edu.