Potentially Hard Graphs for Graph Partitioning Solvers
Graph partitioning is a class of problems used in many fields of computer science and engineering. Applications include VLSI design, load balancing for parallel computations, network analysis, and optimal scheduling. The goal is to partition the vertices of a graph into a certain number of disjoint sets of approximately the same size, so that a cut metric is minimized. This problem is NP-complete even for several restricted classes of graphs, and there is no constant factor approximation algorithm for general graphs. Because of the practical importance, many heuristics of different nature have been developed to provide an approximate result in a reasonable (and, one hopes, linear) computational time. We created a benchmark with potentially hard graphs for fast graph partitioning solvers.
 For full definition of the minimum k-partitioning problem and this benchmark please see our paper. 
 Highlights of technical details: 
 These graphs have been created from the real-life graphs by adding new edges (less than 3%) 
 Experimental settings (see our paper): imbalance = 3%, k=2,4,8 
 For multilevel algorithms designers: some of these graphs are here because of the big gap between final result and that before the last refinement 
If you use this benchmark please cite our paper
  [SSS12]     [MSS14]  
Graph Nodes Edges k=2 k=4 k=8 k=2 k=4 k=8
barth5_1Ksep_50in_5Kout 32212 101805 3735 6080 7760 3735 6060 7592
                 
bcsstk30_500sep_10in_1Kout 58348 2016578 617 13473 34118 617 13473 33973
                 
befref_fxm_2_4_air02 14109 98224 3638 28948 45856 3638 28375 44462
                 
bump2_e18_aa01_model1_crew1 56438 300801 29701 61873 85619 28898 58900 85449
                 
c-30_data_data 11023 2184 1506 5199 12086 1457 4176 9281
                 
c-60_data_cti_cs4 85830 241080 4377 7311 9960 4241 7124 9642
                 
data_and_seymourl 9167 55866 7185 14675 19299 7643 14130 18662
                 
finan512_scagr7-2c_rlfddd 139752 552020 13468 43597 61776 13161 42469 60646
                 
mod2_pgp2_slptsk 101364 389368 29625 60061 75138 28349 53600 71687
                 
msc10848_300sep_100in_1Kout 21996 1221028 737 26121 67494 737 26121 66437
                 
sctap1-2b_and_seymourl 40174 140831 16036 26367 37045 15755 25510 36713
                 
south31_slptsk 39668 189914 24425 43724 54376 24617 42322 53169
                 
vibrobox_scagr7-2c_rlfddd 77328 435586 35450 54662 78637 34764 54339 75610
                 
p0291_seymourl_iiasa 10498 53868 6695 15779 21527 6706 15454 20736
                 
model1_crew1_cr42_south31 45101 189976 24907 47397 67028 25305 46621 65174
[SSS12] Safro, Sanders, Schulz "Advanced coarsening schemes for graph partitioning", 2012
[MSS14] Meyerhenke, Sanders, Schulz “Partitioning complex networks via size-constrained clustering”, 2014