Fast Algorithms for the Maximum Clique Problem on
Massive Sparse Graphs
Bharath Pattabiraman1 ‡ , Md. Mostofa Ali Patwary1 ‡ ,Assefaw H. Gebremedhin2 , Wei-keng Liao1 , and Alok Choudhary1‡
Authors contributed equally1

Northwestern University, Evanston, IL.
{bpa342,mpatwary,wkliao,choudhar}@eecs.northwestern.edu
2
Purdue University, West Lafayette, IN.
agebreme@purdue.edu
Abstract. The maximum clique problem is a well known NP-Hard problem withapplications in data mining, network analysis, information retrieval and manyother areas related to the World Wide Web. There exist several algorithms forthe problem with acceptable runtimes for certain classes of graphs, but many ofthem are infeasible for massive graphs. We present a new exact algorithm that
employs novel pruning techniques and is able to quickly find maximum cliquesin large sparse graphs. Extensive experiments on different kinds of synthetic andreal-world graphs show that our new algorithm can be orders of magnitude fasterthan existing algorithms. We also present a heuristic that runs orders of magnitude
faster than the exact algorithm while providing optimal or near-optimal solutions.

1

Introduction

A clique in an undirected graph is a subset of vertices in which every two vertices are
adjacent to each other. The maximum clique problem seeks to find a clique of the largest
possible size in a given graph.
The maximum clique problem, and the related maximal clique and clique enumeration problems, find applications in a wide variety of domains, many intimately related
to the World Wide Web. A few examples include: information retrieval [2], community
detection in networks [15, 29, 33], spatial data mining [40], data mining in bioinformatics [37], disease classification based on symptom correlation [7], pattern recognition[31], analysis of financial networks [5], computer vision [19], and coding theory [8]. To
get a sense for how clique computation arises in the aforementioned contexts, consider
a generic data mining or information retrieval problem. A typical objective here is toretrieve data that are considered similar based on some metric. Constructing a graph inwhich vertices correspond to data items and edges connect similar items, a clique in thegraph would then give a cluster of similar data. More examples of application areas forclique problems can be found in [18, 30].
The maximum clique problem is NP-Hard [16]. Most exact algorithms for solving
it employ some form of branch-and-bound approach. While branching systematicallysearches for all candidate solutions, bounding (also known as pruning) discards fruitless candidates based on a previously computed bound. The algorithm of Carraghanand Pardalos [9] is an early example of a simple and effective branch-and-bound algorithm for the maximum clique problem. More recently, Östergȧrd [28] introduced an
improved algorithm and demonstrated its relative advantages via computational experiments. Tomita and Seki [35], and later, Konc and Janežič [21] use upper bounds computed using vertex coloring to enhance the branch-and-bound approach. Other examplesof branch-and-bound algorithms for the clique problem include [6, 34, 3]. Prosser [32]in a recent work compares various exact algorithms for the maximum clique problem.
In this paper, we present a new exact branch-and-bound algorithm for the maximum
clique problem that employs several new pruning strategies in addition to those used in[9], [28], [35] and [21], making it suitable for massive graphs. We run our algorithms
on a large variety of test graphs and compare its performance with the algorithm ofCarraghan and Pardalos [9], the algorithm of Östergȧrd [28] and the algorithm of Konc
and Janežič [21]. We find our new exact algorithm to be up to orders of magnitude
faster on large, sparse graphs and of comparable runtime on denser graphs. We alsopresent a hew heuristic, which runs several orders of magnitude faster than the exact
algorithm while providing solutions that are optimal or near-optimal for most cases.
We have made our implementations publicly available3 . Both the exact algorithm andthe heuristic are well-suited for parallelization.

2

Related Previous Algorithms

Given a simple undirected graph G, the maximum clique can clearly be obtained byenumerating all of the cliques present in it and picking the largest of them. Carraghan
and Pardalos [9] introduced a simple-to-implement algorithm that avoids enumerating
all cliques and instead works with a significantly reduced partial enumeration. The reduction in enumeration is achieved via a pruning strategy which reduces the search
space tremendously. The algorithm works by performing at each step i, a depth firstsearch from vertex vi , where the goal is to find the largest clique containing the vertex
vi . At each depth of the search, the algorithm compares the number of remaining vertices that could potentially constitute a clique containing vertex vi against the size of thelargest clique encountered thus far. If that number is found to be smaller, the algorithm
backtracks (search is pruned).
Östergȧrd [28] devised an algorithm that incorporated an additional pruning strategy to the one by Carraghan and Pardalos. The opportunity for the new pruning strategy
is created by reversing the order in which the search is done by the Carraghan-Pardalos
algorithm. This allows for an additional pruning with the help of some auxiliary bookkeeping. Experimental results in [28] showed that the Östergȧrd algorithm is faster thanthe Carraghan-Pardalos algorithm on random and DIMACS benchmark graphs [20].
However, the new pruning strategy used in this algorithm is intimately tied to the orderin which vertices are processed, introducing an inherent sequentiality into the algorithm.
A number of existing branch-and-bound algorithms for maximum clique also use
a vertex-coloring of the graph to obtain an upper bound on the maximum clique. A
popular and recent algorithm based on this idea is the algorithm of Tomita and Seiku
3

http://cucis.ece.northwestern.edu/projects/MAXCLIQUE/

[35] (known as MCQ). More recently, Konc and Janežič [21] presented an improved
version of MCQ, known as MaxCliqueDyn (MCQD and MCQD+CS), that involves theuse of tighter, computationally more expensive upper bounds applied on a fraction of
the search space.

3

The New Algorithms

We describe in this section new algorithms that overcome the shortcomings mentioned
earlier; the new algorithms use additional pruning strategies, maintain simplicity, andavoid a sequential computational order. We begin by first introducing the following
notations. We identify the n vertices of the input graph G = (V, E) as {v1 , v2 , . . . , vn }.
The set of vertices adjacent to a vertex vi , the set of its neighbors, is denoted by N (vi ).
And the degree of the vertex vi , the cardinality of N (vi ), is denoted by d(vi ).
3.1

The Exact Algorithm

The maximum clique in a graphcan be found by computing the Algorithm 1 Algorithm for finding the maximum cliquelargest clique containing each of a given graph. Input: Graph G = (V, E), lower boundvertex and picking the largest on clique lb (default, 0). Output: Size of maximum clique.
among these. A key element of 1: procedure M AX C LIQUE(G = (V, E), lb)
2:
max
lb
our exact algorithm is that dur3:
for i : 1 to n do
ing the search for the largest 4:
if d(vi ) max then. Pruning 1
clique containing a given vertex, 5:U;vertices that cannot form cliques 6:
for each vj 2 N (vi ) do
if j > i then. Pruning 2
larger than the current maxi- 7:
8:
if
d(v
)
max
then
. Pruning 3
jmum clique are pruned, in a hi9:
U
U
[
{v
j}
erarchical fashion. The method
C LIQUE(G, U, 1)
is outlined in detail in Algo- 10:rithm 1. Throughout, the vari- – Subroutine
able max stores the size of the 1: procedure C LIQUE(G = (V, E), U , size)
maximum clique found thus far. 2:
if U = ; thenif size > max thenInitially it is set to be equal to 3:
4:
max
size
the lower bound lb provided as
5:
returnan input parameter. It gives the6:while |U | > 0 do
maximum clique size when the7:
if size + |U |  max then. Pruning 4
algorithm terminates.
8:
return
To obtain the largest clique 9:
Select any vertex u from U
containing a vertex vi , it is suffi- 10:
U
U \ {u}N 0 (u) := {w|w 2 N (u) ^ d(w) max} .
cient to consider only the neigh- 11:
Pruning 5bors of vi . The main routine
12:
C LIQUE(G, U \ N 0 (u), size + 1)
M AX C LIQUE thus generates foreach vertex vi 2 V a set U ✓N (vi ) (neighbors of vi that survive pruning) and calls the subroutine C LIQUE on U .
The subroutine C LIQUE goes through every relevant clique containing vi in a recursive
fashion and returns the largest. We use size to maintain the size of the clique foundat any point through the recursion. Since we start with a clique of just one vertex, thevalue of size is set to one initially, when C LIQUE is called (Line 10, M AX C LIQUE).
Our algorithm consists of several pruning steps. Pruning 1 (Line 4, M AX C LIQUE)
filters vertices having strictly fewer neighbors than the size of the maximum clique already computed. These vertices can be ignored, since even if a clique were to be found,
its size would not be larger than max. While forming the neighbor list U for a vertex
vi , we include only those of vi ’s neighbors for which the largest clique containing themhas not been found (Pruning 2; Line 7, M AX C LIQUE), to avoid recomputing previously
found cliques. Pruning 3 (Line 8, M AX C LIQUE) excludes vertices vj 2 N (vi ) that havedegree less than the current value of max, since any such vertex could not form a cliqueof size larger than max. Pruning 4 (Line 7, C LIQUE) checks for the case where even if
all vertices of U were added to get a clique, its size would not exceed that of the largest
clique encountered so far in the search, max. Pruning 5 (Line 11, C LIQUE) reduces thenumber of comparisons needed to generate the intersection set in Line 12. Note that theroutine C LIQUE is similar to the Carraghan-Pardalos algorithm [9]; Pruning 5 accounts
for the main difference. Also, Pruning 4 is used in most existing algorithms, whereas
Prunings 1, 2, 3 and 5 are not.
3.2

The Heuristic

The exact algorithm examines Algorithm 2 Heuristic for finding the maximum clique
all relevant cliques contain- in a graph. Input: Graph G = (V, E). Output: Approxiing every vertex. Our heuristic, mate size of maximum clique.
shown in Algorithm 2, considers 1: procedure M AX C LIQUE H EU(G = (V, E))
only the maximum degree neigh- 2:
for i : 1 to n do
if d(vi ) max thenbor at each step instead of recur- 3:
U;sively considering all neighbors 4:
5:
for
each
vj 2 N (vi ) dofrom the set U , and thus is much6:
if d(vj ) max thenfaster.
3.3

Complexity

7:
8:

U
U [ {vj }C LIQUE H EU(G, U, 1)

The exact algorithm, Algorithm – Subroutine
1, examines for every vertex vi 1: procedure C LIQUE H EU(G = (V, E), U , size)
if U = ; thenall candidate cliques containing 2:
if size > max thenthe vertex vi in its search for the 3:
4:
max
size
largest clique. Its time complex5:
returnity is exponential in the worst 6:
Select a vertex u 2 U of maximum degree in G
case. The heuristic, Algorithm 7:
U
U \ {u}2, loops over the n vertices, each 8:
N 0 (u) := {w|w 2 N (u) ^ d(w) max}
time possibly calling the subrou- 9:
C LIQUE H EU(G, U \ N 0 (u), size + 1)
tine C LIQUE H EU, which effectively is a loop that runs until theset U is empty. Clearly, |U | is bounded by the max degree in the graph. The subroutine also includes the computation of a neighbor list, whose runtime is bounded byO( ). Thus, the time complexity of the heuristic is bounded by O(n · 2 ).

Table 1. Overview of real-world graphs in the testbed and their origins.
Graph
Description
cond-mat-2003 [26] A collaboration network of scientists posting preprints on
the condensed matter archive at www.arxiv.org in the period
email-Enron [23] A communication network representing email exchanges.
dictionary28 [4]Pajek network of words.
Fault 639 [14]A structural problem discretizing a faulted gas reservoir withtetrahedral Finite Elements and triangular Interface Elements.
audikw 1 [11]An automotive crankshaft model of TETRA elements.
bone010 [39]A detailed micro-finite element model of bones representing
the porous bone micro-architecture.
af shell [11]A sheet metal forming simulation network.
as-Skitter [23]An Internet topology graph from trace routes run daily in 2005.
roadNet-CA [23]A road network of California. Nodes represent intersections
and endpoints and edges represent the roads connecting them.
kkt power [11]An Optimal Power Flow (nonlinear optimization) network.

4

Experiments and Results

We present in this section results comparing the performance of our algorithm withthe algorithms of Carraghan-Pardalos [9], Östergȧrd algorithm [28], and Konc andJanezik [21]. We implemented the algorithm of [9] ourselves. For the algorithm of[28], we used the publicly available cliquer source code [27]. For the algorithm of[21], we used the code MaxCliqueDyn (MCQD, available at http://www.sicmm.
org/˜konc/maxclique/). Among the variants available in MCQD, we report resultson MCQD+CS (which uses improved coloring and dynamic sorting), since it is thebest-performing variant.
The experiments are performed on a Linux workstation running 64-bit Red Hat Enterprise Linux Server release 6.2 with a 2 GHz Intel Xeon E7540 processor. The codes
are implemented in C++ and compiled using gcc version 4.4.6 with -O3 optimization.
4.1 Test Graphs
Our testbed is grouped in three categories.
1. Real-world graphs Under this category, we consider 10 graphs (downloaded fromthe University of Florida Sparse Matrix Collection [11]) that originate from various
real-world applications. Table 1 gives a quick overview of the graphs and their origins.
2. Synthetic Graphs In this category we consider 15 graphs generated using the RMAT algorithm [10]. The graphs are subdivided in three categories depending on the
structures they represent.
A. Random graphs (5 graphs) – Erdős-Rényi random graphs generated using R-MAT
with the parameters (0.25, 0.25, 0.25, 0.25). Denoted with prefix rmat er.
B. Skewed Degree, Type 1 graphs (5 graphs) – graphs generated using R-MAT withthe parameters (0.45, 0.15, 0.15, 0.25). Denoted with prefix rmat sd1.
C. Skewed Degree, Type 2 graphs (5 graphs) – graphs generated using R-MAT withthe parameters (0.55, 0.15, 0.15, 0.15). Denoted with prefix rmat sd2.

Table 2. Structural properties (the number of vertices, |V |; edges, |E|; and the maximum degree,) of the graphs, G in the testbed: DIMACS Challenge graphs (upper left); UF Collection (lower
and middle left); RMAT graphs (right).

202
1,383
38
317
344

G
rmat sd1 1
rmat sd1 2
rmat sd1 3
rmat sd1 4
rmat sd1 5

|V |
|E|
131,072 1,046,384
262,144 2,093,552
524,288 4,190,376
1,048,576 8,382,821
2,097,152 16,767,728

bone010
af shell10
as-Skitter
roadNet-CA
kkt power

986,703 35,339,811
80
1,508,065 25,582,130
34
1,696,415 11,095,298 35,455
1,971,281 2,766,607
12
2,063,494 6,482,320
95

rmat sd2 1
rmat sd2 2
rmat sd2 3
rmat sd2 4
rmat sd2 5

131,072 1,032,634 2,980
262,144 2,067,860 4,493
524,288 4,153,043 6,342
1,048,576 8,318,004 9,453
2,097,152 16,645,183 14,066

rmat er 1
rmat er 2
rmat er 3
rmat er 4rmat er 5

131,072 1,048,515
262,144 2,097,104
524,288 4,194,254
1,048,576 8,388,540
2,097,152 16,777,139

hamming6-4
johnson8-4-4
keller4
c-fat200-5
brock200 2G
cond-mat-2003
email-Enron
dictionary28
Fault 639
audikw 1|V ||E|
31,163120,029
36,692
183,83152,652
89,038638,802 13,987,881
943,695 38,354,076

82
98
94
97
102

64
70
171
200
200

704
1,855
9,435
8,473
9,876

407
558
618
802
1,069

22
53
124
86
114

3. DIMACS graphs This last category consists of 5 graphs selected from the Second
DIMACS Implementation Challenge [20].
The DIMACS graphs are an established benchmark for the maximum clique problem, but they are of rather limited size and variation. In contrast, the real-work networks included in category 1 of the testset and the synthetic (RMAT) graphs in category 2 represent a wide spectrum of large graphs posing varying degrees of difficulty
for testing the algorithms. The rmat er graphs have normal degree distribution, whereas
the rmat sd1 and rmat sd2 graphs have skewed degree distributions and contain many
dense local subgraphs. The rmat sd1 and rmat sd2 graphs differ primarily in the magnitude of maximum vertex degree they contain; the rmat sd2 graphs have much higher
maximum degree. Table 2 lists basic structural information (the number of vertices,
number of edges and the maximum degree) about all 30 of the test graphs.
4.2 Results
Table 3 shows the size of the maximum clique (!) and the runtimes of our exact algorithm (Algorithm 1) and the algorithms of Caraghan and Pardalos (CP), Östergȧrd(cliquer) and Konc and Janežič (MCQD+CS) for all the graphs in the testbed. The lasttwo columns show the results of our heuristic (Algorithm 2)—the size of the maximum
clique returned and its runtime. The columns labeled P 1, P 2, P 3 and P 5 list the number of vertices/branches pruned in the respective pruning steps of Algorithm 1. Pruning
4 is omitted since it is used by all the algorithms compared in the table. These numbers
have been rounded (K stands for 103 , M for 106 and B for 109 ), although the exact
numbers can be found in the Appendix (Table 4).
In Table 3, the fastest runtime for each instance is indicated with boldface. An asterisk (*) indicates that an algorithm did not terminate within 25,000 seconds for aTable 3. Comparison of runtimes (in seconds) of algorithms [9] (CP), [28] (cliquer), [21](MCQD+CS) and our new exact algorithm (⌧A1 ) for the graphs in the testbed. P 1, P 2, P 3
and P 5 are the number of vertices/branches pruned in steps Pruning 1, 2, 3 and 5 of our exact
algorithm (K stands for 103 , M for 106 and B for 109 ). ! denotes the maximum clique size in thegraph, !A2 denotes the clique size returned by our heuristic and ⌧A2 shows its runtime.
⌧M CQD

Graph
cond-mat-2003
email-Enron
dictionary28
Fault 639
audikw 1
bone010
af shell10
as-Skitter
roadNet-CA
kkt power

!
25
20
26
18
36
24
15
67
4
11

⌧CP ⌧cliquer
4.875
11.17
7.005
15.08
7.700
32.74
14571.20 4437.14* 9282.49* 10002.67* 21669.96
24385.73*****

rmat er 1
rmat er 2
rmat er 3
rmat er 4rmat er 5

3
3
3
3
3

rmat sd1 1
rmat sd1 2
rmat sd1 3
rmat sd1 4
rmat sd1 5

2.41
3.70
7.69
-

⌧A1
0.011
0.998
<0.01
20.03
190.17393.1150.99
3838.36
0.44
2.26

P1 P2 P3
P5
29K 48K 6,527 17K
32K 155K 4,060
8M
52K 4,353 2,114 107
36 13M 126 1,116
4,101 38M 59K 721K
37K 34M 361K 44M
19 25M
75 2,105
1M 6M 981K 737M
1M 1M 370K 4,302
1M 4M 401K
2M

!A2
25
18
26
18
36
24
15
66
4
11

⌧A2
<0.01
0.261
<0.01
5.80
58.38
24.39
10.67
27.08
0.08
1.83

256.37215.181016.70865.184117.35 3456.39
16419.80 13894.52
*
*

49.79
-

0.38
0.78
1.87
4.16
9.87

780 1M 915 8,722
2,019 2M 2,351 23K
4,349 4M 4,960 50K
9,032 8M 10K 106K
18K 16M 20K 212K

3
3
3
3
3

0.12
0.24
0.49
1.44
2.57

6
6
6
6
6

225.93214.99912.44858.803676.14 3446.02
14650.40 13923.93
*
*

50.08
-

1.39
3.79
8.17
25.61
46.89

39K 1M 23K 542K
90K 2M 56K
1M
176K 4M 106K
2M
369K 8M 214K
5M
777K 16M 455K 12M

6
6
6
6
6

0.45
0.98
1.78
4.05
9.39

rmat sd2 1
rmat sd2 2
rmat sd2 3
rmat sd2 4
rmat sd2 5

26
35
39
43
N

427.41
213.234663.62851.84
13626.23 3411.14* 13709.52
*
*

48.17
242.20- 3936.55- 10647.84**

110K 853K 88K 614M
232K 1M 195K
1B
470K 3M 405K
1B
*
*
*
*
*
*
*
*

26
32.83
35
95.89
37 245.51
42 700.05
51 1983.21

hamming6-4
johnson8-4-4
keller4
c-fat200-5
brock200 2

4
14
11
58
12

<0.01
0.19
22.19
0.60
0.98

<0.01
<0.01
0.15
0.33
0.02

+CS

<0.01
<0.01
0.02
0.01
<0.01

<0.01
0.23
23.35
0.93
1.10

0 704
0 1,855
0 9,435
0 8,473
0 9,876

0
0
0
0
0

0
0
0
0
0

4
14
11
58
10

<0.01
<0.01
<0.01
0.04
<0.01

particular instance. A hyphen (-) indicates that the publicly available implementation(the MaxCliqueDyn code) had to be aborted because the input graph was too large forthe implementation to handle. Even for the instances for which the code eventually run
successfully, we had to first modify the graph reader to make it able to handle graphswith multiple connected components. For the graph rmat sd2 5, none of the algorithms
computed the maximum clique size in a reasonable time; the entry there is marked withN, standing for “Not Known”.
We discuss in what follows our observations from this table for the exact algorithm
and the heuristic.
Exact algorithms As expected, our exact algorithm gave the same size of maximum
clique as the other three algorithms for all test cases. In terms of runtime, its relative
performance compared to the other three varied in accordance with the advantages afforded by the various pruning steps.

Vertices that are discarded by Pruning 1 are skipped in the main loop of the algorithm, and the largest cliques containing them are not computed. Pruning 2 avoids
re-computing previously computed cliques in the neighborhood of a vertex. In the absence of Pruning 1, the number of vertices pruned by Pruning 2 would be bounded by
the number of edges in the graph (note that this is more than the total number of vertices
in the graph). While Pruning 3 reduces the size of the input set on which the maximum
clique is to be computed, Pruning 5 brings down the time taken to generate the intersection set in Line 12 of the subroutine. Pruning 4 corresponds to back tracking. Unlike
Pruning steps 1, 2, 3 and 5, Pruning 4 is used by all three of the other algorithms in ourcomparison. The primary strength of our algorithm is its ability to take advantage ofpruning in multiple steps in a hierarchical fashion, allowing for opportunities for one ormore of the steps to kick in and impact performance.
As a result of the differences seen in the effects of the pruning steps, as discussed
below, the runtime performance of our algorithm (seen in Table 3) compared to the otherthree algorithms varied in accordance with the difference in the structures represented
by the different categories of graphs in the testbed.
Real-world Graphs. For most of the graphs in this category, it can be seen that ouralgorithm runs several orders of magnitude faster than the other three, mainly due tothe large amount of pruning the algorithm enforced. These numbers also illustrate thegreat benefit of hierarchical pruning. For the graphs Fault 639, audikw 1 and af shell10,
there is only minimal impact by Prunings 1, 3 and 5, whereas Pruning 2 makes a big
difference resulting in impressive runtimes. The number of vertices pruned in steps
Pruning 1 and 3 varied among the graph within the category, ranging from 0.001% foraf shell to a staggering 97% for as-Skitter for the step Pruning 1.
Synthetic Graphs. For the synthetic graph types rmat er and rmat sd1, our algorithm clearly outperforms the other three by a few orders of magnitude in all cases. Thisis also primary due to the high number of vertices discarded by the new pruning steps.
In particular, for rmat sd1 graphs, between 30 to 37% of the vertices are pruned justin the step Pruning 1. For the rmat sd2 graphs, which have relatively larger maximum
clique and higher maximum degree than the rmat sd1 graphs, our algorithm is observed
to be faster than CP but slower than cliquer.
DIMACS Graphs. The runtime of our exact algorithm for the DIMACS graphs is
in most cases comparable to that of CP and higher than that of cliquer and MCQD+CS.
For these graphs, only Pruning 2 was found to be effective, and thus the performance
results agree with one’s expectation. We include in the Appendix timing results on alarger collection of DIMACS graphs.
It is to be noted that the DIMACS graphs are intended to serve as challenging test
cases for the maximum clique problem, and graphs with such high edge densities andlow vertex count are rare in practice. Most of these have between 20 to 1024 vertices
with an average edge density of roughly 0.6, whereas, most real world graphs are oftenvery large and sparse. Good examples are Internet topology graphs [13], the web graph[22], social network graphs [12], and the real-world graphs in our testbed.

The Heuristic It can be seen that our heuristic runs several orders of magnitude fasterthan our exact algorithm, while delivering either optimal or very close to optimal solution. It gave the optimal solution on 25 out of the 30 test cases. On the remaining
5 cases where it was suboptimal, its accuracy ranges from 83% to 99% (on average93%). Additionally, we run the heuristic by choosing a vertex randomly in Line 6 ofAlgorithm 2 instead of the one with the maximum degree. We observe that on average,
the solution is optimal only for less than 40% of the test cases compared to 83% whenselecting the maximum degree vertex.
Figure 1 provides an aggregated visual summary of the runtime trends of the various
algorithms across the five categories of graphs in the testbed.
Fig. 1. Runtime (normalized, mean)
comparison between various algorithms. For each category of graph,
first, all runtimes for each graphwere normalized by the runtime ofthe slowest algorithm for that graph,and then the mean was calculated foreach algorithm. Graphs were considered only if the runtimes for at least
three algorithms was less than the
25,000 seconds limit set.

To give a sense of runtime growth rates, we provide in Figure 2 plots of the runtimeof the new exact algorithm and the heuristic for the synthetic and real-world graphs inthe testbed. Besides the curves corresponding to the runtimes of the exact algorithm
and the heuristic, the figures also include a curve corresponding to the number of edges
in the graph divided by the clock frequency of the computing platform used in theexperiment. This curve is added to facilitate comparison between the growth rate of thealgorithms with that of a linear-time (in the size of the graph) growth rate. It can beseen that the runtime of the heuristic by and large grows somewhat linearly with thesize of a graph. The exact algorithm’s runtime, which is orders of magnitude larger thanthe heuristic, exhibited a similar growth behavior for these test-cases (even though its
worst-case complexity suggests exponential growth).

5

Conclusion

We presented a new exact and a new heuristic algorithm for the maximum clique problem. We performed extensive experiments on three broad categories of graphs comparing the performance of our algorithms to the algorithms due to Carraghan and Pardalos(CP) [9], Östergȧrd (cliquer) [28] and Konc and Janežič (MCQD+CS) [21]. For DIMACS benchmark graphs and certain dense synthetic graphs (rmat sd2), our new exact
algorithm performs comparably with the CP algorithm, but slower than cliquer and
MCQD+CS. For large sparse graphs, both synthetic and real-world, our new algorithm
runs several orders of magnitude faster than the other three. The heuristic, which runs
many orders of magnitude faster than our exact algorithm and the others, gave opti-

Fig. 2. Run time plots of the new exact and heuristic algorithms. The third curve, labeled edges,
shows the quantity, number of edges in the graph divided by the clock frequency of the computing
platform used in the experiment.

mal solution for 83% of the test cases, and when it is sub-optimal, its accuracy ranged
between 0.83 and 0.99.
In this work, we did not compare the performance of our algorithm against thosefor which an implementation is not publicly available such as [36, 25]. It would beinteresting to implement these and compare in future work. Further, the MCQD implementation uses an adjacency matrix, whereas our algorithm uses an adjacency list
to represent the graph. Although it is unlikely for the overall results to be drasticallydifferent with a change in the graph representation, it will be interesting to study towhat degree the performance will change with the change in graph representation. The
heuristic’s performance is impressive as presented; still it is worthwhile to comparewith other existing heuristics approaches such as [1, 17].

Acknowledgements
This work is supported in part by the following grants: NSF awards CCF-0833131,
CNS-0830927, IIS-0905205, CCF-0938000, CCF-1029166, and OCI-1144061; DOE
awards DE-FG02-08ER25848, DE-SC0001283, DE-SC0005309, DESC0005340, andDESC0007456; AFOSR award FA9550-12-1-0458. The work of Assefaw Gebremedhin is supported by the NSF award CCF-1218916 and by the DOE award DE-SC0010205.

References

1. D. Andrade, M. Resende, and R. Werneck, Fast local search for the maximum independent
set problem, Journal of Heuristics, 18 (2012), pp. 525–547.
2. J.G. Augustson and J. Minker, An analysis of some graph theoretical cluster techniques, J.
ACM 17 (1970), pp. 571–588.
3. L. Babel and G. Tinhofer, A branch and bound algorithm for the maximum clique problem,
Mathematical Methods of Operations Research 34 (1990), pp. 207–217.
4. V. Batagelj and A. Mrvar, Pajek datasets (2006), URL http://vlado.fmf.uni-lj.
si/pub/networks/data/.
5. V. Boginski, S. Butenko, and P.M. Pardalos, Statistical analysis of financial networks, Computational Statistics & Data Analysis 48 (2005), pp. 431–443.
6. I.M. Bomze, M. Budinich, P.M. Pardalos, and M. Pelillo, The Maximum Clique Problem, in
Handbook of Combinatorial Optimization, Kluwer Academic Publishers, 1999, pp. 1–74.
7. R.E. Bonner, On some clustering techniques, IBM J. Res. Dev. 8 (1964), pp. 22–32.
8. A.E. Brouwer, J.B. Shearer, N.J.A. Sloane, and W.D. Smith, A new table of constant weightcodes., IEEE Transactions on Information Theory (1990), pp. 1334–1380.
9. R. Carraghan and P. Pardalos, An exact algorithm for the maximum clique problem, Oper.
Res. Lett. 9 (1990), pp. 375–382.
10. D. Chakrabarti and C. Faloutsos, Graph mining: Laws, generators, and algorithms, ACM
Comput. Surv. 38 (2006).
11. T.A. Davis and Y. Hu, The university of florida sparse matrix collection, ACM Transactions
on Mathematical Software (TOMS) 38 (2011), pp. 1:1–1:25.
12. P. Domingos and M. Richardson, Mining the network value of customers, in Proc. of the 7th
ACM SIGKDD KDD’01, KDD ’01, San Francisco, California, ACM, New York, NY, USA,
2001, pp. 57–66.
13. M. Faloutsos, P. Faloutsos, and C. Faloutsos, On power-law relationships of the Internet
topology, in Proc. of the conference on Applications, technologies, architectures, and protocols for computer communication, SIGCOMM ’99, Cambridge, Massachusetts, UnitedStates, ACM, 1999, pp. 251–262.
14. M. Ferronato, C. Janna, G. Gambolati, Mixed constraint preconditioning in computational
contact mechanics, Computer Methods in Applied Mechanics and Engineering 197 (2008),
pp. 3922 – 3931.
15. S. Fortunato, Community detection in graphs, Physics Reports 486 (2010), pp. 75–174.
16. M.R. Garey and D.S. Johnson, W. H. Freeman & Co., New York, NY, USA 1979.
17. A. Grosso, M. Locatelli, and W. Pullan, Simple ingredients leading to very efficient heuristics
for the maximum clique problem, Journal of Heuristics, 14 (2008), pp. 587–612.
18. G. Gutin, Gross, J. L.; Yellen, J., Handbook of graph theory, Discrete Mathematics & Its
Applications, CRC Press 2004.
19. R. Horaud and T. Skordas, Stereo correspondence through feature grouping and maximal
cliques, IEEE Trans. Pattern Anal. Mach. Intell. 11 (1989), pp. 1168–1180.
20. D. Johnson and M.A. Trick, Editors, Cliques, coloring and satisfiability: Second dimacs
implementation challenge, DIMACS Series on Discrete Mathematics and Theoretical Computer Science 26 (1996).
21. J. Konc and D. Janežič, An improved branch and bound algorithm for the maximum clique
problem, MATCH Commun. Math. Comput. Chem., 2007, 58, pp. 569590.

22. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, Extracting Large-Scale Knowledge
Bases from the Web., in VLDB’99, 1999, pp. 639–650.
23. J. Leskovec, J. Kleinberg, and C. Faloutsos, Graphs over time: densification laws, shrinking
diameters and possible explanations, in Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, KDD ’05, Chicago, Illinois, USA,ACM, New York, NY, USA, 2005, pp. 177–187.
24. L. Leydesdorff, On the normalization and visualization of author co-citation data: Salton’scosine versus the jaccard index, J. Am. Soc. Inf. Sci. Technol. 59 (2008), pp. 77–85.
25. C.-M. Li and Z. Quan, An efficient branch-and-bound algorithm based on maxsat for the
maximum clique problem, 2010.
26. M.E.J. Newman, Coauthorship networks and patterns of scientific collaboration, Proceedings of the National Academy of Sciences of the United States of America 101 (2004), pp.
5200–5205.
27. S. Niskanen and P.R.J. Östergård, Cliquer user’s guide, version 1.0, Tech. Rep. T48, Communications Laboratory, Helsinki University of Technology, Espoo, Finland, 2003.
28. P.R.J. Östergård, A fast algorithm for the maximum clique problem, Discrete Appl. Math.
120 (2002), pp. 197–207.
29. G. Palla, I. Derenyi, I. Farkas, and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society, Nature 435 (2005), pp. 814–818.
30. P.M. Pardalos and J. Xue, The maximum clique problem, Journal of Global Optimization 4(1994), pp. 301–328.
31. M. Pavan and M. Pelillo, A new graph-theoretic approach to clustering and segmentation, in
Proc. of the 2003 IEEE computer society conference on Computer vision and pattern recognition, CVPR’03, Madison, Wisconsin, IEEE Computer Society, Washington, DC, USA,2003, pp. 145–152.
32. P. Prosser, Exact algorithms for maximum clique: A computational study, arXiv preprint
arXiv:1207.4616v1 (2012).
33. S. Sadi, S. Öğüdücü, and A.S. Uyar, An efficient community detection method using parallel
clique-finding ants, in Proc. of IEEE Congress on Evol. Comp, July, 2010, pp. 1–7.
34. P. San Segundo, D. Rodrı́guez-Losada, and A. Jiménez, An exact bit-parallel algorithm forthe maximum clique problem, Comput. Oper. Res. 38 (2011), pp. 571–581.
35. E. Tomita and T. Seki, An efficient branch-and-bound algorithm for finding a maximum
clique, in Proc. of the 4th international conference on Discrete mathematics and theoreticalcomputer science, Dijon, France, Springer-Verlag, Berlin, Heidelberg, 2003, pp. 278–289.
36. E. Tomita, Y. Sutani, T. Higashi, S. Takahashi, and M. Wakatsuki, A simple and fasterbranch-and-bound algorithm for finding a maximum clique, in WALCOM: Algorithms andComputation, M. Rahman and S. Fujita, eds., vol. 5942 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2010, pp. 191–203.
37. T. Matsunaga, C. Yonemori, E. Tomita, and M. Muramatsu, Clique-based data mining for
related genes in a biomedical database, BMC Bioinformatics 10 (2009), p. 205.
38. J. Turner, Almost all k-colorable graphs are easy to color, Journal of Algorithms 9 (1988),
pp. 63–82.
39. B. van Rietbergen, H. Weinans, R. Huiskes, and A. Odgaard, A new method to determine
trabecular bone elastic properties and loading using micromechanical finite-element models,
Journal of Biomechanics 28 (1995), pp. 69 – 81.
40. L. Wang, L. Zhou, J. Lu, and J. Yip, An order-clique-based approach for mining maximal
co-locations, Information Sciences 179 (2009), pp. 3370–3382.

Appendix

Table 4. P 1, P 2, P 3, P 4 and P 5 are the number of vertices pruned in steps Pruning 1, 2, 3, 4,
and 5 of Algorithm 1. An asterisk (*) indicates that the algorithm did not terminate within 25,000
seconds for that instance. ! denotes the maximum clique size.

G!

cond-mat-2003 25
email-Enron
20
dictionary28
26
Fault 639
18
audikw 1
36
bone01024
af shell1015
as-Skitter
67
roadNet-CA
4kkt power
11

P1

P2

P3

P4

P5

29,40748,0966,527
2,600
32,462
155,344
4,060
110,168
52,139
4,353
2,114
542
36 13,987,719
126 10,767,992
4,101 38,287,830 59,985 32,987,342
37,887 34,934,616 361,170 96,622,580
19 25,582,015
75 40,629,688
1,656,570 6,880,534 981,810 26,809,527
1,487,640 1,079,025 370,206
320,118
1,166,311 4,510,661 401,129 1,067,824

17,576
8,835,739
107
1,116
721,938
43,991,787
2,105
737,899,486
4,302
1,978,595

rmat er 1
rmat er 2
rmat er 3
rmat er 4rmat er 5

3
3
3
3
3

780 1,047,599
2,019 2,094,751
4,349 4,189,290
9,032 8,378,261
18,155 16,756,493

915
2,351
4,960
10,271
20,622

118,461
235,037
468,086
933,750
1,865,415

8,722
23,90850,741
106,200
212,838

rmat sd1 1
rmat sd1 2
rmat sd1 3
rmat sd1 4
rmat sd1 5

6
6
6
6
6

39,281 1,004,660 23,898
90,010 2,004,059 56,665
176,583 4,013,151 106,543
369,818 8,023,358 214,981
777,052 16,025,729 455,473

151,838
284,577
483,436
889,165
1,679,109

542,245
1,399,314
2,677,437
5,566,602
12,168,698

rmat sd2 1
rmat sd2 2
rmat sd2 3
rmat sd2 4
rmat sd2 5

26
35
39
43
N

110,951
232,352
470,302**

hamming6-4
johnson8-4-4
keller4
c-fat200-5
brock200 2

4
14
11
58
12

0
0
0
0
0

853,116 88,424 1,067,824 614,813,037
1,645,086 195,427 81,886,879 1,044,068,886
3,257,233 405,856 45,841,352 1,343,563,239
*
*
*
*
*
*
*
*
704
1855
9435
8473
9876

0
0
0
0
0

583
136,0078,834,190
70449
349,42700
0
00Table 5. Comparison of runtimes of algorithms [9] (CP), [28] (cliquer) and [21] (MCQD+CS)
with that of our new exact algorithm (⌧A1 ) for DIMACS graphs. An asterisk (*) indicates thatthe algorithm did not terminate within 10,000 seconds for that instance. ! denotes the maximum
clique size, !A2 the maximum clique size found by our heuristic and ⌧A2 , its runtime.
⌧M CQDG|V ||E| !
brock200 1
200 14,834 21
brock200 2
2009,876 12brock200 3
200 12,048 15
brock200 4
200 13,089 17
c-fat200-1
200
1,534 12c-fat200-2
200
3,235 24c-fat200-52008,473 58
c-fat500-1
500
4,459 14c-fat500-2
500
9,139 26
c-fat500-5
500 23,191 64
hamming6-2
64
1,824 32
hamming6-4
64704
4
hamming8-2
256 31,616 128
hamming8-4
256 20,864 16
hamming10-2 1,024 518,656 512
johnson8-2-4
28210
4
johnson8-4-4
70
1,855 14johnson16-2-4 120
5,460
8keller4
171
9,435 11MANN a945
918 16MANN a27378 70,551 126
p hat300-1
300 10,933
8
p hat300-2
300 21,928 25
p hat500-1
500 31,569
9
p hat500-2
500 62,946 36
p hat700-1
700 60,999 11
p hat1000-1
1,000 122,253 10
san200 0.7 1
200 13,930 30⌧CP ⌧cliquer
*
10.37
0.98
0.02
14.09
0.16
60.25
0.7
<0.01 <0.01<0.01 <0.01
0.6
0.33<0.01 <0.01
0.02 <0.01
3.07 <0.01
0.68 <0.01<0.01 <0.01*
0.01* <0.01*
0.31<0.01 <0.01
0.19 <0.01
20.95
0.04
22.19
0.15
1.73 <0.01
*
*
0.14
0.01
831.52
0.32
2.38
0.07
* 159.96
12.7
0.12
97.39
1.33
*
0.99

⌧A1
0.75
*
0.01
1.1
0.03 14.86
0.12 65.78<0.01 <0.01<0.01 <0.01
0.01
0.93
<0.01 <0.01
0.01
0.01
<0.01
*
<0.01
0.33
<0.01 <0.01
0.01
*
0.1
*
*
<0.01 <0.01
<0.01
0.23
0.42 22.07
0.02 23.35
<0.01
2.5
3.3
*
<0.01
0.14
0.03 854.59
0.04
2.44
1.2
*
0.13 12.73
0.41 98.48
<0.01
*
+CS

!A2 ⌧A2
18 0.02
10 <0.01
12 <0.01
14 <0.01
12 <0.01
24 <0.01
58 0.04
14 <0.01
26 0.01
64 0.1132 <0.01
4 <0.01
128 0.67
16 0.03512 95.24
4 <0.01
14 <0.01
8 <0.01
11 <0.01
16 <0.01
125 1.74
8 <0.01
24 0.03
9 0.0234 0.14
9 0.04
10 0.11
16 0.01