Abstract
In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (J Heuristics 18(4):525–547, 2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.
Similar content being viewed by others
References
Andrade, D.V., Resende, M.G.C., Werneck, R.F.: Fast local search for the maximum independent set problem. J. Heuristics 18(4), 525–547 (2012). doi:10.1007/s10732-012-9196-4
Balas, E., Yu, C.S.: Finding a maximum clique in an arbitrary graph. SIAM J. Comput. 15(4), 1054–1068 (1986)
Bertoni, A., Campadelli, P., Grossi, G.: A discrete neural algorithm for the maximum clique problem: analysis and circuit implementation. In: Proceedings of Workshop on Algorithm, Engineering, WAE’97, pp. 84–91 (1997)
Boginski, V., Butenko, S., Pardalos, P.M.: On structural properties of the market graph. In: Nagurney, A. (ed.) Innovations in Financial and Economic Networks, pp 29–45. Edward Elgar Publishing, London (2003)
Bomze, I., Budinich, M., Pardalos, P.M., Pelillo, M.: The Maximum Clique Problem. Handbook of Combinatorial Optimization. Kluwer, Dordrecht (1999)
Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973). doi:10.1145/362342.362367
Brouwer, A., Shearer, J., Sloane, N., Smith, W.: A new table of constant weight codes. IEEE Trans. Inf. Theory 36(6), 1334–1380 (1990). doi:10.1109/18.59932
Butenko, S., Wilhelm, W.E.: Clique-detection models in computational biochemistry and genomics. Eur. J. Oper. Res. 173(1), 1–17 (2006). doi:10.1016/j.ejor.2005.05.026
Carraghan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6), 375–382 (1990). doi:10.1016/0167-6377(90)90057-C
Du, D., Pardalos, P.M.: Handbook of Combinatorial Optimization, Supplement vol A, p. 648. Springer, Berlin (1999)
Fahle, T.: Simple and fast: improving a branch-and-bound algorithm for maximum clique. In: Proceedings of the 10th Annual European Symposium on Algorithms (ESA ’02), pp 485–498. Springer, London, UK (2002)
Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Glob. Optim. 6(2), 109–133 (1995). doi:10.1007/BF01096763
Funabiki, N., Takefuji, Y., Lee, K.C.: A neural network model for finding a near-maximum clique. J. Parallel Distrib. Comput. 14(3), 340–344 (1992). doi:10.1016/0743-7315(92)90072-U
Glover, F., Laguna, M.: Tabu Search. Kluwer, Dordrecht (1997)
Grosso, A., Locatelli, M., Pullan, W.: Simple ingredients leading to very efficient heuristics for the maximum clique problem. J. Heuristics 14(6), 587–612 (2008). doi:10.1007/s10732-007-9055-x
Jenelius, E., Petersen, T., Mattsson, L.: Importance and exposure in road network vulnerability analysis. Transp. Res. Part A: Policy Pract. 40(7), 537–560 (2006). doi:10.1016/j.tra.2005.11.003
Jerrum, M.: Large cliques elude the metropolis process. Random Struct. Algorithms 3(4), 347–359 (1992). doi:10.1002/rsa.3240030402
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)
Konc, J., Janezic, D.: An improved branch and bound algorithm for the maximum clique problem. MATCH Commun. Math. Comput. Chem. 58, 569–590 (2007)
Kopf, R., Ruhe, G.: A computational study of the weighted independent set problem for general graphs. Found. Control Eng. 12, 167–180 (1987)
Li, C.M., Quan, Z.: Combining graph structure exploitation and propositional reasoning for the maximum clique problem. In: Proceedings of the 2010 22nd IEEE International Conference on Tools with Artificial Intelligence—Volume 01 (ICTAI’10), pp 344–351. IEEE, Arras, France (2010a)
Li, C.M., Quan, Z.: An efficient branch-and-bound algorithm based on maxsat for the maximum clique problem. In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), pp. 128–133. AAAI Press, Atlanta, USA (2010b)
Marchiori, E.: Genetic, iterated and multistart local search for the maximum clique problem. In: Applications of Evolutionary Computing, Springer, LNCS, pp. 112–121. Springer, Berlin (2002)
Matula, D.W., Marble, G., Isaacson, J.D.: Graph coloring algorithms. In: Read, R.C. (ed.) Graph Theory and Computing, pp 109–122. Academic Press, New York (1972)
Mycielski, J.: Sur le coloriage des graphes. Colloq. Math. 3, 161–162 (1955)
Pullan, W., Hoos, H.H.: Dynamic local search for the maximum clique problem. J. Artif. Int. Res. 25(1), 159–185 (2006)
Singh, A., Gupta, A.K.: A hybrid heuristic for the maximum clique problem. J. Heuristics 12(1–2), 5–22 (2006). doi:10.1007/s10732-006-3750-x
Sloane, N.J.A.: Unsolved problems in graph theory arising from the study of codes. Graph Theory Notes NY 18(11), 11–20 (1989)
Tomita, E., Kameda, T.: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Glob. Optim. 37(1), 95–111 (2007)
Tomita, E., Seki, T.: An efficient branch-and-bound algorithm for finding a maximum clique. In: Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science (DMTCS’03), pp. 278–289. Springer, Berlin, Heidelberg (2003)
Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., Wakatsuki, M.: A simple and faster branch-and-bound algorithm for finding a maximum clique. In: Proceedings of the 4th International Conference on Algorithms and Computation (WALCOM’10), pp. 191–203. Springer, Berlin, Heidelberg (2010). doi: 10.1007/978-3-642-11440-3_18
Acknowledgments
The authors would like to thank professor Mauricio Resende and his co-authors for the source code of their powerful ILS heuristic. We are also thankful to Chu-Min Li and Zhe Quan for the source code of their efficient MAXSAT algorithm. The authors are supported by LATNA Laboratory, National Research University Higher School of Economics (NRU HSE), Russian Federation government grant, ag. 11.G34.31.0057. Mikhail Batsyn is supported by Federal Grant-in-Aid Program “Research and development on priority directions of development of the scientific-technological complex of Russia for 2007–2013” (Governmental Contract No. 14.514.11.4065).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Maslov, E., Batsyn, M. & Pardalos, P.M. Speeding up branch and bound algorithms for solving the maximum clique problem. J Glob Optim 59, 1–21 (2014). https://doi.org/10.1007/s10898-013-0075-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-013-0075-9