Abstract
This paper introduces Phased Local Search (PLS), a new stochastic reactive dynamic local search algorithm for the maximum clique problem. (PLS) interleaves sub-algorithms which alternate between sequences of iterative improvement, during which suitable vertices are added to the current clique, and plateau search, where vertices of the current clique are swapped with vertices not contained in the current clique. The sub-algorithms differ in their vertex selection techniques in that selection can be solely based on randomly selecting a vertex, randomly selecting within highest vertex degree or randomly selecting within vertex penalties that are dynamically adjusted during the search. In addition, the perturbation mechanism used to overcome search stagnation differs between the sub-algorithms. (PLS) has no problem instance dependent parameters and achieves state-of-the-art performance for the maximum clique problem over a large range of the commonly used DIMACS benchmark instances.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Balus E, Yu C (1986) Finding a maximum clique in an arbitary graph. SIAM J Comp 15(4):1054–1068
Battiti R, Protasi M (2001) Reactive local search for the maximum clique problem. Algorithmica 29:610–637
Bomze I, Budinich M, Pardalos P, Pelillo M (1999) The maximum clique problem. In: Du DZ, P.P. (ed) Handbook of Combinatorial Optimization, vol. A, pp 1–74
Boppana R, Halldórsson M (1992). Approximating maximum independent sets by excluding subgraphs. Bit 32:180–196
Brockington M, Culberson J (1996) Camouflaging independent sets in quasi-random graphs. In: Johnson DS, M. T. (ed) Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge, vol. 26 of DIMACS Series. American Mathematical Society
Busygin S (2002) A new trust region technique for the maximum clique problem. Internal report, http://www.busygin.dp.ua.
Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of \(\mathcal{NP}\)-Completeness. Freeman, San Francisco, CA, USA
Grosso A, Locatelli M, Croce FD (2004) Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem. J. Heur 10:135–152
Grosso A, Locatelli M, Pullan W (2005) Randomness, plateau search, penalties, restart rules: simple ingredients leading to very efficient heuristics for the maximum clique problem. J. Heur (submitted)
Hansen P, Mladenović N, Urosević D (2004) Variable neighborhood search for the maximum clique. Disc Appl Math 145:117–125
Håstad J (1999). Clique is hard to approximate within n 1−c. Acta Math 182:105–142
Ji Y, Xu X, Stormo GD (2004) A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences. Bioinformatics 20(10):1591–1602.
Johnson D, Trick M (Eds) (1996) Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge, Vol. 26 of DIMACS Series. American Mathematical Society
Katayama K, Hamamoto A, Narihisa H (2004) Solving the maximum clique problem by k-opt local search. In: Proceedings of the 2004 ACM Symposium on Applied Computing, pp 1021–1025
Marchiori, E (2002). Genetic, iterated and multistart local search for the maximum clique problem. In Applications of Evolutionary Computing, vol. 2279 of Lecture Notes in Computer Science, pp 112–121. Springer Verlag, Berlin, Germany
Pevzner PA, Sze S-H (2000) Combinatorial approaches to finding subtle signals in DNA sequences. In: Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology, AAAI Press, pp 269–278
Pullan W, Hoos H (2006) Dynamic local search for the maximum clique problem. J Arti Intel Res 25:159–185
Resende M, Feo T, Smith S (1998). Algorithm 786: FORTRAN subroutine for approximate solution of the maximum independent set problem using GRASP. ACM Trans Math Soft 24:386–394
Wolpert D, Macready G (1997) No free lunch theorems for optimization. IEEE Trans Evolut Comp 1:67–82
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pullan, W. Phased local search for the maximum clique problem. J Comb Optim 12, 303–323 (2006). https://doi.org/10.1007/s10878-006-9635-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-006-9635-y