https://doi.org/10.31449/inf.v43i2.2678 Informatica 43 (2019) 177–186 177
Benchmark Problems for Exhaustive Exact Maximum Clique Search
Algorithms
Sándor Szabó
Institute of Mathematics and Informatics, University of Pécs
Ifjuság utja 6, H-7624 Pécs, Hungary
E-mail: sszabo7@hotmail.com
Bogdán Zaválnij
Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences
Reáltanoda u. 13–15, H-1053 Budapest, Hungary
E-mail: bogdan@renyi.hu
Keywords: clique, maximal clique, maximum clique, graph coloring, random graph, Mycielski graph
Received: February 12, 2019
There are well established widely used benchmark tests to assess the performance of practical exact clique
search algorithms. In this paper a family of further benchmark problems is proposed mainly to test exhaus-
tive clique search procedures.
Povzetek: Podanih je nekaj novih standardnih problemov za testiranje algoritmov za iskanje klik.
1 Preliminaries
Let G = (V;E) be a ﬁnite simple graph. Here V is the
set of vertices of G and E is the set of edges of G. The
ﬁniteness ofG means thatG has ﬁnitely many nodes and
ﬁnitely many vertices, that is,jVj <1,jEj <1. The
simplicity ofG means thatG does not have any loop and it
does not have double edges.
LetC be a subset ofV . If two distinct nodes inC are
always adjacent inG, thenC is called a clique inG. When
C has k elements, then we talk about a k-clique. We in-
clude the casesk = 0 andk = 1 as well whenjCj = 0 and
jCj = 1, respectively. Though in these cases C does not
have two distinct elements.
A clique is maximal in G if it is not part of any larger
clique inG. In other words a clique is maximal clique of
the graphG if it cannot be extended to a larger clique by
adding a new node of the graphG. Ak-clique is a maxi-
mum clique inG ifG does not contain any (k + 1)-clique.
All the maximum cliques of a graphG have the same num-
ber of nodes. We call this well deﬁned number the clique
number ofG and we denote it by!(G).
A number of problems is referred as clique search prob-
lems [1].
Problem 1. Given a ﬁnite simple graphG. List all maxi-
mal cliques ofG without repetition.
Problem 2. Given a ﬁnite simple graphG and given a pos-
itive integerk. Decide ifG has ak-clique.
Problem 3. Given a ﬁnite simple graph G. Determine
!(G).
Problem 4. Given a ﬁnite simple graphG. List all maxi-
mum cliques ofG without repetition.
An algorithm to solve Problem 1 can be found in [2].
The algorithm is commonly known as Bron-Kerbosch al-
gorithm. Obviously, the Bron-Kerbosch algorithm can be
used to solve Problems 2, 3 and 4. A more efﬁcient algo-
rithm to solve these problems was ﬁrst given in [3]. The
algorithm is known under the name Caraghan-Pardalos al-
gorithm. The Bron-Kerbosch and Carraghan-Pardalos al-
gorithms are the classical algorithms that form the base of
many further clique search procedures. These algorithms
are presented in [14], [26], [24], [10], [9]. But this list is
not intended to be complete.
The complexity theory of the algorithm tells us that
Problem 2 is in the NP-complete complexity class. (See for
instance [6].) Consequently, Problem 3 must be NP-hard.
We color the vertices ofG such that the following con-
ditions are satisﬁed.
(1) Each vertex ofG is colored with exactly one color.
(2) Vertices of G connected by an edge receive distinct
colors.
A coloring of the nodes ofG that satisﬁes conditions (1),
(2) is called a legal coloring or well coloring of the nodes
ofG.
Suppose that the nodes ofG can be colored legally using
k colors. We may use a mapf : V !f1;:::;kg to de-
scribe a coloring of the nodes ofG. The numbers 1;:::;k
play the roles of the colors andf(v) is the color of the ver-
texv for eachv2 V . If for adjacent nodesu andv ofG
178 Informatica 43 (2019) 177–186 S. Szabo et al.
the equationf(u) =f(v) impliesu =v, then the coloring
deﬁned by the mapf is a legal coloring.
There is a number of the colors k such that the nodes
of G can be colored legally using k colors and the nodes
of G cannot be colored legally using k  1 colors. This
well deﬁned number k is called the chromatic number of
the graphG and it is denoted by  (G).
Graph coloring is a vast subject and we cannot make jus-
tice to this venerable ﬁeld. In this paper we take a very
narrow view. We are interested in only one particular ap-
plication. Note that !(G)    (G) holds for each ﬁnite
simple graphG and so coloring of the nodes can be used to
estimate the size of a maximum clique. However, the gap
between!(G) and  (G) can be arbitrarily large. J. Myciel-
ski [13] exhibited a graph M
(k)
for which !(M
(k)
) = 2
and  (M
(k)
) =k for each integerk  2.
In order to ﬁnd bounds for!(G) the following node col-
oring was proposed in [21]. Let us choose an integers  2
and consider a coloring of the nodes ofG that satisﬁes the
following conditions.
(1
0
) Each vertex ofG is colored with exactly one color.
(2
0
) If the verticesv
1
;:::;v
s
are vertices of a clique inG,
then all the verticesv
1
;:::;v
s
cannot receive the same
color.
A coloring of the nodes ofG satisfying the conditions (1
0
),
(2
0
), is called a monochrome s-clique free coloring. In
short we will talk abouts-clique free coloring. Fors = 2
the monochromes-clique free coloring of the nodes gives
back the legal coloring of the nodes. There is a well de-
ﬁned minimum numberk such that the nodes ofG have an
s-clique free coloring usingk colors. Thisk is referred to
as the thes-clique free chromatic number ofG and it is de-
noted by  (s)
(G). The inequality!(G)  (s  1)  (s)
(G)
shows thats-clique free coloring of the nodes can be used
to establish upper bound for the clique number.
A number of problems is considered in connection with
coloring the nodes of a graph customarily.
Problem 5. Given a ﬁnite simple graphG and given a pos-
itive integerk. Decide whether the nodes ofG admit a legal
coloring usingk colors.
Problem 6. Given a ﬁnite simple graph G. Determine
  (G).
It is a well known result of the complexity theory of al-
gorithms that Problem 5 belongs to the P complexity class
for k = 2 and it belongs to the NP-complete complexity
class fork  3. (See for example [15].) It follows that for
k  3 Problem 6 is NP-hard.
Problem 7. Given a ﬁnite simple graphG and two positive
integerss,k. Decide if the nodes ofG have a legals-clique
free coloring withk colors.
It was established in [23] that fork = 3,s  3 Problem
7 is NP-complete.
2 A Mycielski type result
As we have already mentioned the chromatic number can
be a poor upper estimate of the clique number. By My-
cielski’s construction there are 3-clique free graphs with
arbitrarily large chromatic number. P. Erd˝ os [5] general-
ized this result. Let us call the length of a shortest cordless
circle in a graph the girth of the graph. Clearly, the girth of
a 3-clique free graph must be at least 4. Erd˝ os has proved
that for given positive integersk andl, there is a ﬁnite sim-
ple graphG with girth(G)  l,  (G)  k. Erd˝ os’s proof
is not constructive and so it is not at all straight forward
how the resulting graphs could be used in constructing test
instances.
In this section we present another extension of Myciel-
ski’s result. We replace the legal coloring of the nodes of a
graph by a legals-clique free coloring of the nodes of the
graph. Consequently, the s-clique free chromatic number
  (s)
(G) will play the role of the chromatic number  (G).
The result is motivated by the fact that one might try
to construct clique search test instances by replacing the
Mycielski graph by the graph emerging from the proof the
generalized version.
Theorem 1. Let us choose two positive integers s and k
with s   3 and k   2
(s  1)
=(s  1). There is a ﬁnite
simple graph L
(s;k)
such that !(L
(s;k)
)   2
(s  1)
and
  (s)
(L
(s;k)
)  k.
The reader may notice that the graph L
(2;k)
is isomor-
phic to the Mycielski graphM
(k)
.
Proof. The proof will be constructive. We start with the
special case s = 3. We choose an integer k for which
k  2
(3  1)
=(3  1) = 2. LetM
(k)
be the Mycielski graph
with parameter k. Let u
1
;:::;u
n
be the nodes of M
(k)
.
We substitute the nodeu
i
ofM
(k)
by an isomorphic copy
M
(k)
i
of the Mycielski graph for eachi, 1  i  n. Let
v
i;1;
;:::;v
i;n
be the nodes of M
(k)
i
. We assume that the
nodes
v
1;1
;:::;v
1;n
;:::;v
n;1
;:::;v
n;n
are pair-wise distinct. These nodes will be the nodes of the
graphL
(3;k)
.
The edges of M
(k)
i
are going to be edges of L
(3;k)
for
each i, 1   i   n. Further, whenever the unordered
pairfu
i
;u
j
g is an edge of M
(k)
, then we add the edge
fv
i; 
;v
j; 
g toL
(3;k)
for each  ,  , 1   ;    n.
The dedicated reader will not fail to notice that the con-
struction we just presented is the so called lexicographic
product of the graphsM
(k)
andM
(k)
.
We claim that!(L
(3;k)
)  4.
In order to verify the claim we assume on the con-
trary that !(L
(3;k)
)  5. Let C be a 5-clique in L
(3;k)
.
Set V
i
= fv
i;1;
;:::;v
i;n
g. Note that the set V
i
induces
M
(k)
i
inL
(3;k)
as a subgraph ofL
(3;k)
. From the fact that
!(M
(k)
i
)  2 it follows thatC may have at most 2 nodes
inV
i
for eachi, 1  i  n. ThereforeC has nodes in some
M
(k)
i
for at least 3 distinct values ofi.
Benchmark Problems for Exhaustive Exact. . . Informatica 43 (2019) 177–186 179
Suppose that i and j are distinct numbers in the set
f1;:::;ng. A node in M
(k)
i
and a node in M
(k)
j
can be
adjacent only if the unordered pairfu
i
;u
j
g is an edge of
M
(k)
. This means thatM
(k)
contains a 3-clique. ButM
(k)
does not contain any 3-clique. This contradiction com-
pletes the veriﬁcation of the claim.
We claim that  (3)
(L
(3;k)
)  k.
In order to prove the claim let us assume on the contrary
that  (3)
(L
(3;k)
)  k  1. Set
V = V
1
[   [ V
n
= fv
1;1
;:::;v
1;n
;:::;v
n;1
;:::;v
n;n
g:
Suppose that the mapf : V !f1;:::;k  1g deﬁnes a
3-clique free coloring of the nodes ofL
(3;k)
.
The restriction of f to the set V
i
is a map g
i
: V
i
!
f1;:::;k  1g. Clearly, the mapg
i
deﬁnes a coloring of
the nodes of the graphM
(k)
i
. From the fact that  (M
(k)
i
)  k it follows that there are two distinct adjacent nodes of
M
(k)
i
such that the two nodes receive the same color c
i
.
SetU =fu
1
;:::;u
n
g. Using the colorc
i
we deﬁne a map
h : U !f1;:::;k  1g. We seth(u
i
) = c
i
for eachi,
1  i  n.
Note that the maph deﬁnes a legal coloring of the nodes
of the graphM
(k)
. The only thing which needs veriﬁcation
is that ifu
i
andu
j
are distinct adjacent nodes ofM
(k)
, then
c
i
6=c
j
.
Let us assume on the contrary thatu
i
andu
j
are distinct
adjacent nodes ofM
(k)
andc
i
= c
j
. The graphM
(k)
i
has
two distinct adjacent nodesv
i;i(1)
andv
i;i(2)
such that
f(v
i;i(1)
) =f(v
i;i(2)
) =c
i
:
Similarly, the graphM
(k)
j
has two distinct adjacent nodes
v
j;j(1)
andv
j;j(2)
such that
f(v
j;j(1)
) =f(v
j;j(2)
) =c
j
:
Note that the nodes v
i;i(1)
, v
i;i(2)
, v
j;j(1)
, v
j;j(2)
are the
nodes of a 4-clique inL
(3;k)
. This means that the coloring
deﬁned by the mapf is not a 3-clique free coloring of the
nodes of L
(3;k)
. This shows that the coloring deﬁned by
the maph is a legal coloring of the nodes ofM
(k)
.
The coloring deﬁned byh is using at mostk  1 colors.
This contradicts the fact that  (M
(k)
)  k. Thus we may
conclude that  (3)
(L
(3;k)
)  k as we claimed.
Let us turn to the special cases = 4. We choose a integer
k for whichk  2
(4  1)
=(4  1), that is,k  3. LetM
(k)
be the Mycielski graph with parameterk. Letu
1
;:::;u
n
be the nodes ofM
(k)
. We substitute the nodeu
i
ofM
(k)
by an isomorphic copyL
(3;k)
i
of the graphL
(3;k)
for each
i, 1  i  n. Letv
i;1;
;:::;v
i;m
be the nodes ofL
(3;k)
i
. We
assume that the nodes
v
1;1
;:::;v
1;m
;:::;v
n;1
;:::;v
n;m
are pair-wise distinct. These nodes will be the nodes of the
graphL
(4;k)
.
The edges ofL
(3;k)
i
are going to be edges ofL
(4;k)
for
each i, 1   i   n. Further, whenever the unordered
pairfu
i
;u
j
g is an edge of M
(k)
, then we add the edge
fv
i; 
;v
j; 
g toL
(4;k)
for each  ,  , 1   ;    m.
We claim that!(L
(4;k)
)  8.
In order to verify the claim we assume on the contrary
that !(L
(4;k)
)  9. Let C be a 9-clique in L
(4;k)
. Note
that the setV
i
=fv
i;1;
;:::;v
i;m
g inducesL
(3;k)
i
inL
(4;k)
as a subgraph ofL
(4;k)
. From the fact that!(L
(3;k)
i
)  4
it follows thatC may have at most 4 nodes inV
i
for each
i, 1  i  n. ThereforeC has nodes in someL
(3;k)
i
for at
least 3 distinct values ofi.
Suppose that i and j are distinct numbers in the set
f1;:::;ng. A node in L
(3;k)
i
and a node in L
(3;k)
j
can
be adjacent only if the unordered pairfu
i
;u
j
g is an edge
of M
(k)
. This means that M
(k)
contains a 3-clique. But
M
(k)
does not contain any 3-clique. This contradiction
completes the proof of the claim.
We claim that  (4)
(L
(4;k)
)  k.
In order to prove the claim let us assume on the contrary
that  (4)
(L
(4;k)
)  k  1. Set
V = V
1
[   [ V
n
= fv
1;1
;:::;v
1;n
;:::;v
n;1
;:::;v
n;n
g:
Suppose that the mapf : V !f1;:::;k  1g deﬁnes a
4-clique free coloring of the nodes ofL
(4;k)
.
The restriction of f to the set V
i
is a map g
i
: V
i
!
f1;:::;k  1g. Clearly, the map g
i
deﬁnes a coloring
of the nodes of the graph L
(3;k)
i
. From the fact that
  (3)
(L
(3;k)
i
)  k it follows that there is a 3-clique inL
(3;k)
i
such that the 3 nodes of the clique receive the same color
c
i
. SetU =fu
1
;:::;u
n
g. Using the colorc
i
we deﬁne a
maph :U!f1;:::;k  1g. We seth(u
i
) =c
i
for each
i, 1  i  n.
Note that the maph deﬁnes a legal coloring of the nodes
of the graphM
(k)
. The only thing which needs veriﬁcation
is that ifu
i
andu
j
are distinct adjacent nodes ofM
(k)
, then
c
i
6=c
j
.
Let us assume on the contrary thatc
i
= c
j
. The graph
L
(3;k)
i
has 3 distinct pair-wise adjacent nodesv
i;i(1)
,v
i;i(2)
,
v
i;i(3)
such that
f(v
i;i(1)
) =f(v
i;i(2)
) =f(v
i;i(2)
) =c
i
:
Similarly, the graphL
(3;k)
i
has 3 distinct pair-wise adjacent
nodesv
j;j(1)
,v
j;j(2)
,v
j;j(2)
such that
f(v
j;j(1)
) =f(v
j;j(2)
) =f(v
j;j(3)
) =c
j
:
Note that the nodes
v
i;i(1)
;v
i;i(2)
;v
i;i(3)
;v
j;j(1)
;v
j;j(2)
;v
j;j(3)
are the nodes of a 6-clique inL
(4;k)
. This means that the
coloring deﬁned by the mapf is not a 4-clique free coloring
of the nodes ofL
(4;k)
. This shows that the coloring deﬁned
by the maph is a legal coloring of the nodes ofM
(k)
.
180 Informatica 43 (2019) 177–186 S. Szabo et al.
In the coloring deﬁned by h most k  1 colors occur.
This contradicts the fact that  (M
(k)
)  k. Thus we may
draw the conclusion that  (4)
(L
(4;k)
)  k as we claimed.
Continuing in this way we can complete the proof of the
theorem. 2
3 Test problems
Problems 2 and 3 are commonly referred as k-clique and
maximum clique problems, respectively. As we have
pointed out it is a well known result of the complexity the-
ory of algorithms that the maximum clique problem is NP-
hard. Loosely speaking it can be interpreted such that the
maximum clique problem is computationally demanding.
As at this moment there are no readily available mathe-
matical tools to evaluate the performance of practical clique
search algorithms, the standard procedure is to carry out
numerical experiments on a battery of well selected bench-
mark tests.
The most widely used test instances are the Erd˝ os–Rényi
random graphs, graphs from the the second DIMACS chal-
lenge
1
[8], combinatorial problems of monotonic matrices
[25, 22], and hard coding problems of Deletion-Correcting
Codes
2
[20].
Evaluating the performances of various clique search al-
gorithms is a delicate matter. On one hand one would
like to reach some practically relevant conclusion about the
competing algorithms. On the other hand this conclusion is
based on a ﬁnite list of instances.
One has to be ever cautious not to draw overly sweep-
ing conclusions from these inherently limited nature ex-
periments. (We intended to contrast this approach to the
asymptotic techniques which are intimately tied to inﬁnity.)
The situation is of course not completely pessimistic. Af-
ter all, these benchmarks were successful at shedding light
on the practicality of many of the latest clique search pro-
cedures. However, we should strive for enhancing the test
procedures. The main purpose of this paper is to propose
new benchmark instances.
There are occasions when we are trying to locate a large
clique in a given graph such that the clique is not necessar-
ily optimal. This approach is referred as non-exact method
to contrast it to the exhaustive search. For instance con-
structing a large time table in this way can be practically
important and useful even without a certiﬁcate of optimal-
ity.
The benchmark tests are of course relevant in connec-
tion with non-exact procedures too. In order to avoid any
unnecessary confusion we would like emphasize that in this
paper we are focusing solely on the exact clique search
methods.
Let n be a positive integer and let p be a real number
such that 0  p  1. An Erd˝ os-Rényi random graph with
1
ftp://dimacs.rutgers.edu/pub/challenge/
2
http://neilsloane.com/doc/graphs.html
parametersn,p is a graphG with vertices 1; 2;:::;n. The
probability that the unordered pairfx;yg is an edge ofG
is equal top for eachx,y, 1  x<y  n. The events that
the distinct pairs
fx
i(1)
;y
i(1)
g;:::;fx
i(s)
;y
i(s)
g
are edges ofG are independent of each other for each sub-
setfi(1);:::;i(s)g off1; 2;:::;ng, wheres  2.
In a more formal way the Erd˝ os-Rényi random graph of
parametersn,p is a random variable whose values are all
the simple graphs withn vertices. The probability distribu-
tion over these graphs is speciﬁed in the manner we have
described above. In this paper we can work safely in a
more intuitive level. We start with a complete graph onn
vertices and we decide the fate of each edge by ﬂipping a
biased coin.
In the casep = 0 we end up with a graph consisting of
n isolated nodes. In the casep = 1 we end up with a com-
plete graph onn nodes. (Paper [4] is the basic reference on
Erd˝ os-Rényi random graph.)
Let l, m be positive integers. Let H
i
= (V
i
;E
i
) be
a graph consisting of l isolated nodes. This means that
jV
i
j = l and E
i
=; for each i, 1  i  m. Let V
i
=
fv
i;1
;:::;v
i;l
g. We construct a new graph G = (V;E).
We setV = V
1
[   [ V
m
. The nodesv
i;r
,v
j;s
are con-
nected by an edge inG wheneveri6= j. We may say that
the graphG is isomorphic to the lexicographic product of
the graphsH andK
m
, whereH consists ofl isolated nodes
andK
m
is the complete graph onm nodes. (For further de-
tails of graph products see [7].)
Clearly,V
i
is an independent set inG for eachi, 1  i  m. The subgraph induced by V
i
[V
j
in G is a complete
bipartite graph for eachi,j, 1  i < j  m. Obviously,
  (G) = m and !(G) = m hold. In fact G contains l
m
distinctm-cliques.
At this stage we choose a real numberp such that 0  p  1. At each edge ofG we ﬂip a biased coin. The edge
stays with probabilityp. We call this step randomizingG.
The resulting random graphG
0
belongs to the parametersl,
m,p. Thel = 1 particular case corresponds to the Erd˝ os-
Rényi random graph of parametersm,p.
It is clear that   (G
0
)  m and !(G
0
)  m. In order
to guarantee that !(G
0
) = n holds we will plant an m-
clique intoG
0
. One can achieve this by pickingx
i
2V
i
for
eachi, 1  i  m and connect each distinct pairs among
x
1
:::;x
m
by an edge inG
0
.
Benchmark tests based on these random graphs are col-
lected in the BHOSLIB library.
3
(The acronym BHOSLIB
stands for Benchmarks with Hidden Optimum Solutions
Library.)
After all these preparations we are ready to describe the
graphs we would like to propose for testing clique search
algorithms. Let k, m be positive integers. Let M
(k)
i
=
(V
i
;E
i
) be the Mycielski graph of parameterk. LetV
i
=
3
http://www.nlsde.buaa.edu.cn/~kexu/
benchmarks/graph-benchmarks.htm
Benchmark Problems for Exhaustive Exact. . . Informatica 43 (2019) 177–186 181
fv
i;1
;:::;v
i;n
g for each i, 1  i  m. We construct a
new graphG = (V;E). We setV = V
1
[   [ V
m
. Let
v
i;r
;v
i;s
2 V
i
. If the unordered pairfv
i;r
;v
i;s
g is an edge
ofM
(k)
i
, then we add this pair as an edge toG. These edges
will be the blue edges ofG. In other words the subgraph
induced byV
i
inG is isomorphic toM
(k)
i
for eachi, 1  i  m.
Pick v
i;r
2 V
i
, v
j;s
2 V
j
. We connect the nodes v
i;r
,
v
j;s
by an edge inG wheneveri6=j. These edges will be
the red edges ofG.
Note that the graphG is isomorphic to the lexicographic
product of the graphs M
(k)
and K
m
, where M
(k)
is the
Mycielski graph of parameter k and K
m
is the complete
graph on m nodes. One can verify that   (G) = (k)(m)
and!(G) = (2)(m).
We choose a real number p such that 0  p  1. We
randomize the red edges of G. We ﬂip a biased coin and
keep each red edge with probabilityp. The resulted random
graph is denoted byG
0
. It is obvious that  (G
0
)  (k)(m)
and!(G
0
)  (2)(m). By planting a (2m)-clique intoG
0
we can guarantee that!(G
0
) = (2)(m). We pickx
i
;y
i
2
V
i
such that the unordered pairfx
i
;y
i
g is an edge inG
0
for
each i, 1  i  m. Finally, we construct a (2m)-clique
whose nodes arex
1
;y
1
;:::;x
m
;y
m
.
Figure 1: The adjacency matrices of the Mycielski graph
M
(4)
and the random graphG
0
.
4 Numerical experiments
The proposed new collection of test graphs can be found
on the site clique.ttk.pte.hu/evil. The source
code of the program that generates the adjacency matrices
of these graphs are also available on this site.
As an illustration Figure 1 exhibits the adjacency ma-
trix of the Mycielski graph of parameter 4. Further it de-
picts the adjacency matrix of the randomized version of the
lexicographic product ofM
(4)
andK
4
, whereM
(4)
is the
Mycielsky graph of parameter 4 and K
4
is the complete
graph on 4 vertices. As the number of vertices ofM
(4)
and
K
4
are equal to 11 and 4, respectively, the product graph
has 44 nodes. The probability we used for randomizing is
p = 0:98.
In the constructions we systematically replaced the My-
cielski graphM
(k)
by the graphL
(s;k)
that appeared in the
proof of Theorem 1 for small values of the parameters s
and k. The graph M
(4)
has 11 nodes. Its chromatic and
clique numbers are 4 and 2, respectively. There is a graph
with the same chromatic and clique numbers the so-called
Chvatal graph. The Chvatal graph has 12 vertices but more
symmetric than M
(4)
. We replaced M
(4)
by the Chvatal
graph systematically when we constructed test instances.
Note that other graphs also can be used instead of these
two examples. Presumably the kind of graphs where the
clique number is far from the chromatic number. As the
last step we randomly permuted the nodes of the graphs.
We carried out a large scale numerical experiment to
check the proposed EVIL benchmark problems. We used
55 test graphs. We took 35 BHOSLIB graphs and 20 EVIL
graphs. The experiment involved 7 programs implement-
ing 12 different algorithms and so we are able to compare
the running times of 660 clique searches. The processor of
the computer we used was a 2.3 GHz, Xeon E5-2670v3.
The 12 clique search algorithms we used are the follow-
ing.
(1) Östergård
4
[14] (cliquer),
(2) Li
5
[11], [12] (M-cql 10, M-cql 13-1 and M-cql 13-2).
(3) Konc
6
[9] (mcqd and mcqd-dyn)
(4) Prosser
7
(who implemented Tomita’s algorithm [24])
(MCR)
(5) San Segundo
8
[16], [17], [18], [19] (BBMC, BBMC-
R, BBMC-L and BBMC-X).
There are three ways to use the 2013 version of C.-M. Li
program. A switch can be set to either “1” or “2” to select
between two built in orderings of the nodes of the graph. In
case no value of the switch is speciﬁed the program chooses
between the “1” and “2” possibilities. During our test we
explicitly used the switch “1” and “2” ( M-cql 13-1 and
M-cql 13-2).
The above programs are high quality state of art pro-
grams. It seemed reasonable to enter an unsophisticated
program to the competion. The program can be found on
the same site as the EVIL instances and goes under the
name antiB. The brief description of the program is the fol-
lowing.
4
http://users.aalto.fi/~pat/cliquer.html
5
http://home.mis.u-picardie.fr/~cli/
EnglishPage.html
6
http://www.sicmm.org/konc/maxclique/
7
http://www.dcs.gla.ac.uk/~pat/maxClique/
distribution/
8
https://www.biicode.com/pablodev/examples_
clique
182 Informatica 43 (2019) 177–186 S. Szabo et al.
1) Using the simplest sequential greedy algorithm color
legally the nodes of the graph and save the colors of
the nodes.
2) Setk to be the number of colors of the legal coloring
we have located.
3) Carry out ak-clique search.
4) If ak-clique is found, then it is a maximum clique of
the graph. Otherwise reduce the value ofk and go to
step 3.
Thek-clique search is based on the Carraghan-Pardalos
algorithm, where we utilized original coloring of the nodes.
The ordering of the nodes was done by the size of the color
classes and the node degrees.
The results of the experiment are summarized in Table
1.
The running times on the BHOSLIB instances are shown
in the ﬁrst part of the table. The evaluation of the results
shows that the 2013 version of Li’s program with the “2”
switch is on is performing unexpectedly well. The running
times of he cliquer and the antiB programs are outliers as
well.
Our possible explanation is that although the BHOSLIB
tests are excellent for heuristic big clique search programs
however they are not so good for evaluating exact maxi-
mum clique search algorithms. One problem with these
instances is that the nodes of these graphs are not randomly
permuted. This means that a simple sequential greedy col-
oring will ﬁnd the chromatic number at once, as the color
classes are laid out consecutively. This can be remedied
easily. An other possible problem is that most maximum
clique search programs use coloring as an auxiliary algo-
rithm. For these graphs the chromatic number is equal to
the clique size leaving a zero optimality or duality gap. So
specially designed programs, as the presented antiB, are
able to take advantage of this.
The running times for the EVIL benchmark problems are
shown in the second part of the table. Here the running
times are more evenly distributed.
One particular result was that there is a test graph with
220 nodes – 20 copies of theM
(4)
graph,p = 98% edge
probability – whose clique number could be determined by
only one program in slightly less than 12 hours. We sup-
pose that this problem is the hardest one of such small size.
For certain graph the running times of the cliquer pro-
gram are again outliers. These short running times could
be explained by the fact that the cliquer does not rely on
legal coloring of the nodes as do the other programs. Af-
ter all, we constructed the tests to widen the gap between
the chromatic number and the clique number. On the same
graphs but with non-permuted nodes the cliquer runs even
faster. This again points out the importance of randomly
permuting the nodes of the test graphs. The antiB program
ﬁnishes at the last place as one would expect.
We would like to close this section with a few remarks on
why the reader should appreciate the proposed benchmark
problems. Although it seems that there is a large number
of benchmark problems for maximum clique search algo-
rithms the plain fact is that there are not enough of them.
Many of these test problems are too easy for the modern
solvers as the sizes of these problems are small. On the
other hand there are test instances that are overly hard for
the contemporary clique solvers. The proposed EVIL test
graphs are forming parameterized families. The parameters
can be tuned to produce benchmark problems in various de-
grees of difﬁculty.
5 A historical thread
The graphs that are used for benchmarking clique search al-
gorithms are coming from various walks of discrete math-
ematics and its applications. In this section we will follow
a particular thread in order to shed some light on the forces
and demands that shaped the evolution of certain bench-
mark problems.
By the lack of other possibilities the performance of
clique search algorithms are commonly evaluated by car-
rying out large scale numerical experiments. Historically
the ﬁrst clique search procedures were tested almost exclu-
sively on random graphs. The Erd˝ os-Rényi random graphs
are readily available with any speciﬁed number of nodes
and with any speciﬁed edge densities. These random graph
are popular and useful test instances.
Since the clique size and the chromatic number of a ran-
dom graph is unknown at the moment of generating them,
these test graphs are not the ideal choices to testk-clique
search algorithms or for algorithms to list all maximum
cliques.
Let G = (V;E) be a complete k-partite graph with
n nodes. For the sake of deﬁniteness we assume that V
is partitioned into the sets V
1
;:::;V
k
such thatjV
1
j =
    = jV
k
j = s. Consequently n = ks. Suppose
V
i
= fv
i;1
;:::;v
i;s
g. If i 6= j, then we connect each
node v
i; 
in V
i
with each node v
j; 
in V
j
. Thus G has
(1=2)k(k  1)s
2
edges, that is,jEj = (1=2)k(k  1)s
2
.
The nodes of G can be legally colored using k colors.
The setsV
1
;:::;V
k
can play the roles of the color classes.
It is clear that!(G) = k. Picking exactly one node from
eachV
i
we get mutually adjacent nodes that form the nodes
of a k-clique in G. The number of the maximum cliques
inG is equal tos
k
. These benchmark problems are good
candidates to test clique search algorithms that list all max-
imum cliques. These benchmark problems painfully lack
the unpredictability of random graphs.
Therefore when we connect the nodes of the setsV
i
and
V
j
we should do it in a randomized manner. Each of the
s
2
edges of the bipartite graph induced by the setV
i
[V
j
in G is chosen with a ﬁxed probability p
i;j
. The clique
size of the resulting random graph may decrease and the
chromatic number of the resulting random graph may in-
crease. By planting a randomly chosen k-clique into the
graph we guarantee that the clique and the chromatic num-
ber are equal tok.
Benchmark Problems for Exhaustive Exact. . . Informatica 43 (2019) 177–186 183
These graphs are the BHOSLIB instances. The develop-
ment of these graphs greatly enhanced the utility of random
graphs in testing clique search algorithms.
A graph whose chromatic number is equal to its clique
number is by no means is a typical graph. This is why we
propose a family of test graphs that have all the desired
properties of the BHOSLIB graph and in the same time the
gap between the clique and chromatic numbers can be set
in a more ﬂexible manner.
Let G = (V;E) be the graph we intend to construct.
Let us start with a graphM = (W;F ) such that!(M) =
r,   (M) = s are known. SupposeW =fw
1
;:::;w
m
g.
We considerk isomorphic copiesM
1
;:::;M
k
ofM. Let
M
i
= (W
i
;F
i
), whereW
i
=fw
i;1
;:::;w
i;m
g.
In order to construct the graph G we set V = W
1
[
   [ W
k
. Here we assume that the sets W
1
;:::;W
k
are
pair-wise disjoint. ConsequentlyG haskm nodes. Let us
pick two distinct W
i
and W
j
. We connect w
i 
and w
j; 
for each  ,  , 1   ;    m. The resulting graphG has
km nodes and kjFj + (1=2)k(k  1)m
2
edges. Clearly,
!(G) =k!(M) =kr and  (G) =k  (M) =ks.
As a next step we randomizeG. Namely, we pick each
of them
2
edges running betweenW
i
andW
j
with a ﬁxed
probability p
i;j
. (In many cases we choose all p
i;j
to be
equal.) Because we drop edges from the graphG, the quan-
tities!(G),  (G) may change. By planting a random (kr)-
clique we may restore the original !(G). The chromatic
number of the new random graph may decrease. If the
probabilityp
i;j
is close to one then most likely the decrease
in the chromatic number is small. When we choose a graph
M for which!(M) is much smaller than  (M), then for
the resulted random graph the gap between the clique and
chromatic numbers most likely does not disappear.
The resulting random graphs are the test instances pro-
posed in this paper.
The Szemerédi regularity lemma teaches us that a large
dense graph can be transformed into a form which is very
much similar to our proposed graph. So the proposed graph
in a sense is not overly artiﬁcial.
6 Reducing the number of nodes
We use the graphsL
(s;k)
deﬁned in the proof of Theorem
1 to construct benchmark instances. It is imperative to con-
struct hard benchmark instances with as few nodes as possi-
ble. In this section we will show that with a little extra care
we can reduce the number of the nodes and still get a graph
which has the required properties of the graphsL
(s;k)
. For
the sake of simplicity we will restrict our attention to the
special cases = 3.
LetG = (V;E) be a ﬁnite simple graph. A subsetC of
V is called an edge covering set ofG if each edge ofG has
at least one end point inC.
Let   (k) be the number of the nodes of the Mycielski
graphM
(k)
of parameterk. The Mycielski graphM
(3)
is
a circle consisting of 5 nodes and 5 edges. Thus   (3) =
5. The Mycielski graph M
(k+1)
is constructed from the
Mycielski graphM
(k)
in the following way.
SupposeU =fu
1
;:::;u
n
g is the set of nodes ofM
(k)
.
Here of course n =   (k). In order to construct M
(k+1)
from M
(k)
we add new nodes v
1
;:::;v
n
to the existing
nodesu
1
;:::;u
n
. We setV =fv
1
;:::;v
n
g. We assume
that the nodesu
1
;:::;u
n
andv
1
;:::;v
n
are pair-wise dis-
tinct. In other words we assume thatU\V =;. We draw
an edge between the nodev
i
and each neighbor of the node
u
i
for eachi, 1  i  n. Finally we add a new nodew to
the set of nodesU[V and draw an edge between the node
w andv
i
for eachi, 1  i  n.
Note that the equation  (k + 1) = 2  (k) + 1 holds and
using  (3) = 5 one can compute the number of nodes of
the Mycielski graphM
(k)
.
Lemma 1. The Mycielski graphM
(k)
has an edge cover-
ing set of size  (k  1) + 1 for eachk  3.
Proof. Fork = 3 the Mycielski graph is a circle consisting
of 5 vetices and 5 edges. Two adjacent nodes x, y and a
node z that is not adjacent to any of x, y form an edge
covering set inM
(3)
. This proves the lemma in the special
casek = 3.
For the remaining part of the proof we may assume that
k   4. We proceed by an induction on k. The My-
cielski graph M
(k)
has some nodes u
1
;:::;u
n
such that
n =  (k  1) and the subsetU =fu
1
;:::;u
n
g induces a
subgraph that is isomorphic toM
(k  1)
.
The Mycielski graph M
(k)
has some nodes v
1
;:::;v
n
such thatv
i
is adjacent to each neighbor ofu
i
for eachi,
1  i  n. Finally,M
(k)
has a nodew which is adjacent
tov
i
for eachi, 1  i  n.
The setC = U[fwg is an edge covering set inM
(k)
.
This completes the proof of the lemma. 2
We do not claim that this edge covering set has the smallest
possible number of nodes.
Lemma 2. For each integerk  3 there is a graphN
(k)
such that it has [  (k  1) + 1]  (k) +   (k  1) nodes
!(N
(k)
)  4 and  (3)
(N
(k)
)  k.
Proof. We start the construction ofN
(k)
with the Mycielski
graphM
(k)
. We assume thatU =fu
1
;:::;u
n
g is the set
of nodes of M
(k)
. By Lemma 1, the graph M
(k)
has an
edge covering set C, where n =   (k) andjCj =   (k  1) + 1.
We will assign a subgraphL
i
to the nodeu
i
of the graph
M
(k)
for eachi, 1  i  n. The graphL
i
is either a graph
consisting of one single node v
i;1
or L
i
is an isomorphic
copy of the Mycielski graphM
(k)
. In this second case the
set of nodes ofL
i
is equal toV
i
=fv
i;1
;:::;v
i;r
g, where
r =  (k).
If u
i
62 C, then to the node u
i
we assign the graph L
i
which consists of a single node. Ifu
i
2C, then to the node
u
i
we assign the graphL
i
which has  (k) nodes.
Let us suppose that the unordered pairfu
i
;u
j
g is an
edge of the graphM
(k)
. We draw edges between each node
184 Informatica 43 (2019) 177–186 S. Szabo et al.
ofL
i
and each node ofL
j
. The result of repeating this pro-
cedure for each edges of the graphM
(k)
will be the graph
N
(k)
. Clearly,N
(k)
has
[  (k  1) + 1]  (k) +  (k)    (k  1)  1 =
[  (k  1) + 1]  (k) + 2  (k  1) + 1    (k  1)  1 =
[  (k  1) + 1]  (k) +  (k  1)
nodes. It remains to show that !(N
(k)
)   4 and
  (3)
(N
(k)
)  k.
In order to prove that !(N
(k)
)  4 we assume on the
contrary that!(N
(k)
)  5. Let   be a 5-clique inN
(k)
.
Note that
!(L
i
) =
  1; if jV
i
j = 1;
2; if jV
i
j =  (k):
The clique   may contain at most one node from L
i
for
whichjV
i
j = 1. The clique   may contain at most two
nodes from L
i
whenjV
i
j =   (k). It follows that there
must be at least three distinct values of i for which the
graphL
i
contains a node from the 5-clique   . This gives
at least three distinct values of i for which the nodes u
i
pair-wise adjacent. But M
(k)
does not have any 3-clique
as!(M
(k)
)  2.
In order to prove that  (3)
(N
(k)
)  k we assume on the
contrary that  (3)
(N
(k)
)  k  1. LetV =V
1
[   [ V
n
be
the set of nodes ofN
(k)
and letf :V !f1;:::;k  1g be a
map that describes the monochrome 3-clique free coloring
of the nodes ofN
(k)
.
Consider a subgraph L
i
of N
(k)
. Let g
i
be the re-
striction of f to V
i
= fv
i;1
;:::;v
i;r
g. Plainly, the map
g
i
:V
i
!f1;:::;k  1g describes a coloring of the nodes
of the graph L
i
. Using the facts that L
i
is isomorphic to
M
(k)
and  (M
(k)
)  k we can draw the conclusion that
there must be two distinct adjacent nodes ofM
(k)
that re-
ceive the same color.
Remember thatU =fu
1
;:::;u
n
g is the set of nodes of
the Mycielski graph M
(k)
we used in the construction of
N
(k)
. We deﬁne a maph :U!f1;:::;k  1g.
If the subgraphL
i
ofN
(k)
has only one node, then we
seth(u
i
) to bef(v
i;1
). In plain English we assign the color
of the only node of the graphL
i
to the nodeu
i
of the graph
M
(k)
.
If the subgraphL
i
ofN
(k)
has  (k) nodes, then there are
two distinct adjacent nodes of L
i
, say v
i;i(1)
, v
i;i(2)
such
thatf(v
i;i(1)
) =f(v
i;i(2)
). In this case we seth(u
i
) to be
f(v
i;i(1)
). In simple English assign the common color of
the adjacent nodesv
i;i(1)
,v
i;i(2)
ofN
(k)
to the nodeu
i
of
M
(k)
.
We claim that the maph :U!f1;:::;k  1g describes
a legal coloring of the nodes ofM
(k)
. The only thing we
should check is that ifu
i
,u
j
are distinct adjacent nodes of
M
(k)
, thenh(u
i
)6=h(u
j
) must hold.
Let us start with the case whenu
i
62 C, u
j
62 C. The
assumption thatu
i
,u
j
are distinct adjacent nodes ofM
(k)
contradicts the fact thatC is an edge covering set inM
(k)
.
Therefore this case cannot occur.
Ifu
i
2 C,u
j
2 C, then the subgraphsL
i
,L
j
ofN
(k)
both have   (k) nodes. There are distinct adjacent nodes
v
i;i(1)
, v
i;i(2)
in L
i
such that f(v
i;i(1)
) = f(v
i;i(2)
) =
h(u
i
). Similarly, there are distinct adjacent nodesv
j;j(1)
,
v
j;j(2)
in L
j
such that f(v
j;j(1)
) = f(v
j;j(2)
) = h(u
j
).
Hereh(u
i
)6= h(u
j
) must hold since otherwise we have a
4-clique inN
(k)
whose nodes receive the same color. This
cannot happen as the map f : V !f1;:::;k  1g de-
scribes a monochrome 3-clique free coloring of the nodes
ofN
(k)
.
If u
i
62 C, u
j
2 C, then the subgraph L
i
of N
(k)
has only one node and the subgraph L
j
of N
(k)
has
  (k) nodes. Now f(v
i;1
) = h(u
i
). There are dis-
tinct adjacent nodes v
j;j(1)
, v
j;j(2)
in L
j
such that
f(v
j;j(1)
) =f(v
j;j(2)
) =h(u
j
). This timeh(u
i
)6=h(u
j
)
must hold since otherwise we have a 3-clique in N
(k)
whose nodes receive the same color. This cannot happen as
the mapf :V !f1;:::;k  1g describes a monochrome
3-clique free coloring of the nodes ofN
(k)
. 2
Acknowledgments
This research was supported by National Research, Devel-
opment and Innovation Ofﬁce – NKFIH Fund No. SNN-
117879.
References
[1] I. M. Bomze, M. Budinich, P. M. Pardalos, M. Pelillo
(1999) The Maximum Clique Problem, Handbook
of Combinatorial Optimization V ol. 4, Kluwer Aca-
demic Publisher.https://doi.org/10.1007/
978-1-4757-3023-4_1
[2] C. Bron and J. Kerbosch (1973) Finding all
cliques of an undirected graph, Communications
of ACM 16, 575–577. https://doi.org/10.
1145/362342.362367
[3] R. Carraghan, P. M. Pardalos (1990) An exact al-
gorithm for the maximum clique problem, Opera-
tion Research Letters 9, 375–382. https://doi.
org/10.1016/0167-6377(90)90057-C
[4] P. Erd˝ os, A. Rényi (1960) On the evolution of random
graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5,
17–61.
[5] P. Erd˝ os (1959), Graph theory and probability, Canad.
J. Math. 11, 34–38.
[6] M. R. Garey and D. S. Johnson (2003), Computers
and Intractability: A Guide to the Theory of NP-
completeness, Freeman, New York.
[7] R. Hammack, W. Imrich, S. Klavžar (2011) Hand-
book of Product Graphs, CRC Press, Boca Raton, FL.
Benchmark Problems for Exhaustive Exact. . . Informatica 43 (2019) 177–186 185
[8] J. Hasselberg, P. M. Pardalos, and G. Vairak-
tarakis (1993) Test case generators and com-
putational results for the maximum clique
problem, Journal of Global Optimization 3 ,
463–482. http://www.springerlink.
com/content/p2m65n57u657605n
https://doi.org/10.1007/bf01096415
[9] J. Konc and D. Janežiˇ c (2007) An improved branch
and bound algorithm for the maximum clique prob-
lem, MATCH Communications in Mathematical and
Computer Chemistry 58, 569–590.
[10] D. Kumlander (2005) Some Practical Algorithms to
Solve the Maximum Clique problem PhD. Thesis,
Tallin University of Technology.
[11] C.-M. Li, Z. Quan (2010) An efﬁcient branch-and-
bound algorithm based on MaxSAT for the maximum
clique problem, Proceedings of the Twenty-Fourth
AAAI Conference on Artiﬁcial Intelligence. (AAAI-
10), pp. 128–133.
[12] C.-M. Li, Z. Fang, K. Xu (2013) Combining MaxSAT
reasoning and incremental upper bound for the max-
imum clique problem, Proceedings of the 2013 IEEE
25th International Conference on Tools with Artiﬁcial
Intelligence. (ICTAI2013), pp. 939–946.https://
doi.org/10.1109/ictai.2013.143
[13] J. Mycielski (1955) Sur le coloriage des graphes, Col-
loq. Math. 3, 161–162.
[14] P. R. J. Östergård (2002) A fast algorithm for the
maximum clique problem, Discrete Applied Math-
ematics 120, 197–207. https://doi.org/10.
1016/S0166-218X(01)00290-6
[15] C. H. Papadimitriou (1994) Computational Complex-
ity, Addison-Wesley Publishing Company, Inc.
[16] P. San Segundo, D. Rodriguez-Losada, A. Jimenez
(2011) An exact bit-parallel algorithm for the max-
imum clique problem, Computers & Operations
Research. 38, 571–581. https://doi.org/10.
1016/j.cor.2010.07.019
[17] P. San Segundo, F. Matia, D. Rodriguez-Losada,
M. Hernando (2013) An improved bit parallel ex-
act maximum clique algorithm, Optimization Let-
ters. 7, 467–479.https://doi.org/10.1007/
s11590-011-0431-y
[18] P. San Segundo, C. Tapia (2014) Relaxed approx-
imate coloring in exact maximum clique search,
Computers & Operations Research. 44, 185–192.
https://doi.org/10.1016/j.cor.2013.
10.018
[19] P. San Segundo, A. Nikolaev, M. Batsyn (2015)
Infra-chromatic bound for exact maximum clique
search, Computers & Operations Research. 64,
293–303. https://doi.org/10.1016/j.
cor.2015.06.009
[20] N. J. A. Sloane, Challenge Problems: Indepen-
dent Sets in Graphs.http://neilsloane.com/
doc/graphs.html
[21] S. Szabó (2011) Parallel algorithms for ﬁnding
cliques in a graph, Journal of Physics: Conference Se-
ries 268 012030 https://doi.org/10.1088/
1742-6596/268/1/012030
[22] S. Szabó (2013) Monotonic matrices and clique
search in graphs, Annales Univ. Sci. Budapest., Sect.
Computatorica 41, 307–322.
[23] S. Szabó and B. Zaválnij (2012) Greedy algorithms
for triangle free coloring, AKCE International Jour-
nal of Graphs and Combinatorics 9 No. 2, 169–186.
[24] E. Tomita and T. Seki (2003) An efﬁcient branch-and-
bound algorithm for ﬁnding a maximum clique, Lec-
ture Notes in Computer Science 2731, 278–289.
[25] E. W. Weisstein, Monotonic Matrix, In: MathWorld–
A Wolfram Web Resource. http://mathworld.
wolfram.com/MonotonicMatrix.html
[26] D. R. Wood (1997) An algorithm for ﬁnding a
maximum clique in a graph, Oper. Res. Lett.
21, 211–217. https://doi.org/10.1016/
S0167-6377(97)00054-0
186 Informatica 43 (2019) 177–186 S. Szabo et al.
antiB BBMC BBMC BBMC BBMC M-clq M-clq M-clq mcqd mcqd MCR cliquer
name jVj % !(G) -R -L -X 10 13-1 13-2 -dyn
frb30-15-1.clq 450 82 30 0 1611 1645 1694 1613 575 629 0 2735 2541 3673 21
frb30-15-2.clq 450 82 30 0 1010 1094 1191 1047 921 990 0 3329 4155 905 43
frb30-15-3.clq 450 82 30 0 602 581 623 556 432 429 0 1305 2767 300 194
frb30-15-4.clq 450 82 30 0 1855 1768 1901 1676 1154 617 0 5763 4996 2698 2
frb30-15-5.clq 450 82 30 0 1273 1213 1437 1154 726 1110 0 1997 4536 1355 0
frb35-17-1.clq 595 84 35 1 – – – – – – 1 – – 34983 18
frb35-17-2.clq 595 84 35 1 – – – – – – 1 – – – 104
frb35-17-3.clq 595 84 35 2 – – – – – – 0 – – 22607 14493
frb35-17-4.clq 595 84 35 1 – – – – 27231 42219 0 – – 5249 7923
frb35-17-5.clq 595 84 35 5 – – – – – – 0 – – – 181
frb40-19-1.clq 760 86 40 0 – – – – – – 1 – – 11589 –
frb40-19-2.clq 760 86 40 1 – – – – – – 0 – – – –
frb40-19-3.clq 760 86 40 8 – – – – – – 0 – – – 353
frb40-19-4.clq 760 86 40 38 – – – – – – 7 – – – 2296
frb40-19-5.clq 760 86 40 10 – – – – – – 5 – – – 78
frb45-21-1.clq 945 87 45 0 – – – – – – 119 – – – –
frb45-21-2.clq 945 87 45 118 – – – – – – 72 – – – –
frb45-21-3.clq 945 87 45 122 – – – – – – 44 – – – –
frb45-21-4.clq 945 87 45 218 – – – – – – 36 – – – –
frb45-21-5.clq 945 87 45 475 – – – – – – 203 – – – –
frb50-23-1.clq 1150 88 50 16385 – – – – – – 764 – – – –
frb50-23-2.clq 1150 88 50 10145 – – – – – – 363 – – – –
frb50-23-3.clq 1150 88 50 12585 – – – – – – 7938 – – – –
frb50-23-4.clq 1150 88 50 501 – – – – – – 17 – – – 2754
frb50-23-5.clq 1150 88 50 18256 – – – – – – 221 – – – –
frb53-24-1.clq 1272 88 53 73 – – – – – – 4771 – – – –
frb53-24-2.clq 1272 88 53 – – – – – – – 190 – – – –
frb53-24-3.clq 1272 88 53 2910 – – – – – – 2091 – – – –
frb53-24-4.clq 1272 88 53 29815 – – – – – – 4022 – – – –
frb53-24-5.clq 1272 88 53 27671 – – – – – – 1071 – – – –
frb59-26-1.clq 1534 89 59 – – – – – – – – – – – –
frb59-26-2.clq 1534 89 59 42408 – – – – – – – – – – –
frb59-26-3.clq 1534 89 59 – – – – – – – – – – – –
frb59-26-4.clq 1534 89 59 – – – – – – – – – – – –
frb59-26-5.clq 1534 89 59 – – – – – – – 11661 – – – –
chv12x10.clq 120 92 20 – 4 5 4 1 1 8 0 4759 48 700 0
myc5x24.clq 120 97 48 14536 0 0 0 0 0 0 0 2 1 4 112
myc11x11.clq 121 93 22 – 8 12 7 2 1 7 0 1097 85 1081 239
s3m25x5.clq 125 89 20 5440 6 8 6 5 1 1 0 5 6 9 0
myc23x6.clq 138 87 12 1681 2 3 2 2 2 57 0 4 7 56 699
myc5x30.clq 150 97 60 – 1 1 1 0 0 0 0 10 2 47 42042
s3m25x6.clq 150 90 24 – 192 278 195 186 4 12 8 64 92 128 0
myc11x14.clq 154 94 28 – 486 566 422 66 33 235 23 – 11563 – –
chv12x15.clq 180 94 30 – 26019 34161 26045 7796 1235 26798 184 – – – 0
myc5x36.clq 180 97 72 – 3 2 3 2 0 0 0 17 6 118 –
myc23x8.clq 184 90 16 – 115 165 112 88 215 23434 90 1138 1390 – –
myc11x17.clq 187 95 34 – 40109 – 33957 5056 2378 43935 2375 – – – 3159
s3m25x8.clq 200 92 32 – 46253 – 44843 38987 181 1206 478 22778 18148 40089 0
myc5x42.clq 210 98 84 – 26 15 25 4 0 0 0 443 36 1414 –
myc11x20.clq 220 95 40 – – – – – – – 38519 – – – –
myc23x10.clq 230 91 20 – – – – 38104 26210 – 7545 – – – –
chv12x20.clq 240 95 40 – – – – – – – – – – – –
myc5x48.clq 240 97 96 – 23 22 25 13 0 0 0 319 39 3316 –
s3m25x10.clq 250 93 40 – – – – – 6980 44122 – – – – 18
myc11x23.clq 253 95 46 – – – – – – – – – – – –
Table 1: Running time results in seconds for the BHOSLIB and EVIL instances. The “–” sign indicates that the running
times are exceeding the 12 hour limit.