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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|