https://doi.org/10.31449/inf.v45i2.3107 Informatica 45 (2021) 197–204 197
Estimating Clique Size via Discarding Subgraphs
Sándor Szabó
University of Pécs, Hungary
E-mail: sszabo7@hotmail.com
Bogdán Zaválnij
Rényi Institute of Mathematics
E-mail: bogdan@renyi.hu
Keywords: combinatorial optimization, maximum clique problem, greedy coloring, Lovász’ theta function, practical
solutions of NP-hard problems
Received: April 1, 2020
The paper will present a method to establish an upper bound on the clique number of a given ﬁnite simple
graph. In order to evaluate the performance of the proposed algorithm in practice we carry out a large scale
numerical experiment on carefully selected benchmark instances.
Povzetek: Razvita in opisana je nova metoda za doloˇ canje zgornje meje števila klik v grafu.
1 Introduction
In this paper we will work with ﬁnite simple graphs. A
graph is ﬁnite if it has ﬁnitely many nodes and ﬁnitely many
edges. A graph is simple if it does not have double edges
and if it does not have loops. IfV is the set of nodes and
E is the set of edges of a ﬁnite simple graph G, then the
ordered pair (V;E) completely describes the graphG.
A set of nodesI of the ﬁnite simple graphG = (V;E)
is called an independent set if two distinct nodes inI are
never adjacent. A set of nodes U of G is called a clique
if two distinct nodes inU are always adjacent. Sometimes
the subgraph   induced by U in G is called a clique of
G. If the clique   has k nodes, then we say that   is a
k-clique inG. The numberk is sometimes referred as the
size of the clique. Ak-clique   inG is called a maximal
clique ifG does not have any (k + 1)-clique that contains
  as a subgraph. Ak-clique   inG is called a maximum
clique ifG does not contain any clique with size larger than
k. This well deﬁned integerk is called the clique number
of the graph G and it is denoted by !(G). Plainly each
maximum clique inG has the same size which is equal to
!(G). Finding both maximal and maximum cliques in a
given graph has important and interesting theoretical and
practical applications. (For further details consult with [2,
5, 12, 23, 24].)
It is a well known result of the complexity theory of com-
putations that the problem of determining the clique num-
ber of a given ﬁnite simple graph belongs to the NP-hard
complexity class. (For a proof see [9, 17].) This can be in-
terpreted such that computing the clique number of a given
graph is computationally demanding. From this reason in-
stead of determining the clique number exactly sometimes
we settle for ﬁnding a large but not necessarily maximum
clique. In this sense we distinguish exact and non-exact
clique search algorithms. The non-exact algorithms are fur-
ther categorized as local search or stochastic or heuristic
algorithm depending on the nature of the search technique
involved. An example of the exact algorithm can be found
in [22] and an example of the non-exact method can be
seen in [13]. A strong upper bound can be used as a quality
certiﬁcate to prove that a heuristically found clique is close
enough to a maximum clique.
The main result of this paper is a procedure to establish
an upper bound for the clique number of a given graph. The
procedure employs legal coloring of the nodes of tactically
chosen subgraphs of the given graph. Although the col-
oring schemes we use are complex the approach is essen-
tially combinatorial. As a consequence it does not involve
ﬂoating point arithmetic and free of rounding errors. It is
known that the Lovász’ theta function can be used to com-
pute upper bounds for the clique number of a given graph.
This estimate in practice boils down to solve semideﬁnite
programs which is inherently a ﬂoating point computation.
We were interested in how the elementary combinatorial
and the less elementary techniques compares. In the lack
of adequate theoretical tools we carried out a large scale
numerical experiment on carefully selected problems.
2 Bounding the clique number
Let G be a ﬁnite simple graph and let b a ﬁxed positive
integer. We color the nodes of the graph G such that the
following two conditions hold.
1. Each node ofG receives exactlyb distinct colors.
2. Two adjacent nodes never receive the same color.
198 Informatica 45 (2021) 197–204 S. Szabó et al.
A coloring of the nodes of G satisfying these conditions
is called a b-fold legal coloring of the nodes of G. For
each ﬁnite simple graph G there is an integer k such that
the nodes ofG can be legally colored withk colors in ab-
fold manner but the nodes ofG do not admit a legalb-fold
coloring using (k  1) colors. This well deﬁned number
k is referred as theb-fold chromatic number ofG and it is
denoted by   b
(G). In the b = 1 particular case we drop
the subscriptb and use the notation  (G). We refer to this
number as the chromatic number ofG. Coloring the nodes
of a graph is an important problem with many applications
and with a venerable history. (See [10].)
At a legal coloring of the nodes ofG the nodes of ak-
clique inG must receivek distinct colors and consequently
!(G)    (G). In other words, legal coloring of the nodes
can be used to establish upper bound for the clique number.
It is known from the complexity theory of computations
that determining the chromatic number of a given graph
is an NP-hard problem. A number of greedy coloring al-
gorithms is available to construct a legal coloring of the
nodes but not necessarily with an optimal number of col-
ors. (See for instance [6, 14, 7].) Many clique search al-
gorithms used in practice employs these greedy algorithms
for upper bounding the clique size.
In this paper we will show that with some extra effort
one may improve on the above upper estimates. We have
carried out a number of computations in which approxi-
mate node coloring procedures were used. But a little con-
templation can convince the reader that the computational
scheme we use in fact can be combined with less elemen-
tary clique size estimates without major difﬁculty.
LetI(G) denote the set of all independent sets of nodes
of a graphG, and letI(G;u) denote the independent sets
ofG that contain the nodeu. For each independent setI,
we deﬁne a nonnegative real variable x
I
. The fractional
chromatic number ofG, which is denoted by  f
(G) is the
minimum value of
P
I2I(G)
x
I
, subject to
P
I2I(G;u)
x
I
  1 for each nodeu. This value provides an upper estimate
of the clique number ofG. (See [1].)
A connection between the fractional and theb-fold chro-
matic numbers is the following  f
(G) = lim
b!1
  b
(G)
b
.
Therefore in practice one can useb-fold coloring [19] as an
approximation.
Lemma 1. !(G)    b
(G)
b
    (G).
Proof. At anyb-fold coloring of the nodes ofG the nodes
of ak-clique inG must receiveb  k distinct colors. Thus
  b
(G) must be at leastb  k.
For any positive integer b and a legal node coloring of
the graph with   (G) colors one can construct a legal b-
fold coloring with b    (G) colors. For this replace each
color with a list ofb different colors on each node. From
the conditions of legal node coloring and b-fold coloring
this will yield to a properb-fold coloring. Thus  b
(G)  b    (G).
Computing the b-fold chromatic number is an NP-hard
problem, as for b = 1 case it reduces to the problem of
computing the chromatic number. So one looks for heuris-
tic algorithms in case of large graphs. The b-fold color-
ing of a graph can be reduced to a legal coloring of a suit-
able auxiliary graph as described in [19, 21], so any heuris-
tic algorithm for legal coloring of the nodes can be easily
adopted for ﬁnding ab-fold coloring as well.
We may use other upper bounding techniques. For each
ﬁnite simple graphG there is a well deﬁned graph param-
eter#(G), which is called the Lovász’ theta number [15].
The Lovász’ theta number of the complement of a graph
G also bounds the clique number of G from above. The
values of the # function can be computed in polynomial
time [3, 4], but the degree of the polynomial bound of the
running time is high. The bounds on the clique number we
have listed so far are the following [8]:
!(G)  #(G)    f
(G)    b
(G)
b
    (G):
3 The description of the algorithm
Letv
1
;:::;v
n
be all the nodes ofG = (V;E). For each
nodev
i
ofG we deﬁne a graphK
i
ofG. Namely, letK
i
be
the subgraph ofG induced by the set of nodesN(v
i
). Here
N(v
i
) is the set of neighbors ofv
i
inG, that is,
N(v
i
) =fv :v2V;fv
i
;vg2Eg:
For eachi, 1  i  n we compute an upper bound  i
for
!(K
i
). For example using a greedy coloring algorithm we
color the nodes ofK
i
legally and set  i
to be the number
of colors the algorithm provided. Obviously one can use
another upper bound as well. Using the given graphG we
deﬁne a sequence of numbers  1
;:::;  n
. We pick a graph
K
i
with a minimum  i
. We set  n
=   i
. Next we delete
the nodev
i
fromG. We repeat the whole procedure with
this smaller graph and get a new quantity  n  1
. When all
nodes ofG are deleted the computation terminates. At this
stage we have a sequence  1
;:::;  n
.
Theorem 1. Using the notation introduced above the in-
equality
!(G)  1 + maxf  1
;:::;  n
g
holds.
In the remaining part of this section we justify this claim.
Let u
1
;:::;u
n
be a ﬁxed rearrangement of the nodes
v
1
;:::;v
n
. We consider the subgraphL
i
ofG induced by
the set of nodesN(u
i
)\fu
1
;:::;u
i
g for eachi, 1  i  n.
Note thatu
i
62N(u
i
) and so
N(u
i
)\fu
1
;:::;u
i
g =N(u
i
)\fu
1
;:::;u
i  1
g:
In thei = 1 special case we should identifyfu
1
;:::;u
i  1
g
with the empty set. ThusL
1
is a graph without any node.
In this situation we set!(L
1
) to be 0.
We will need the following result.
Estimating Clique Size via Discarding Subgraphs Informatica 45 (2021) 197–204 199
Lemma 2. Using the notations introduced above the in-
equality
!(G)  1 + maxf!(L
1
);:::;!(L
n
)g
holds.
Proof. Set k = !(G). Clearly, the graph G contains a
k-clique   . On the ﬁxed list u
1
;:::;u
n
of the nodes
v
1
;:::;v
n
there is a unique u
i
such that u
i
is a node of
  butu
j
is not a node of   for eachj,i<j  n. The set
N(u
i
)\fu
1
;:::;u
i  1
g containsk  1 nodes of   and so
k  1  !(L
i
) holds. Fromk  1 +!(L
i
) it follows that
k  1 + maxf!(L
1
);:::;!(L
n
)g:
The alart reader will recognize that in the statement of
Lemma 2 the inequality sign can be replaced by an equation
sign. But we are content with this weaker result.
Computing !(L
i
) is computationally demanding.
Therefore we use an easily computable upper bound   i
for !(L
i
) instead. Lemma 2 shows that we can freely
rearrange the nodes for the estimate of !(G). This
rearrangement inﬂuences the ﬁnal result. Preliminary
tests showed that different rearrangements can result in
quite different upper bound values. The rearrangement we
propose results a rather good upper estimate.
Let us turn back to our proposed algorithm. First we
locate a subgraphK
i
ofG for which the corresponding  i
is a minimum among  1
;:::;  n
. We setu
n
= v
i
. This
will be the ﬁrst node ﬁxed in our rearrangement. Putting it
in another way we may say that we have identiﬁed the last
elementu
n
of the ﬁxed list of nodesu
1
;:::;u
n
. We have
also identiﬁed the subgraphL
n
. Namely,L
n
=K
i
.
We delete the nodeu
n
=v
i
from the graphG. It means
we are working with a smaller new graph induced by the
set of nodesVnfu
n
g. Next we identify the nodeu
n  1
and
the subgraphL
n  1
by performing the previous step again.
Continuing in this way we get the subgraphsL
1
;:::;L
n
.
Our procedure gives that!(L
i
)    i
, for eachi, 1  i  n
and so
maxf!(L
1
);:::;!(L
n
)g  maxf  1
;:::;  n
g:
Combining this result with Lemma 2 we get!(G)  1 +
maxf  1
;:::;  n
g as stated in Theorem 1. We we call this
algorithm DISCARDING.
We make some remarks about streamlining the DIS-
CARDING procedure. Remember that ﬁrst employing a
greedy coloring algorithm to the graphs K
1
;:::;K
n
we
compute the numbers  1
;:::;  n
. Since we are looking for
the minimum value occurring among  1
;:::;  n
in certain
cases we need not to complete the coloring procedure. We
may abort coloring a subgraphK
i
if we have already used
more colors than the minimum number of colors needed so
far.
Next, when we delete the nodev
i
fromG for which  i
is
minimum we may delete eachv
j
for which  j
is minimum.
In this way we end up with a shorter list  1
;:::;  s
instead
of the longer list  1
;:::;  n
. Note that the upper estimate
!(G)  1+maxf  1
;:::;  s
g is not weaker than the upper
estimate!(G)  1+maxf  1
;:::;  n
g. We can also delete
all thev
i
nodes during the procedure, where  i
less than or
equal to the maximum of the previous  values.
Note that when the nodev
j
is not adjacent to the deleted
nodev
i
, then the upper bound  j
of!(K
j
) need not to be
recalculated. The reason is that in this situation deleting the
nodev
i
leaves the subgraphK
j
unchanged.
We would like to point out, that calculating the  i
val-
ues can be carried out independently of each other, thus we
can perform this calculation in parallel fashion. We im-
plemented the algorithm DISCARDING in both sequen-
tial and parallel manner using OpenMP for shared mem-
ory computers. Both programs resulted the same upper
bounds. It is clear, that the program could be implemented
using MPI for distributed computers as well thus achieving
greater scalability.
4 A simpler estimating procedure
In this section we consider a less sophisticated version of
the procedure DISCARD. We will call this new procedure
SEQUENTIAL. We ﬁx an orderingw
1
;w
2
;:::;w
n
of the
nodesv
1
;v
2
;:::;v
n
of the given ﬁnite simple graphG =
(V;E). We consider the graph L
i
induced by N(w
i
)\
fw
1
;:::;w
i
g for eachi, 1  i  n and compute a  i
such
that !(L
i
)    i
holds for each i, 1  i  n. Now the
inequality!(G)  1 + maxf  1
;:::;  n
g holds.
Let P be an auxiliary procedure for computing an up-
per bound  (G;P ) for the clique number!(G) of a given
ﬁnite simple graphG. We say thatP has the monotonic-
ity property if  (H;P )    (G;P ) holds wheneverH is a
subgraph ofG.
For example the auxiliary procedure of computing the
chromatic number of a graph has the monotonicity prop-
erty as the inequality   (H)    (G) holds for each sub-
graphH ofG. On the other hand the auxiliary procedure
of using the not necessarily optimal number of colors of a
legal coloring of the nodes does not have the monotonicity
property. It can happen that we use more colors to color the
nodes of a subgraphH than we use for coloring the nodes
of the whole graphG.
The next result reveals a certain optimality property of
the DISCARDING procedure.
Theorem 2. LetG = (V;E) be a ﬁnite simple graph and
suppose that the auxiliary procedure used to establish the
upper bound !(K
i
)    i
has the monotonicity property.
Then the SEQUENTIAL procedure does not provide a bet-
ter estimate for the clique number ofG than the DISCARD-
ING procedure.
Proof. Suppose that the DISCARDING algorithm
gives rise to the ordering u
1
;u
2
;:::;u
n
of the nodes
v
1
;v
2
;:::;v
n
of G. Assume on the contrary that the
200 Informatica 45 (2021) 197–204 S. Szabó et al.
SEQUENTIAL procedure applied to some ordering
w
1
;w
2
;:::;w
n
of the nodesv
1
;v
2
;:::;v
n
ofG leads to a
strictly smaller upper estimate of!(G).
We show that such a sequence leads to contradiction.
Let us assign colors red, green, yellow to the nodes
v
1
;v
2
;:::;v
n
. This coloring of the nodes is based on the
sequenceu
1
;u
2
;:::;u
n
, and it is not connected to the con-
cept of legal coloring. There is a special node in this se-
quence, called the pivot node, for which the upper estimate
attains its maximum. If the maximum is attained at sev-
eral nodes we choose the last one. The pivot node of the
graph will receive color green. We color the nodes in the
sequence preceeding the pivot node by red, and the nodes
after the pivot node by yellow.
Of course the members of the sequence u
1
;u
2
;:::;u
n
and the sequence w
1
;w
2
;:::;w
n
are colored with
red, green and yellow, as they are just reordering of
v
1
;v
2
;:::;v
n
.
The following observation will play a critical role. When
in the course of the algorithm we deleted all yellow nodes
from the graphG (let us denote the nodes of this new graph
byV
y
) we made an upper estimate for graphs using all re-
maining nodes, and the upper estimate for the graph using
the green node was minimal. That means that the upper es-
timate for the graphs using the red nodes is at least as this
ﬁgure after deleting the all yellow nodes of the graph.
Now we look at the other sequencew
1
;w
2
;:::;w
n
as-
sumed to give a better upper estimate. We locate two nodes
in it, the pivot node (the green one), and the last node
among the nodes that colored red. We shall denote them
w
g
andw
r
, respectively. Note, that all nodesw
i
,i>r are
colored yellow or green. We distinguish two cases:
Case (g>r). In this situation all nodesw
i
;i>g are col-
ored yellow, as the last red node appears before the
green node. Let us denote the nodes of the graph we
get after deleting all nodesw
i
, i > g fromG byV
g
.
As the set of deleted nodes is a subset of the set of all
yellow nodes, the graph induced byV
y
is a subgraph
of the graph induced by V
g
. But the upper estimate
for the graph induced by N(w
g
)\V
g
is assumed to
be less than the upper estimate for the graph induced
by N(w
g
)\V
y
. This contradicts the monotonicity
property of the auxiliary procedure.
Case (r>g). In this situation all nodesw
i
,i>r are col-
ored yellow, as w
r
is the last red node and the only
green one precedes it. Let us denote the nodes of the
graph we get after deleting all nodesw
i
,i > r from
G byV
r
. As the set of deleted nodes is a subset of the
set of all yellow nodes, the graph induced byV
y
is a
subgraph of the graph induced byV
r
. But the upper
estimate for the graph induced byN(w
r
)\V
r
is as-
sumed to be less than the upper estimate for the graph
induced byN(w
r
)\V
y
. This contradicts the mono-
tonicity property of the auxiliary procedure.
5 Numerical experiments
We selected altogether 43 graphs for carrying out our ex-
tended measurements. As we were aiming at problems
where it is hard to calculate the !(G), we used sources
of graphs according to this, and decided to use graphs hav-
ing at least 500 nodes. We used those graphs from these
sources for which either the Lovász’ theta program or our
algorithm could ﬁnish the calculation of the upper bound in
100 000 seconds using the available 48GB of memory. The
ﬁrst 29 graphs
1
come from the problems of the 2nd DI-
MACS Challenge [11]. The second 11 graphs
2
come from
various error correcting code problems [18]. (Note, that we
used complement graphs of those from the webpage, as the
original problem asks for the maximum independent set.)
The last 3 graphs
3
are reformulated problems of mono-
tonic matrices [20, 16]. We choose these graphs so that
they would represent extremely hard clique search prob-
lems and for some we even do not know the value of the
size of the maximum clique as the available clique search
programs are not able to ﬁnd the exact!(G) value. There
are a few ones where the exact value of the clique number
is known but the existing clique solvers are not able to com-
pute them. The so-called Johnson codes give rise to such
clique problems.
As the proposed algorithm instructs us to use an arbitrary
upper bound for calculating the  values we need to choose
one method as a starting point. We have chosen theb-fold
coloring with Culberson’s iterated recoloring scheme be-
cause it gives the best result in reasonable time of couple
of seconds. This way we were using several hours of com-
putational time and hoped to achieve improvements over
the original upper bound ofb-fold coloring. Ab-fold legal
coloring of the nodes of a given graph can be reduced to
legally coloring the nodes of an auxiliary graph described
in [21]. In the course of our numerical experiments we per-
formed several measurements to establish and compare dif-
ferent upper bounds. We collected the results in the Table
1. Namely, we did the following measurements:
1. perform a legal coloring of the graph (column: “legal
coloring”);
2. ﬁnd the Lovász’ theta value of the complement graph
(column: “#(G)”);
3. perform a b-fold coloring of the graph (column: “b-
fold coloring”);
4. useb-fold coloring as a base and perform the proposed
algorithm (column: “DISC”).
All coloring programs started with a DSatur algorithm
due to D. Brélaz [6]. Then we recolored the nodes several
1
http://iridia.ulb.ac.be/~fmascia/maximum_
clique/DIMACS-benchmark
2
https://oeis.org/A265032/a265032.html
3
http://mathworld.wolfram.com/MonotonicMatrix.
html
Estimating Clique Size via Discarding Subgraphs Informatica 45 (2021) 197–204 201
times using a method due to J. C. Culberson [7]. The stop-
ping criteria was if the number of colors did not changed
after a speciﬁed number of iterations. For smaller and
medium graphs we used 1000 iterations; for bigger graphs
(over 3000 nodes) we used 500 iterations. We used 7-fold
coloring for smaller graphs (up to 2000 nodes); 5-fold col-
oring for medium graphs (over 2000 nodes); and 3-fold
coloring for the biggest graphs (over 3000 nodes). The
Lovász’ theta function was computed with the program of
B. Borchers [3, 4]. The measurements were performed on
a computer with two Intel Xeon X5680 3.33 GHz proces-
sors – all together 12 cores – and 48GB of RAM. (This
computer happens to be a node of a supercomputer, but
this is of no importance for the present paper.) The legal
coloring andb-fold coloring of the graphs were performed
in sequential manner. The Lovász’ theta calculations used
all 12 cores due to the underlying BLAS implementation.
Our DISCARDING algorithm used also 12 cores as it per-
formed the calculation of   i
values independently. Note,
that for BLAS the 12 core is a limit as it needs to be run
in shared memory environment, while our algorithm could
have used more cores in distributed parallelization on a su-
percomputer but for the sake of comparability we limited it
to the same 12 cores.
The running times for legal coloring were smaller than
a second or in the range of a few seconds. The time for
performing the b-fold coloring depends on the size of the
graph and the value ofb. The running times forb-fold col-
oring algorithm was in the range of several seconds up to
a few minutes. The running times of the Borchers’ pro-
gram on 12 cores for calculating the Lovász’ theta of the
complement graph is indicated in the column “time (sec)
#(G) (12c)”. The running times of our parallel algorithm
using the same 12 cores is indicated in the column “time
(sec) DISC (12c)”. Those values that cannot be calculated
on the used test hardware we indicated in the table with
“> 24h”, as the 100 000 seconds limit is roughly 24 hours.
6 Evaluation of the proposed
algorithm
From the results in the Table 1 we may conclude that the
proposed algorithm is feasible, that is, it can be computed
on a nowadays computer in reasonable time. But in this
section we are making also a comparison between our al-
gorithm based on theb-fold coloring and the Lovász’ theta
upper bound calculation. We should point out, that this
comparison is far from trivial:
1. We needed to parallelize our program and use the
same number of cores by both programs. Note, that
Borchers’ program uses shared memory, so we could
not use more cores than cores in one node of a super-
computer. On the other hand our program could be
written to use a distributed supercomputer with hun-
dreds of cores.
2. As our program, which uses b-fold coloring, using
only integer and bit calculation the different architec-
tures are not affecting the running times much. Op-
posed to this Borchers’ program uses ﬂoating point
calculations and BLAS. Thus different architectures
(Intel or AMD), different compilers (icc or gcc)
and different implementations of BLAS (Reference
BLAS, ATLAS, OpenBLAS or Intel MKL library) all
have huge effect on the running times. A modern
AMD desktop PC with 8 core Ryzen processor us-
ing gcc as a compiler and OpenBLAS resulted in up
to 50 times(!) slower running times compared to the
times presented in Table 1 for the Lovász’ theta cal-
culations on Intel architecture, icc compiler and the
MKL library. The architecture, compiler and BLAS
implementation used for the results of the present pa-
per all strongly favor the Lovász’ theta calculations. A
reproduction of the results on a desktop PC may result
much longer running times for the Lovász’ theta cal-
culation program due to Borchers while giving similar
times for our algorithm.
The reader can see that the computation of the Lovász’
theta number for 22 of 43 instances could not be completed.
In each of these 22 cases the program terminated with the
error message: “not enough memory”. As it turns out the
length of the calculation of the Lovász’ theta function de-
pends on the number of edges (m) of the complement graph
(or the non-edges, the missing edges of the graph). The
running time and memory requirements are O
  m
3
  and
O
  m
2
  , respectively. (See [3, 4].) Using these asymptotic
results we estimated the running time as 7:2  10
  11
m
3
sec-
onds and the memory requirement as 9:2  10
  9
m
2
Giga-
Bytes. This estimate was consistent with the experimen-
tal results. Clearly 48GB of memory is not enough in the
missing cases. Actually, some instances, as for example
thekeller6 graph, would need 1 TB(!) of memory and
would run for nearly a thousand of years. If one would use
a PC with nowadays usual 8-16GB of memory 6 other in-
stances would be out of reach, thus making 28 out of 43
instances incalculable.
To sum up the results, we can say, that our algorithm
gives better upper bounds than the Lovász’ theta calcu-
lation for 24 out of 43 instances. In addition it runs
faster for 24 out of 43 instances. It holds for the cases
when the Lovász’ theta computation cannot be completed.
Further there are instances when our algorithm actually
gave lower bound than the Lovász’ theta approach. These
are the graphs MANN_a45, MANN_a81, keller4 and
p_hat300-1 from which the former two are in the ta-
ble, and the later two are not as they have less than
500 nodes. Obviously, there can be other cases as well
among those where the Lovász’ theta could not be calcu-
lated. The graphs johnson10-4-4 and p_hat300-2
gave the same bound – these two also was excluded
from the table because of being too small. Note, that
in several cases our algorithm gave sharp upper bound
which is equal to the clique number: p_hat300-1,
202 Informatica 45 (2021) 197–204 S. Szabó et al.
latin10, c-fat500-1, queen40, queen50 and
san1000 graphs.
Let us return to the question if the proposed algorithm
can lower the upper bound provided by the base algorithm.
One can see from the results that the proposed algorithm
with few exceptions improves the upper bound of b-fold
coloring, in some cases radically. We may conclude that
there is computational evidence that the proposed algo-
rithm lower the upper bound if we use more computational
resources. Let us turn to the question how the proposed al-
gorithm compares to the Lovász’ theta based methodology.
We are getting better result only a few times. However,
we were able to compute our new bound for all but two
graphs that cannot be said about the Lovász’ theta number.
Practically, our algorithm is so versatile that even for those
cases where the upper bound could not be calculated we are
able to tune it using smallerb and using smaller number of
recoloring steps. Thus reducing the running time we can
turn the instance calculable. Note, that one can replace the
upper bounds computed by coloring the nodes of the tacti-
cally chosen subgraphs by upper bounds computed by the
Lovász’ theta function. The calculations involved in this
situation would use much more time and need to be per-
formed several thousand times. Thus we would expect it to
be reasonable only using distributed computing on a super-
computer, as the calculations of the  values can be done
independently.
Acknowledgements
The project has been supported by National Research, De-
velopment and Innovation Ofﬁce – NKFIH Fund No. SNN-
135643.
References
[1] E. Balas and J. Xue, Weighted and unweighted
maximum clique algorithms with upper bounds
from fractional coloring, Algorithmica 15 (1996),
pp. 397–412. https://doi.org/10.21236/
ada275328
[2] I. M. Bomze, M. Budinich, P. M. Pardalos and M.
Pelillo, The Maximum Clique Problem, Handbook
of Combinatorial Optimization Vol. 4, Kluwer Aca-
demic Publisher, 1999. https://doi.org/10.
1007/978-1-4757-3023-4_1
[3] B. Borchers, CSDP , A C library for semideﬁnite
programming, Optimization Methods and Software,
11(1) (1999), pp. 613–623. https://doi.org/
10.1080/10556789908805765
[4] B. Borchers and J. G. Young, Implementation
of a primal-dual method for SDP on a shared
memory parallel architecture, Computational
Optimization and Applications 37(3), (2007)
pp. 355–369. https://doi.org/10.1007/
s10589-007-9030-3
[5] A. Bóta and M. Krész, A high resolution clique-
based overlapping community detection algorithm for
small-world networks, Informatica, 39(2). (2015).
[6] D. Brélaz, New methods to color the vertices
of a graph, Communications of the ACM, 22
(1979), pp. 251–256. https://doi.org/10.
1145/359094.359101
[7] J. C. Culberson, Iterated Greedy Graph Coloring and
the Difﬁculty Landscape, Technical Report, Univer-
sity of Alberta, 1992.
[8] C. Elphick and P. Wocjan, An inertial lower bound
for the chromatic number of a graph, The Elec-
tronic Journal of Combinatorics, V olume 24, Is-
sue 1 (2017)https://arxiv.org/abs/1605.
01978https://doi.org/10.37236/6404
[9] M. R. Garey and D. S. Johnson, Computers and
Intractability: A Guide to the Theory of NP-
completeness, Freeman, New York, 2003.
[10] F. Harary, Graph Theory, Addison-Wesley, 1969.
[11] J. Hasselberg, P. M. Pardalos, and G. Vairak-
tarakis, Test case generators and computa-
tional results for the maximum clique prob-
lem, Journal of Global Optimization 3 (1993),
pp. 463–482. http://www.springerlink.
com/content/p2m65n57u657605n
https://doi.org/10.1007/bf01096415
[12] D. Kumlander, Some Practical Algorithms to Solve
the Maximal Clique Problem, PhD. Thesis, Tallin
University of Technology, 2005.
[13] S. Lamm, P. Sanders, C. Schulz, D. Strash,
R. F. Werneck, Finding near-optimial indepen-
dent sets at scale, Proceedings of the 16th Meet-
ing on Algorithm Engineering and Experimenta-
tion (ALENEX’16). 2016. https://doi.org/
10.1137/1.9781611974317.12
[14] F. T. Leighton, A graph coloring algorithm for large
scheduling problems, Journal of Research of National
Bureau of Standards 84 (1979), pp. 489–506.
[15] L. Lovász, On the Shannon capacity of a graph, IEEE
Transactions on Information Theory, V olume 25 Issue
1, January 1979 pp. 1–7.https://doi.org/10.
1109/TIT.1979.1055985
[16] P. R. J. Östergård and A. Pöllänen, New results
on tripod packings. Discrete Comput. Geom. 61
(2019), pp. 271–284. https://doi.org/10.
1007/s00454-018-0012-2
Estimating Clique Size via Discarding Subgraphs Informatica 45 (2021) 197–204 203
[17] C. H. Papadimitriou, Computational Complexity,
Addison-Wesley Publishing Company, Inc., Reading,
MA 1994.
[18] N. J. A. Sloane, Challenge Problems: Indepen-
dent Sets in Graphs, http://neilsloane.
com/doc/graphs.html
[19] S. Stahl, n-Tuple colorings and associated
graphs, Journal of Combinatorial Theory,
Series B V olume 20, Issue 2, April 1976,
pp. 185–203. https://doi.org/10.1016/
0095-8956(76)90010-1
[20] S. Szabó, Monotonic matrices and clique search in
graphs, Annales Univ. Sci. Budapest., Sect. Comp.
41 (2013), pp. 307–322.
[21] S. Szabó and B. Zaválnij, Reducing graph coloring to
clique search, Asia Paciﬁc Journal of Mathematics, 1
(2016), pp. 64–85.
[22] S. Szabó and B. Zaválnij, A different ap-
proach to maximum clique search. 20th In-
ternational Symposium on Symbolic and
Numeric Algorithms for Scientiﬁc Comput-
ing (SYNASC2018) pp. 310–316. https:
//doi.org/10.1109/SYNASC.2018.00055
[23] S. Szabó and B. Zaválnij, Reducing hypergraph col-
oring to clique search. Discrete Applied Mathe-
matics, 264 (2019), pp. 196–207. https://doi.
org/10.1016/j.dam.2018.09.010
[24] Q. Wu and J-K. Hao, A review on algorithms for max-
imum clique problems, European Journal of Opera-
tional Research. V olume 242, Issue 3, 1 May 2015,
pp. 693–709. https://doi.org/10.1016/j.
ejor.2014.09.064
204 Informatica 45 (2021) 197–204 S. Szabó et al.
Table 1: The test graphs and their upper bounds for!(G) from different legal coloring methods and Lovász’ theta along
with the new bound from the proposed algorithm. We indicated by an * those cases where the program could not reach
the result within 100,000 seconds, that is roughly in 24 hours.
jVj density !(G) legal #(
  G) time (sec) b-fold DISC time (sec)
% coloring #(
  G) (12c) DISC (12c)
brock800_1 800 64.93 23 117 * > 24h 103 68 12717s
brock800_2 800 65.13 24 118 * > 24h 103 68 11670s
brock800_3 800 64.87 25 117 * > 24h 103 67 15414s
brock800_4 800 64.97 26 118 * > 24h 103 68 9849s
C500.9 500 90.05   57 139 84.20 109s 130 115 10235s
C1000.9 1000 90.11   68 251 123.49 6029s 232 207 94916s
C2000.5 2000 50.02 16 194 * > 24h 174 90 68024s
c-fat500-1 500 3.57 14 14 * > 24h 14 14 9s
DSJC500_5 500 50.20 13 58 22.74 9960s 51 28 850s
DSJC1000_5 1000 50.02 15 107 * > 24h 92 49 10913s
hamming10-4 1024 82.89 40 74 * > 24h 55 50 6227s
johnson-12-5-4 792 95.58 80 140 99.00 130s 106 105 4318s
johnson-13-4-4 715 94.96 65 115 71.50 107s 76 76 1877s
johnson-13-5-4 1287 96.89   123 212 143.00 792s 155 154 19485s
keller5 776 75.15 27 31 * > 24h 31 31 598s
keller6 3361 81.82 59 64 * > 24h 64 63 5515s
MANN_a45 1035 99.63 345 360 356.05 23s 360 353 29869s
MANN_a81 3321 99.88 1100 1134 1126.62 589s 1134 1121 91875s
p_hat1000-1 1000 24.48 10 52 * > 24h 46 17 4041s
p_hat700-1 700 24.93 11 40 * > 24h 35 13 977s
p_hat700-2 700 49.76 44 86 * > 24h 76 52 31637s
p_hat700-3 700 74.80 62 129 72.00 11781s 120 87 73518s
p_hat500-1 500 25.31 9 31 * > 24h 27 11 376s
p_hat500-2 500 50.46 36 63 38.97 13677s 57 40 8540s
p_hat500-3 500 75.19 50 101 58.57 1391s 92 67 14654s
latin10 900 75.97 90 110 * > 24h 93 90 5529s
queen40 1600 91.91 40 40 * > 24h 40 40 5397s
queen50 2500 93.49 50 50 * > 24h 50 50 24986s
san1000 1000 50.15 15 15 * > 24h 15 15 2173s
1dc.512-c 512 92.56 52 73 53.03 76s 55 54 2007s
1dc.1024-c 1024 95.41 94 137 95.98 1004s 101 99 9171s
1dc.2048-c 2048 97.22   172 262 174.73 14395s 189 186 78627s
1et.1024-c 1024 98.17 171 215 184.23 93s 191 189 94866s
1et.2048-c 2048 98.93 316 401 342.03 1026s 356 * > 24h
1tc.1024-c 1024 98.48 196 227 206.30 64s 216 212 23475s
1tc.2048-c 2048 99.10 352 420 374.64 753s 387 * > 24h
1zc.512-c 512 94.72 62 93 68.75 23s 72 71 1110s
1zc.1024-c 1024 96.82   112 180 128.67 295s 136 134 13793s
2dc.1024-c 1024 67.70 16 31 * > 24h 21 18 4024s
2dc.2048-c 2048 75.93 24 54 * > 24h 37 32 53711s
monoton-9 729 83.52 28 45 34.41 5465s 41 37 13670s
monoton-10 1000 85.14 32 61 * > 24h 51 46 39031s
monoton-11 1331 86.47 38 69 * > 24h 63 57 52911s