Abstract
In this work, the NP-hard maximum clique problem on graphs is considered. Starting from basic greedy heuristics, modifications and improvements are proposed and combined in a two-phase heuristic procedure. In the first phase an improved greedy procedure is applied starting from each node of the graph; on the basis of the results of this phase a reduced subset of nodes is selected and an adaptive greedy algorithm is repeatedly started to build cliques around such nodes. In each restart the selection of nodes is biased by the maximal clique generated in the previous execution. Computational results are reported on the DIMACS benchmarks suite. Remarkably, the two-phase procedure successfully solves the difficult Brockington-Culberson instances, and is generally competitive with state-of-the-art much more complex heuristics.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Battiti, R. and M. Protasi. (2001). “Reactive Local Search for the Maximum Clique Problem.” Algorithmica 29(4), 610–637.
Bellare, M., O. Goldreich, and M. Sudan. (1998). “Free Bits, PCPs, and Nonapproximability-Towards Tight Results.” SIAM Journal on Computing 27(3), 804–915.
Bomze, I.M., M. Budinich, P.M. Pardalos, and M. Pelillo. (1999). “The Maximum Clique Problem.” In D.Z. Du and P.M. Pardalos (eds.), Handbook of Combinatorial Optimization, Suppl. vol. A, pp. 1-74.
Brockington, M. and J.C. Culberson. (1996). “Camouflaging Independent Sets in Quasi-Random Graph.” In Johnson and Trick.
Burer, S., R.D.C. Monteiro, and Y. Zhang. (2002). “Maximum Stable Set Formulations and Heuristics Based on Continous Optimization.” Mathematical Programming 94, 137–166.
Busygin, S. (2002a). “A New Trust Region Technique for the Maximum Clique Problem.” Report submitted, available at http://www.busygin.dp.ua.
Busygin, S. (2002b). “A Simple Clique Camouflaging Against Greedy Maximum Clique Heuristics.” Report available at http://www.busygin.dp.ua.
Busygin, S., S. Butenko, and P.M. Pardalos. (2002). “A Heuristic for the Maximum Independent Set Problem Based on Optimization of a Quadratic Over a Sphere.” Journal of Combinatorial Optimization 21(4), 111–137.
Feo, T.A., M.G.C. Resende, and S.M. Smith. (1994) “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set.” Operations Research 46(5), 860–878.
Garey, M. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co.
Jagota, A. and L.A. Sanchis. (2001). “Adaptive, Restart, Randomized Greedy Heuristics for Maximum Clique.” Journal of Heuristics 7, 565–585.
Johnson, D.S. and M. Trick (eds.). (1996). “Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge.” DIMACS Series, vol. 26, American Mathematical Society.
Motzkin, R.S. and E.G. Straus. (1965). “Maxima for Graphs and a New Poof of a Theorem of Turan.” Canadian Journal of Mathematics 17(4), 533–540.
Östergard, P.R.J. (2002). “A Fast Algorithm for the Maximum Clique Problem.” Discrete Applied Mathematics 120, 197–207.
Resende, M.G.C., T.A. Feo, and S.H. Smith. (1998). “Algorithm 786: FORTRAN Subroutines for Approximate Solution of the Maximum Independent Set Problem Using GRASP.” ACM Transactions on Mathematical Software 24, 386–394.
Sanchis, L. and A. Jagota. (1996). “Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem.” INFORMS Journal on Computing 8(2), 87–102.
Wood, D.R. (1997). “An Algorithm for Finding a Maximum Clique in a Graph.” Operations Research Letters 21(5), 211–217.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Grosso, A., Locatelli, M. & Croce, F.D. Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem. Journal of Heuristics 10, 135–152 (2004). https://doi.org/10.1023/B:HEUR.0000026264.51747.7f
Issue Date:
DOI: https://doi.org/10.1023/B:HEUR.0000026264.51747.7f