KCTLIB -- Benchmark Instances

A first set of problem instances was provided in [4]. This set consists of 120 connected graphs on 10, 20, and 30 nodes with a varying number of edges (with a maximum of 268). However, these graphs are nowadays very easy to solve and do not allow to detect differences between the algorithms.

Another set of problem instances was provided in [7] for testing a TS approach, where a set of 35 4-regular graphs of different size (between 25 and 1000 nodes) is provided. Especially the smaller ones, are very easy to solve. However, the bigger ones produce differences among approaches.

The VNS approach proposed in [6] was tested on at least 10 randomly generated 20-regular graphs of 500, 1000, 1500 and 2000 nodes. They tested their VNS approach in comparison to the TS approach by by Jørnsten and Løkketangen [5].

Blum and Blesa [2] initiated a diverse set of problem instances for the most extensive computational study to date (January 2003). First, they randomly generated 10 grid graph instances of varying size, because - as discovered in earlier papers (see for example [3]) - the KCT problem seems to be especially difficult to solve in grid graph instances. Furthermore, they intended to incorporate problem instances of different sparsity and different variance of vertex degree. Regarding the existence of many graph-based combinatorial optimization problems, they decided to borrow graphs from benchmark instance sets for other problems. They chose one of the Leighton graphs from the graph coloring benchmark set available from the OR-Library [1]. This graph is characterized by a high variance in vertex degrees, which can be an indicator for the clusterdness of the graph. They also chose 5 different graphs from the Steiner tree benchmark set that are also available from the OR-Library. This is justified by the fact that the Steiner tree problem is also a problem where trees are sought in a graph. Additionally, for their comparison they chose 4 of the biggest graphs from the set of problem instances provided in [5]. For all the graphs (except the 4 last mentioned, which already had assigned edge weights) they generated edge weights uniformly at random from the interval

. For an overview on the characteristics of these benchmark instances see Table 1. The column with the heading d contains the average vertex degrees of the graphs and the column with the heading $\sigma(d)$ contains the variance of the vertex degrees.

**Table 1:** Benchmark instances by Blum and Blesa [2]
Graph	Type	$\vert V\vert$	$\vert E\vert$	d	$\sigma(d)$	Origin
bb15x15_1.gg	grid graph	225	420	3.73	0.48	randomly generated
bb15x15_2.gg	grid graph	225	420	3.73	0.48	randomly generated
bb45x5_1.gg	grid graph	225	400	3.55	0.53	randomly generated
bb45x5_2.gg	grid graph	225	400	3.55	0.53	randomly generated
bb33x33_1.gg	grid graph	1089	2112	3.87	0.33	randomly generated
bb33x33_2.gg	grid graph	1089	2112	3.87	0.33	randomly generated
bb100x10_1.gg	grid graph	1000	1890	3.78	0.42	randomly generated
bb100x10_2.gg	grid graph	1000	1890	3.78	0.42	randomly generated
bb50x50_1.gg	grid graph	2500	4900	3.92	0.27	randomly generated
bb50x50_2.gg	grid graph	2500	4900	3.92	0.27	randomly generated
g400-4-01.g	-regular graph	400	800	4.00	0.00	KCT benchmark set by Blesa and Xhafa [7]
g400-4-05.g	-regular graph	400	800	4.00	0.00	KCT benchmark set by Blesa and Xhafa [7]
g1000-4-01.g	-regular graph	1000	2000	4.00	0.00	KCT benchmark set by Blesa and Xhafa [7]
g1000-4-05.g	-regular graph	1000	2000	4.00	0.00	KCT benchmark set by Blesa and Xhafa [7]
steinc5.g	sparse graph	500	625	2.5	1.65	Steiner tree benchmarks
steind5.g	sparse graph	1000	1250	2.5	1.57	Steiner tree benchmarks
steine5.g	sparse graph	2500	3125	2.5	1.57	Steiner tree benchmarks
steinc15.g	dense graph	500	2500	10.0	3.08	Steiner tree benchmarks
steind15.g	dense graph	1000	5000	10.0	3.22	Steiner tree benchmarks
le450_15a.g	dense graph	450	8168	36.30	16.83	Graph coloring benchmarks

KCTLIB -- Benchmark Instances

Different sets of benchmark instances: