×

On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem. (English) Zbl 1391.90607

Summary: When searching for a maximum clique in a graph \(G\), branch-and-bound algorithms in the literature usually focus on the minimization of the number of branches generated at each search tree node. We denote this minimization without any constraint a dynamic strategy, because it induces a dynamic vertex ordering in \(G\) during the search. In this paper, we introduce a static strategy that minimizes the number of branches subject to the constraint that a static vertex ordering in \(G\) must be kept during the search. We analyze the two strategies and show that they are complementary. From this complementarity, we propose a new algorithm, called MoMC, that combines the strengths of the two strategies into a single algorithm. The reported experimental results show that MoMC is generally better than the algorithms implementing a single strategy.

MSC:

90C35 Programming involving graphs or networks
05C85 Graph algorithms (graph-theoretic aspects)
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

MaxCliqueDyn; BBMCL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Babel, L.; Tinhofer, G., A branch and bound algorithm for the maximum clique problem, Methods Models Oper. Res., 34, 3, 207-217, (1990) · Zbl 0701.90091
[2] Balasundaram, B.; Butenko, S.; Hicks, I. V., Clique relaxations in social network analysis: the maximum k-plex problem, Oper. Res., 59, 1, 133-142, (2011) · Zbl 1218.90228
[3] Barnes, E.; Strickland, D. M.; Sokol, J. S., Optimal protein structure alignment using maximum cliques, Oper. Res., 53, 389-402, (2005) · Zbl 1165.90664
[4] Benlic, U.; Hao, J. K., Breakout local search for maximum clique problems, Comput. Oper. Res., 40, 1, 192-206, (2013) · Zbl 1349.90005
[5] Berman, P.; Pelc, A., Distributed fault diagnosis for multiprocessor systems, Proceedings of the 20th Annual International Symposium on Fault-Tolerant Computing(FTCS 90), 340-346, (1990), Newcastle U.K.
[6] Boginski, V.; Butenko, S.; Pardalos, P. M., Mining market data: a network approach, Comput. Oper. Res., 33, 11, 3171-3184, (2006) · Zbl 1113.90079
[7] Cai, S. W.; Su, K. L.; Abdul, S., Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Artif. Intell., 175, 1672-1696, (2011) · Zbl 1225.68242
[8] Carraghan, R.; Pardalos, P. M., An exact algorithm for the maximum clique problem, Oper. Res. Lett., 9, 6, 375-382, (1990) · Zbl 0711.90080
[9] Eppstein, D.; Darren, S., Listing all maximal cliques in large sparse real-world graphs, Proceedings of 10th International Symposium on Experimental Algorithms(SEA 2011), LNCS, 6630, 364-375, (2011)
[10] Etzion, T.; Östergård, P. R.J., Greedy and heuristic algorithms for codes and colorings, IEEE Trans. Inf. Theory, 44, 1, 382-388, (1998) · Zbl 0911.94008
[11] Fahle, T., Simple and fast: improving a branch-and-bound algorithm for maximum clique, Proceedings of the 10th Annual European Symposium on Algorithms(ESA 2002), 485-498, (2002) · Zbl 1019.90517
[12] Grosso, A.; Locatelli, M.; Pullan, W., Simple ingredients leading to very efficient heuristics for the maximum clique problem, J. Heuristics, 14, 587-612, (2008) · Zbl 1173.90565
[13] Konc, J.; Janežič, D., An improved branch and bound algorithm for the maximum clique problem, Commun. Math. Comput. Chem., 58, 569-590, (2007) · Zbl 1274.05452
[14] Lagarias, J. C.; Shor, P. W., Keller’s cube-packing conjecture is false in high dimensions, Bull. AMS (New Series), 27, 2, 279-283, (1992) · Zbl 0759.52013
[15] Li, C. M.; Fang, Z. W.; Xu, K., Combining maxsat reasoning and incremental upper bound for the maximum clique problem, Proceedings of the IEEE 25th International Conference on Tools with Artificial Intelligence(ICTAI 2013), 939-946, (2013)
[16] Li, C. M.; Jiang, H.; Xu, R. C., Incremental maxsat reasoning to reduce branches in a branch-and-bound algorithm for maxclique, Proceedings of Learning and Intelligent OptimizatioN Conference (LION 9), LNCS 8994, 268-274, (2015)
[17] Li, C. M.; Quan, Z., Combining graph structure exploitation and propositional reasoning for the maximum clique problem, Proceedings of the IEEE 22th International Conference on Tools with Artificial Intelligence(ICTAI 2010), 344-351, (2010)
[18] Li, C. M.; Quan, Z., An efficient branch-and-bound algorithm based on maxsat for the maximum clique problem, Proceedings of the 24th AAAI Conference on Artificial Intelligence(AAAI-10), 128-133, (2010)
[19] McCreesh, C.; Prosser, P., Multi-threading a state-of-the-art maximum clique algorithm, Algorithms, 6, 618-635, (2013)
[20] McCreesh, C.; Prosser, P., Reducing the branching in a branch and bound algorithm for the maximum clique problem, Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming(CP 2014), LNCS 8656, 549-563, (2014)
[21] McCreesh, C.; Prosser, P., 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, 1-27, (2015)
[22] Östergård, P. R.J., A fast algorithm for the maximum clique problem, Discrete Appl. Math., 120, 197-207, (2002) · Zbl 1019.05054
[23] Prosser, P., Exact algorithms for maximum clique: a computational study, Algorithms 2012, 5, 545-587, (2012)
[24] Pullan, W.; Hoos, H. H., Dynamic local search for the maximum clique problem, J. Artif. Intel. Res., 25, 159-185, (2006) · Zbl 1182.68065
[25] Pullan, W.; Mascia, F.; Brunato, M., Cooperating local search for the maximum clique problem, J. Heuristics, 17, 181-199, (2011)
[26] Ravetti, M. G.; Moscato, P., Identification of a 5-protein biomarker molecular signature for predicting alzheimer’s disease, PLoS ONE, 3, 9, e3111, (2008)
[27] Rebennack, S.; Reineltb, G.; Pardalos, P. M., A tutorial on branch and cut algorithms for the maximum stable set problem, Int. Trans. Oper. Res., 19, 1-2, 161-199, (2012) · Zbl 1270.90092
[28] Régin, J. C., Using constraint programming to solve the maximum clique problem, Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming(CP 2003), LNCS 2833, 634-648, (2003) · Zbl 1273.90176
[29] Segundo, P. S.; Diego, R. L.; Augustin, J., An exact bit-parallel algorithm for the maximum clique problem, Comput. Oper. Res., 38, 571-581, (2011) · Zbl 1231.90369
[30] Segundo, P. S.; Tapia, C., Relaxed approximate coloring in exact maximum clique search, Comput. Oper. Res., 44, 185-192, (2014) · Zbl 1307.90153
[31] Sharmin, S., Practical Aspects of the Graph Parameter Boolean-width, (2014), University of Bergen Norway, Dissertation for the degree of philosophiae doctor (phd)
[32] Tomita, E.; Kameda, T., An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments, J. Glob. Optim., 37, 95-111, (2007) · Zbl 1127.90079
[33] Tomita, E.; Seki, T., An efficient branch-and-bound algorithm for finding a maximum clique, Proceedings of the 4th International Conference on Discrete Mathematics & Theoretical Computer Science(DMTCS 2003), LNCS 2731, 278-289, (2003) · Zbl 1038.68565
[34] Tomita, E.; Sutani, Y.; Higashi, T.; Takahashi, S.; Wakatsuki, M., A simple and faster branch-and-bound algorithm for finding maximum clique, Proceedings of the 4th International Workshop on Algorithms and Computation(WALCOM 2010), LNCS 5942, 191-203, (2010) · Zbl 1274.05455
[35] Wang, K., 2013. Personal communication.
[36] Wu, Q. H.; Hao, J. K., A review on algorithms for maximum clique problems, Eur. J. Oper. Res., 242, 3, 693-709, (2015) · Zbl 1341.05241
[37] Xu, K.; Frédéric, B.; Fred, H.; Christophe, L., Random constraint satisfaction: easy generation of hard (satisfiable) instances, Artif. Intell., 171, 514-534, (2007) · Zbl 1168.68554
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.