Benchmark Dataset for "Exact Minimum Cuts in Hypergraphs at Scale"

Benchmark Dataset To evaluate the algorithms in the paper "Exact Minimum Cuts in Hypergraph at Scale", we use diverse hypergraphs from multiple domains. Our main test sets are the MHG dataset (488 medium-sized hypergraphs) and the LHG dataset (94 large instances, of up to 139 million vertices). The hypergraphs originate from four well-established sources spanning three application domains: the ISPD98 VLSI Circuit Benchmark Suite [1], the DAC 2012 Routability-Driven Placement Contest [2], the SuiteSparse Matrix Collection [3], and the International SAT Competition 2014 [4]. All hypergraphs are initially unweighted; we create weighted versions by assigning each vertex and each hyperedge a random weight drawn uniformly from the range [1, 100]. Additionally, we construct a dataset of (k, 2)-core hypergraphs to evaluate performance on instances where the minimum cut is strictly smaller than the trivial cut (minimum degree of hypergraph). These instances provide a benchmark for future work on this problem. We perform a (k, 2)-core decomposition on the LHG instances by iteratively removing vertices with unweighted degree less than k and all hyperedges of size less than two. For each LHG hypergraph, we retain the (k, 2)-core with the smallest k >= 2 where the minimum cut is strictly smaller than the trivial cut. This yields 44 suitable (k, 2)-core instances. As such, this repository contains: med_set: benchmark set of 488 medium sized hypergraphs. Referenced as set M_HG in our publications. HMetis format. The hypegraphs are weighted: each hyperedge is assigned a random weight drawn uniformly from the range [1, 100]. large_set: benchmark set of 94 large hypergraphs. Referenced as set L_HG in our publications. HMetis format. The hypegraphs are weighted: each hyperedge is assigned a random weight drawn uniformly from the range [1, 100]. k,2-core_benchmark: benchmark set of 44 (k,2)-core hypergraphs. HMetis format. References 1. C. J. Alpert, The ISPD98 Circuit Benchmark Suite, ISPD 1998. DOI 2. N. Viswanathan et al., The DAC 2012 Routability-Driven Placement Contest, DAC 2012. DOI 3. T. A. Davis and Y. Hu, The SuiteSparse Matrix Collection, ACM TOMS 2011. DOI 4. A. Belov et al., The SAT Competition 2014. Link