×

Incremental upper bound for the maximum clique problem. (English) Zbl 1528.05052

Summary: The maximum clique problem (MaxClique for short) consists of searching for a maximum complete subgraph in a graph. A branch-and-bound (BnB) MaxClique algorithm computes an upper bound of the number of vertices of a maximum clique at every search tree node, to prune the subtree rooted at the node. Existing upper bounds are usually computed from scratch at every search tree node. In this paper, we define an incremental upper bound, called IncUB, which is derived efficiently from previous searches instead of from scratch. Then, we describe a new BnB MaxClique algorithm, called IncMC2, which uses graph coloring and MaxSAT reasoning to filter out the vertices that do not need to be branched on, and uses IncUB to prune the remaining branches. Our experimental results show that IncMC2 is significantly faster than algorithms such as BBMC and IncMaxCLQ. Finally, we carry out experiments to provide evidence that the performance of IncMC2 is due to IncUB.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
90C35 Programming involving graphs or networks
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

MaxCliqueDyn
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Benlic U, Hao JK (2013) Breakout local search for maximum clique problems. Comput. Oper. Res. 40(1):192-206.Crossref, Google Scholar · Zbl 1349.90005 · doi:10.1016/j.cor.2012.06.002
[2] Berman P, Pelc A (1990) Distributed probabilistic fault diagnosis for multiprocessor systems. Proc. 20th Annual Internat. Sympos. Fault-Tolerant Comput., FTCS ’90 (IEEE Computer Society, Washington, DC), 340-346.Google Scholar
[3] Cai S, Su K, Sattar A (2011) Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artificial Intelligence 175(9):1672-1696.Crossref, Google Scholar · Zbl 1225.68242 · doi:10.1016/j.artint.2011.03.003
[4] Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6):375-382.Crossref, Google Scholar · Zbl 0711.90080 · doi:10.1016/0167-6377(90)90057-C
[5] Fahle T (2002) Simple and fast: Improving a branch-and-bound algorithm for maximum clique. Di Battista G, Zwick U, eds. Proc. 11th Annual Eur. Sympos. Algorithms, ESA ’03 (Springer, Berlin), 485-498.Google Scholar · Zbl 1019.90517
[6] 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.Crossref, Google Scholar · Zbl 1173.90565 · doi:10.1007/s10732-007-9055-x
[7] Konc J, Janezic D (2007) An improved branch and bound algorithm for the maximum clique problem. Comm. Math. Comput. Chemistry 58:569-590.Google Scholar · Zbl 1274.05452
[8] Li CM, Quan Z (2010a) Combining graph structure exploitation and propositional reasoning for the maximum clique problem. Proc. 22nd IEEE Internat. Conf. Tools with Artificial Intelligence, ICTAI ’10, Vol. 1 (IEEE Computer Society, Washington, DC), 344-351.Google Scholar
[9] Li CM, Quan Z (2010b) An efficient branch-and-bound algorithm based on maxsat for the maximum clique problem. Proc. 24th AAAI Conf. Artificial Intelligence, AAAI ’10 (AAAI Press, Menlo Park, CA), 128-133.Google Scholar
[10] Li CM, Fang Z, Xu K (2013) Combining MaxSAT reasoning and incremental upper bound for the maximum clique problem. Proc. 25th IEEE Internat. Conf. Tools with Artificial Intelligence, ICTAI ’13 (IEEE Computer Society, Washington, DC), 939-946.Google Scholar
[11] Li CM, Jiang H, Xu R-C (2015) Incremental MaxSAT reasoning to reduce branches in a branch-and-bound algorithm for MaxClique. Dhaenens C, Jourdan L, Marmion M-E, eds. Proc. 9th Internat. Conf. Learn. Intelligent Optim., LION 9 (Springer International, Cham, Switzerland), 268-274.Google Scholar
[12] Li CM, Zhu Z, Manyà F, Simon L (2011) Minimum satisfiability and its applications. Walsh T, ed. Proc. 22nd Internat. Joint Conf. Artificial Intelligence, IJCAI ’11 (AAAI/IJCAI, Menlo Park, CA), 605-610.Google Scholar
[13] Li CM, Zhu Z, Manyà F, Simon L (2012) Optimizing with minimum satisfiability. Artificial Intelligence 190:32-44.Crossref, Google Scholar · Zbl 1251.68209 · doi:10.1016/j.artint.2012.05.004
[14] McCreesh C, Prosser P (2014) Reducing the branching in a branch and bound algorithm for the maximum clique problem. O’Sullivan B, ed. Proc. Internat. Conf. Principles Practice Constraint Programming, CP ’14 (Springer International, Cham, Switzerland), 549-563.Google Scholar
[15] McCreesh C, Prosser P (2015) The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound. ACM Trans. Parallel Comput. 2(1):Article no. 8.Crossref, Google Scholar · doi:10.1145/2742359
[16] Östergård P (2002) A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120(1-3):197-207.Crossref, Google Scholar · Zbl 1019.05054 · doi:10.1016/S0166-218X(01)00290-6
[17] Prosser P (2012) Exact algorithms for maximum clique: A computational study. Algorithms 5(4):545-587.Crossref, Google Scholar · Zbl 1461.90162 · doi:10.3390/a5040545
[18] Pullan W, Hoos HH (2006) Dynamic local search for the maximum clique problem. J. Artificial Intelligence Res. 25:159-185.Crossref, Google Scholar · Zbl 1182.68065 · doi:10.1613/jair.1815
[19] Pullan W, Mascia F, Brunato M (2011) Cooperating local search for the maximum clique problem. J. Heuristics 17(2):181-199.Crossref, Google Scholar · doi:10.1007/s10732-010-9131-5
[20] Régin JC (2003) Using constraint programming to solve the maximum clique problem. Rossi F, ed. Proc. Internat. Conf. Principles Practice Constraint Programming, CP ’03 (Springer, Berlin), 634-648.Google Scholar · Zbl 1273.90176
[21] San Segundo P, Rodríguez-Losada D, Jiménez A (2011) An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Res. 38(2):571-581.Crossref, Google Scholar · Zbl 1231.90369 · doi:10.1016/j.cor.2010.07.019
[22] San Segundo P, Lopez A, Batsyn M, Nikolaev A, Pardalos PM (2016) Improved initial vertex ordering for exact maximum clique search. Appl. Intelligence 45(3):868-880.Crossref, Google Scholar · doi:10.1007/s10489-016-0796-9
[23] Strickland DM, Barnes E, Sokol JS (2005) Optimal protein structure alignment using maximum cliques. Oper. Res. 53(3):389-402.Link, Google Scholar · Zbl 1165.90664
[24] Tomita E, Kameda T (2007) An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Global Optim. 37(1):95-111.Crossref, Google Scholar · Zbl 1127.90079 · doi:10.1007/s10898-006-9039-7
[25] Tomita E, Seki T (2003) An efficient branch-and-bound algorithm for finding a maximum clique. Discrete Math. Theoret. Comput. Sci. Lecture Notes in Computer Science, Vol. 2731 (Springer, Berlin), 278-289.Google Scholar · Zbl 1038.68565
[26] Tomita E, Sutani Y, Higashi T, Takahashi S, Wakatsuki M (2010) A simple and faster branch-and-bound algorithm for finding a maximum clique. Rahman MdS, Fujita S, eds. Proc. 4th Internat. Workshop Algorithms Comput., WALCOM ’10 (Springer, Berlin) 191-203.Google Scholar · Zbl 1274.05455
[27] Wang K (2013) Personal communication. Email from Kai Wang to the first author on March 8, 2013.Google Scholar
[28] Wu Q, Hao JK (2015) A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3):693-709.Crossref, Google Scholar · Zbl 1341.05241 · doi:10.1016/j.ejor.2014.09.064
[29] Xu K, Li W (2000) Exact phase transitions in random constraint satisfaction problems. J. Artificial Intelligence Res. 12:93-103.Crossref, Google Scholar · Zbl 0940.68099 · doi:10.1613/jair.696
[30] Xu K, · Zbl 1168.68554 · doi:10.1016/j.artint.2007.04.001
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.