An adaptive multistart tabu search approach to solve the maximum clique problem. (English) Zbl 1275.90084

Summary: Given an undirected graph \(G=(V,E)\) with vertex set \(V={1,\dots,n}\) and an edge set \(E\subseteq V\times V\). The maximum clique problem is to determine in \(G\) a clique (i.e. a complete subgraph) of maximum cardinality. This paper presents an effective algorithm for the maximum clique problem. The proposed multistart tabu search algorithm integrates a constrained neighborhood, a dynamic tabu tenure mechanism and a long term memory based restart strategy. Our proposed algorithm is evaluated on the whole set of 80 DIMACS challenge benchmarks and compared with five state-of-the-art algorithms. Computational results show that our proposed algorithm attains the largest known clique for 79 benchmarks.


90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI


[1] Balas E, Yu CS (1986) Finding a maximum clique in an arbitrary graph. SIAM J Comput 15(4):1054-1068 · Zbl 0604.05024
[2] Barbosa V, Campos L (2004) A novel evolutionary formulation of the maximum independent set problem. J Comb Optim 8(4):419-437 · Zbl 1079.90145
[3] Battiti R, Mascia F (2010) Reactive and dynamic local search for max-clique: engineering effective building blocks. Comput Oper Res 37(3):534-542 · Zbl 1173.90586
[4] Battiti R, Protasi M (2001) Reactive local search for the maximum clique problem. Algorithmica 29(4):610-637 · Zbl 0985.68016
[5] Bui, T.; Eppley, P., A hybrid genetic algorithm for the maximum clique problem, 478-484 (1995)
[6] Busygin S, Butenko S, Pardalos PM (2002) A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere. J Comb Optim 6(3):287-297 · Zbl 1046.90071
[7] Busygin S (2006) A new trust region technique for the maximum weight clique problem. Discrete Appl Math 154(1):2080-2096 · Zbl 1111.90020
[8] Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper Res Lett 9:375-382 · Zbl 0711.90080
[9] Fleurent, C.; Ferland, J.; Johnson, D. (ed.); Trick, M. (ed.), Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability, No. 26, 619-652 (1996), Providence · Zbl 0864.90118
[10] Friden C, Hertz A, de Werra D (1989) Stabulus: A technique for finding stable sets in large graphs with tabu search. Computing 42:35-44 · Zbl 0685.68056
[11] Galinier P, Hao JK (1999) Hybrid evolutionary algorithms for graph coloring. J Comb Optim 3(4):379-397 · Zbl 0958.90071
[12] Gendreau M, Soriano P, Salvail L (1993) Solving the maximum clique problem using a tabu search approach. Ann Oper Res 41:385-403 · Zbl 0775.90297
[13] Glover F, Laguna M (1997) Tabu search. Kluwer Academic, Norwell · Zbl 0930.90083
[14] Grosso A, Locatelli M, Pullan W (2008) Simple ingredients leading to very efficient heuristics for the maximum clique problem. J Heuristics 14(6):587-612 · Zbl 1173.90565
[15] Johnson DS, Trick MA (1996) Second DIMACS implementation challenge: cliques, coloring and satisfiability. DIMACS series in discrete mathe-matics and theoretical computer science, vol 26. Am. Math. Soc., Providence · Zbl 0851.00080
[16] Karp, RM; Miller, RE (ed.); Thatcher, JW (ed.), Reducibility among combinatorial problems, 85-103 (1972), New York
[17] Katayama K, Hamamoto A, Narihisa H (2005) An effective local search for the maximum clique problem. Inf Process Lett 95(5):503-511 · Zbl 1185.68283
[18] Marchiori, E., A simple heuristic based genetic algorithm for the maximum clique problem, 366-373 (1998)
[19] Marchiori, E., Genetic, iterated and multistart local search for the maximum clique problem, No. 2279, 112-121 (2002) · Zbl 1044.68780
[20] Östergärd PJR (2002) A fast algorithm for the maximum clique problem. Discrete Appl Math 120:195-205 · Zbl 1019.05054
[21] Pardalos PM, Xue J (2002) The maximum clique problem. J Glob Optim 4:301-328 · Zbl 0797.90108
[22] Pullan W (2006) Phased local search for the maximum clique problem. J Comb Optim 12(3):303-323 · Zbl 1255.90122
[23] Pullan W, Hoos HH (2006) Dynamic local search for the maximum clique problem. J Artif Intell Res 25:159-185 · Zbl 1182.68065
[24] Rebennack S, Oswald M, Theis DO, Seitz H, Reinelt G, Pardalos PM (2011) A Branch and Cut solver for the maximum stable set problem. J Comb Optim 21(4):434-457 · Zbl 1319.90079
[25] Singh A, Gupta AK (2008) A hybrid heuristic for the maximum clique problem. J Heuristics 12:5-22 · Zbl 1122.90070
[26] Tomita E, Seki T (2003) An efficient branch-and-bound algorithm for finding a maximum clique. Discrete Math Theor Comput Sci 2731:278-289 · Zbl 1038.68565
[27] Zhang QF, Sun JY, Tsang E (2005) Evolutionary algorithm with the guided mutation for the maximum clique problem. IEEE Trans Evol Comput 9(2):192-200
[28] Wu Q, Hao JK (2012a) Coloring large graphs based on independent set extraction. Comput Oper Res 39(2):283-290 · Zbl 1250.05007
[29] Wu Q, Hao JK (2012b) An effective heuristic algorithm for sum coloring of graphs. Comput. Oper. Res. 39(7):1593-1600. doi:10.1016/j.cor.2011.09.010 · Zbl 1250.05114
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.