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
Two comprehensive benchmarks for this problem can be found here and here
If you use this benchmark please cite our paper


				[SSS12]
Graph	Nodes	Edges	k=2	k=4	k=8
barth5_1Ksep_50in_5Kout	32212	101805	3735	6080	7760
bcsstk30_500sep_10in_1Kout	58348	2016578	617	13473	34118
befref_fxm_2_4_air02	14109	98224	3638	28948	45856
bump2_e18_aa01_model1_crew1	56438	300801	29701	61873	85619
c-30_data_data	11023	2184	1506	5199	12086
c-60_data_cti_cs4	85830	241080	4377	7311	9960
data_and_seymourl	9167	55866	7185	14675	19299
finan512_scagr7-2c_rlfddd	139752	552020	13468	43597	61776
mod2_pgp2_slptsk	101364	389368	29625	60061	75138
msc10848_300sep_100in_1Kout	21996	1221028	737	26121	67494
sctap1-2b_and_seymourl	40174	140831	16036	26367	37045
south31_slptsk	39668	189914	24425	43724	54376
vibrobox_scagr7-2c_rlfddd	77328	435586	35450	54662	78637
p0291_seymourl_iiasa	10498	53868	6435	15779	21325
model1_crew1_cr42_south31	45101	189976	24907	47397	67028

References

[SSS12] Safro, Sanders, Schulz "Advanced coarsening schemes for graph partitioning", 2012

Questions?

Ilya Safro
Mathematics and Computer Science Division
Argonne National Laboratory
Email: safro at mcs.anl.gov