clique.org

CLIQUE Benchmark Instances

Utils

• Converter: convert from benchmarks from ascii to binary format and vice versa.

DIMACS Instances

Directory

Files from Dimacs ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/ in binary format (*.clq.b).

	File	Max Clique[fn:1]
1	brock200_1	21
2	brock200_2	12
3	brock200_3	15
4	brock200_4	17
5	brock400_1	27
6	brock400_2	29
7	brock400_3	31
8	brock400_4	33
9	brock800_1	23
10	brock800_2	24
11	brock800_3	25
12	brock800_4	26
13	c-fat200-1	12
14	c-fat200-2	24
15	c-fat200-5	58
16	c-fat500-1	14
17	c-fat500-2	26
18	c-fat500-5	64
19	c-fat500-10	126
20	hamming6-2	32
21	hamming6-4	4
22	hamming8-2	128
23	hamming8-4	16
24	hamming10-2	512
25	hamming10-4	40
26	johnson8-2-4	4
27	johnson8-4-4	14
28	johnson16-2-4	8
29	johnson32-2-4	16
30	keller4	11
31	keller5	27
32	keller6	$≥$ 59
33	MANN_a9	16
34	MANN_a27	126
35	MANN_a45	345
36	MANN_a81	$≥$ 1100
37	p_hat300-1	8
38	p_hat300-2	25
39	p_hat300-3	36
40	p_hat500-1	9
41	p_hat500-2	36
42	p_hat500-3	$≥$ 50
43	p_hat700-1	11
44	p_hat700-2	$≥$ 44
45	p_hat700-3	$≥$ 62
46	p_hat1000-1	$≥$ 10
47	p_hat1000-2	$≥$ 46
48	p_hat1000-3	$≥$ 68
49	p_hat1500-1	$≥$ 12
50	p_hat1500-2	$≥$ 65
51	p_hat1500-3	$≥$ 94
52	san200_0.7_1	30
53	san200_0.7_2	18
54	san200_0.9_1	70
55	san200_0.9_2	60
56	san200_0.9_3	44
57	san400_0.5_1	13
58	san400_0.7_1	40
59	san400_0.7_2	30
60	san400_0.7_3	22
61	san400_0.9_1	100
62	san1000	15
63	sanr200_0.7	18
64	sanr200_0.9	42
65	sanr400_0.5	13
66	sanr400_0.7	21

Additional Instances

Directory

Files from Mike Trick http://mat.gsia.cmu.edu/COLOR02/clq.html. For the brock graphs below, there is an “off-by-one” error in the comments: if it claims node 26, for example, is in the clique, it is really node 27.

	File	Max Clique[fn:1]
1	brock200_2	12
2	brock200_4	17
3	brock400_2	29
4	brock400_4	33
5	brock800_2	24
6	brock800_4	26
7	C125.9	$≥$ 34
8	C250.9	$≥$ 44
9	C500.9	$≥$ 57
10	C1000.9	$≥$ 68
11	C2000.5	$≥$ 16
12	C2000.9	$≥$ 77
13	C4000.5	$≥$ 18
14	DSJC500.5	$≥$ 13
15	DSJC1000.5	$≥$ 15
16	gen200_p0.9_44	44
17	gen200_p0.9_55	55
18	gen400_p0.9_55	55
19	gen400_p0.9_65	65
20	gen400_p0.9_75	75
21	hamming8-4	16
22	hamming10-4	40
23	keller4	11
24	keller5	27
25	keller6	$≥$ 59
26	MANN_a27	126
27	MANN_a45	345
28	MANN_a81	$≥$ 1100
29	p_hat300-1	8
30	p_hat300-2	25
31	p_hat300-3	36
32	p_hat700-1	11
33	p_hat700-2	$≥$ 44
34	p_hat700-3	$≥$ 62
35	p_hat1500-1	$≥$ 12
36	p_hat1500-2	$≥$ 65
37	p_hat1500-3	$≥$ 94

Categories

Reference: http://mat.gsia.cmu.edu/contents.clique.ps, (cached)

CFat

(From Panos Pardalos [email protected]) Problems based on fault diagnosis problems. Original reference is Berman and Pelc, “Distributed Fault Diagnosis for Multiprocessor Systems,” Proceedings of the 20th Annual Symposium on Fault-Tolerant Computing, 340-346 (1990). For more instances, see the generator in graph/contributed/pardalos.

Joh

(From Panos Pardalos [email protected]) Problems based on problem in coding theory. A Johnson graph with parameters n; w; d has a node for every binary vector of length n with exactly w 1s. Two vertices are adjacent if and only if their hamming distance is at least d. A clique then represents a feasible set of vectors for a code. For more instances, see the generator in graph/contributed/pardalos.

Kel

(From Peter Shor [email protected]) Problems based on Keller’s conjecture on tilings using hypercubes. One reference is J.C. Lagarias and P.W. Shor, “Keller’s Cube-Tiling Conjecture is False in High Dimensions,” Bulletin of the AMS, 27: 279-283 (1992). For more instances (though they get very large very fast) see either the generator in graph/contributed/shor or the generator in graph/contributed/pardalos.

Ham

(From Panos Pardalos [email protected]) Another coding theory problem. A Hamming graph with parameters n and d has a node for each binary vector of length n. Two nodes are adjacent if and only if the corresponding bit vectors are hamming distance at least d apart. For more instances, see the generator in graph/contributed/pardalos. It has been noted by participants that n- -2 graphs have a maximum clique of size $2^{n-1}$. For a proof of this, see the note in graph/contributed/bourjolly/hamming.tex.

San

(From Laura Sanchis [email protected]) Instances based on her “Test Case Construction for Vertex Cover Problem,” DIMACS Workshop on Computational Support for Discrete Mathematics, March 1992 along with more recent work that will be part of a technical report to be published. The generator generates instances with known clique size.

SanR

(From Laura Sanchis [email protected]) These are random instances with sizes similar to those in San.

Bro

(From Mark Brockington [email protected]) Instances from Mark Brockington and Joe Culberson’s generator that attempts to “hide” cliques in a graph where the expected clique size is much smaller. For more instances, see their generator in graph/contributed/brockington.

PHat

(From Patrick Soriano and Michel Gendreau [email protected]) Random problems generated with the p hat generator which is a generalization of the classical uniform random graph generator. Uses 3 parameters: n, the number of nodes, and a and b, two density parameters verifying $0 ≤ a ≤ b ≤ 1$. Generates problem instances having wider node degree spread and larger clique sizes. Reference: “Solving the Maximum Clique Problem Using a Tabu Search Approach”, Annals of Operations Research 41, 385-403 (1993).

Stein

(From Carlo Mannino [email protected]) Clique formulation of the set covering formulation of the Steiner Triple Problem. Created using Mannino’s code to convert set covering problems to clique problems. Notes: MANN graphs belongs to this class.

Other Instances

BHOSLIB

Benchmarks with Hidden Optimum Solutions for Graph Problems (Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring): http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm

---

Back to benchmark instances page

[fn:1] Optimal clique size obtained from various resources including http://www.busygin.dp.ua/dimacs_clique.html and http://mat.gsia.cmu.edu/contents.clique.ps