A New Effective Local Search Heuristic for the Maximum Clique Problem

Authors: S. Balaji

Abstract:

An edge based local search algorithm, called ELS, is proposed for the maximum clique problem (MCP), a well-known combinatorial optimization problem. ELS is a two phased local search method effectively £nds the near optimal solutions for the MCP. A parameter ’support’ of vertices de£ned in the ELS greatly reduces the more number of random selections among vertices and also the number of iterations and running times. Computational results on BHOSLIB and DIMACS benchmark graphs indicate that ELS is capable of achieving state-of-the-art-performance for the maximum clique with reasonable average running times.

Keywords: Maximum clique, local search, heuristic, NP-complete.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1087856

References:

[1] S. Lin, B. W. Kernighan, An effective heuristic algorithm for traveling salesman problem, Oper. Res. 21 (1973) 498-516.
[2] B. W. Kernighan, S. Lin, An ef£cient heuristic procedure for partitioning graphs, Bell System Techn. J. 49 (1970) 291-307.
[3] K. Katayama, H. Narihisa, Iterated local search approach using genetic transformation to the traveling salesman problem, Proceedings of the Genetic and Evolutionary Computation Conference, (1999) 321-328
[4] D. Applegate, W. Cook, A. Rohe, Chained Lin-Kernighan for large traveling salesman problems, Informs Journal of Computing, 15(1) (2003) 82-92.
[5] P. Merz, B. Freisleben, Memetic algorithms for the traveling salesman problem, Complex Systems, 13(4) (2001) 297-345.
[6] P. Merz, B. Freisleben, Fitness landscapes, memetic algorithms and greedy operators for graph partitioning, Evolutionary Computing, 8(1) (2000) 61-91.
[7] M. Yaguira, T. Yamaguchi, T. Ibaraki, A variable depth search algorithm for the generalized assignment problem, in S. Voss, S. Martello, I. H. Osman, C. Roucairol(Eds.), Meta-Heuristics: Advance and Trends in Local Search Paradigms for Optimization, Kluwer, Dordrecht, (1999) 459-471.
[8] P. Merz, K. Katayama, Memetic algorithms for the unconstrained binary quadratic programming problem, Biosystems, 78(1-3) (2004) 99-118.
[9] K. Katayama, A. Hamamoto, H. Nirihisa, An effective local search for the maximum clique problem, Information Processing Letters, 95 (2005) 503-511.
[10] W. Pullan, Phased local search for the maximum clique problem, J. Comb. Optim. 12 (2006) 303-323.
[11] D. S. Johnson, M. A. Trick (Eds.): Cliques, Coloring and sats£ability, Second DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 26, American Mathematical Society, Providence, RI, 1996.
[12] P. A. Pevzner, S.-H. Sze, Combinatorial approaches to £nding subtle signals in DNA sequences, in proceedings of Eighth International Conference on intelligent systems for Molecular Biology, AIAA Press, New York, (2000) 269-278.
[13] Y. Ji, X. Xu, G. D. Stormo, A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences. Bioinformatics 20(10) (2004) 1591-1602.
[14] M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to the theory NP - completeness. San Francisco: Freeman (1979).
[15] J. Hastad: Clique is hard to approximate within n1- , Acta Mathematica, 182 (1999) 105-142.
[16] R. Boppana, M. Halldorsson, Approximating maximum independent sets by excluding subgraphs. Bit 32 (1992) 180-196.
[17] X. Geng, J. Xu, J. Xiao and L. Pan: A simple simulated annealing algorithm for the Maximum Clique problem”, 177 (2007) 5064-5071.
[18] E. Tomita, T. Kameda, An ef£cient branch-and-bound algorithm for £nding a maximum clique with computational experiments, J. Glob. Optim. 37 (2007) 95-111.
[19] P. R. J. Ostergard: A fast algorithm for the maximum clique problem, Discrete Applied Mathematics, 120 (2002) 197-207.
[20] E. Balas, W. Niehaus, Optimized crossover-Based Genetic Algorithm for the Maximum Cardinality and Maximum Weight Clique Problems, Journal of Heuristics, 4 (1998) 107-122.
[21] S. Busygin, A new trust region technique for the maximum weight clique problem, Discrete Applied Mathematics, 154 (2006) 2080-2096.
[22] G. -Marin, E. -Casermeiro, J. -Perez, Modelling competitive Hop£eld networks for the maximum clique problem, Computers & Operations Research, 30 (2003) 603-624.
[23] W. Pullan, H. H. Hoos, Dynamic local search for the maximum clique problem, Journal of Arti£cial Intelligence Research, 25 (2006) 159-185.
[24] W. Pullan, Approximating the maximum vertex/edge weighted clique using local search, J. Heuristics, 14 (2008) 117-134.
[25] P. J. Taillon, A new approach for solving the maximum clique problem, LNCS, Springer-Verlag Berlin Heidelberg, 4041 (2006) 279-290.
[26] V. C. Barbosa, C. D. Campos, A novel evolutionary formulation of the maximum independent set problem, J. Comb. Optim. 8 (2004) 419-437.
[27] B. Alidaee, G. Kochenberger, H. Wang, Simple and fast surrogate constraint heuristics for the maximum independent set problem, J. Heuristics, 14 (2008) 571-585.
[28] T. S. Feo, M. G. C. Resende, S. H. Smith, A greedy randomized adaptive search procedure for maximum independent set, Operations Research, 42(5) (1994) 860-978.
[29] S. Balaji, V. Swaminathan, K. Kannan: Approximating maximum weighted independent set using vertex Support, International Journal of Computational and Mathemtical Sciences1, 3(8) (2009) 406-411.
[30] S. Balaji, N. Revathi: An Ef£cient approach for the Optimization version of Maximum Weighted Clique Problem, WSEAS Transactions on Mathematics, 11(9) (2012) 773-783.