A local core number based algorithm for the maximum clique problem. (English) Zbl 1488.05389
Summary: The maximum clique problem (MCP) is to determine a complete subgraph of maximum cardinality in a graph. MCP is a fundamental problem in combinatorial optimization and is noticeable for its wide range of applications. In this paper, we present two branch-and-bound exact algorithms for finding a maximum clique in an undirected graph. Many efficient exact branch and bound maximum clique algorithms use approximate coloring to compute an upper bound on the clique number but, as a new pruning strategy, we show that local core number is more efficient. Moreover, instead of neighbors set of a vertex, our search area is restricted to a subset of the set in each subproblem which speeds up clique finding process. This subset is based on the core of the vertices of a given graph. We improved the MCQ and MaxCliqueDyn algorithms with respect to the new pruning strategy and search area restriction. Experimental results demonstrate that the improved algorithms outperform the previous well-known algorithms for many instances when applied to DIMACS benchmark and random graphs.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | P. San Segundo and J. Artieda, A novel clique formulation for the visual feature matching problem,Appl. Intell.,43 (2015) 325-342. |
| [2] | P. San Segundo, D. Rodriguez-Losada, F. Matia and R. Galan, Fast exact feature based data correspondence search with an efficient bit-parallel MCP solver,Appl. Intell.,32(2010) 311-329. |
| [3] | S. Butenko and W. E. Wilhelm, Clique-detection models in computational biochemistry and genomics,European J. Operational Researc,173(2006) 1-17. · Zbl 1125.92025 |
| [4] | C. W. Art, B. Sergiy and P. Panos M.,Clustering challenges in biological networks, World Scientific Publishing Co, Inc., 2009. |
| [5] | T. Etzion and P. R. Ostergard, Greedy and heuristic algorithms for codes and colorings,IEEE Trans. Inform. Theor, 44(1998) 382-388. · Zbl 0911.94008 |
| [6] | T. Gschwind, S. Irnich, F. Furini and R. W. Calvo,Social network analysis and community detection by decomposing a graph into relaxed cliques, Technical Report LM-2015-07; Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz: Mainz, Germany, 2015. |
| [7] | O. Weide, D. Ryan and M. Ehrgott, An iterative approach to to robust and integrated aircraft routing and crew scheduling,Comput. Oper. Res.,37(2010) 833-844. · Zbl 1177.90190 |
| [8] | Q. Wu and J. K. Hao, A review on algorithms for maximum clique problems,European J. Oper. Res.h,242(2015) 693-709. · Zbl 1341.05241 |
| [9] | V. Batagelj and M. Zaversnik,O(m)algorithm for cores decomposition of networks, arXiv preprint cs/0310049, 2003 1-9. |
| [10] | S. B. Seidman, Network structure and minimum degree,Social Networks,5(1983) 269-287. |
| [11] | M. R. Garey and D. S. Johnson,Computers and intractability: A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco, Calif., 1979. · Zbl 0411.68039 |
| [12] | J. Hastad, Clique is hard to approximate withinn1−ϵ,Acta Math.,182(1999) 105-142. · Zbl 0989.68060 |
| [13] | U. Feige, Approximating maximum clique by removing subgraphs,SIAM J. Discrete Math.,18(2004) 219-225. · Zbl 1068.05052 |
| [14] | P. R. J. Ostergard, A fast algorithm for the maximum clique problem,Discrete Appl. Math.,120(2002) 197-207. · Zbl 1019.05054 |
| [15] | L. Babel and G. Tinhofer, A branch and bound algorithm for the maximum clique problem,Z. Oper. Res.,34(1990) 207-217. · Zbl 0701.90091 |
| [16] | D. Brelaz, New methods to color the vertices of a graph,Comm. ACM,22(1979) 251-256. · Zbl 0394.05022 |
| [17] | E. Tomita and T. Seki, An efficient branch-and-bound algorithm for finding a maximum clique.In:Proceedings of the discrete mathematics and theoretical computer science. Lecture Notes in Computer Science,2731(2003) 278-289. · Zbl 1038.68565 |
| [18] | E. Tomita and T. Kameda, An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments,J. Global Optim.,37(2007) 95-111. · Zbl 1127.90079 |
| [19] | J. Konc and D. Janezic, An improved branch and bound algorithm for the maximum clique problem,MATCH Commun. Math. Comput. Chem.,58(2007) 569-590. · Zbl 1274.05452 |
| [20] | P. San Segundo, D. Rodrguez-Losada and A. Jimenez, An exact bit-parallel algorithm for the maximum clique problem,Comput. Oper. Res.,38(2011) 571-581 · Zbl 1231.90369 |
| [21] | E. Tomita, Y. Sutani, T. Higashi, S. Takahashi and M. Wakatsuki, A simple and faster branch-and bound algorithm for finding a maximum clique,Lecture Notes in Comput. Sci.,5942(2010) 191-203. · Zbl 1274.05455 |
| [22] | P. San Segundo, F. Matia, D. Rodriguez-Losada and M. Hernando, An improved bit parallel exact maximum clique algorithm,Optim. Lett.,7(2013) 467-479. · Zbl 1268.90118 |
| [23] | P. San Segundo, C. Tapia, Relaxed approximate coloring in exact maximum clique search,Comput. Oper. Res.,44 (2014) 185-192. · Zbl 1307.90153 |
| [24] | R. A. Rossi, D. F. Gleich, A. H. Gebremedhin and M. M. A. Patwary, Fast maximum clique algorithms for large graphs,In: Proceedings of the 23rd International Conference on World wide web, ACM, (2014) 365-366. |
| [25] | R. A. Rossi, D. F. Gleich and A. H. Gebremedhin, Parallel maximum clique algorithms with applications to network analysis,SIAM J. Sci. Comput.,37(2015) C589-C616. · Zbl 1323.05103 |
| [26] | B. Pattabiraman, M. M. A. Patwary, A. H. Gebremedhin, W. K. Liao and A. Choudhary,Fast algorithms for the maximum clique problem on massive sparse graphs, Algorithms and models for the web graph, Lecture Notes in Comput. Sci.,8305, Springer, Cham, (2013) 156-169 · Zbl 1342.05185 |
| [27] | P. San Segundo, A. Lopez and P. M. Pardalos, A new exact maximum clique algorithm for large and massive sparse graphs,Comput. Oper. Res.,66(2016) 81-94. · Zbl 1349.90824 |
| [28] | P. San Segundo, A. Nikolaev and M. Batsyn, Infra-chromatic bound for exact maximum clique search,Comput. Oper. Res.,64(2015) 293-303. · Zbl 1349.90825 |
| [29] | C. M. Li and Z. Quan, An efficient branch-and-bound algorithm based on MaxSAT for the maximum clique problem, In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI-10, (2010) 128-133. |
| [30] | D. J. Welsh and M. B. Powell, An upper bound for the chromatic number of a graph and its application to timetabling problems,Comput. J.,10(1967) 85-86. · Zbl 0147.15206 |
| [31] | J. T. Hungerford and F. Rinaldi, A General Regularized Continuous Formulation for the Maximum Clique Problem, Math. Oper. Res.,44(2019) 1161-1173. · Zbl 1437.90147 |
| [32] | K. Kanazawa and S. Cai, FPGA Acceleration to Solve Maximum Clique Problems Encoded into Partial MaxSAT, 2018 IEEE 12th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC), (2018) 217-224. |
| [33] | M. T. Belachew and N. Gillis, Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation,J. Optim. Theory Appl.,173(2017) 279-296. · Zbl 1380.65100 |
| [34] | A. Verma, A. Buchanan and S. Butenko, Solving the maximum clique and vertex coloring problems on very large sparse networks,INFORMS J. Comput.,27(2015) 164-177. · Zbl 1327.90356 |
| [35] | C. M. Li, Z. Fang, H. Jiang and K. Xu, Incremental upper bound for the maximum clique problem,INFORMS J. Comput.,30(2017) 137-153. · Zbl 1528.05052 |
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.
