Surveying Some Metaheuristic Algorithms for Solving Maximum Clique Graph Problem

  • Phan Tấn Quốc TS Phan Tấn Quốc - Khoa CNTT - ĐH Sài gòn: Mobi: 0918178052. Email:
Keywords: maximum clique problem, social networks, heuristic algorithm, metaheuristic algorithm, DIMACS, soft computing


Maximum clique graph problem is a combinatorial optimization that applies science and engineering such as social networks, telecommunication networks, bioinformatics, etc. Maximum clique is a problem of class NP-hard. There are many approaches for solving the maximum clique graph problem such as algorithms to find the exact solutions, heuristic algorithms, metaheuristic algorithms, etc. In this paper, we survey the approach for solving the maximum clique graph problem in the direction of metaheuristic algorithms and evaluate the quality of these research based on the experimental data system DIMACS. This survey can be useful for further research on maximum clique graph problems.


Alessio Conte et al, "Finding all maximal cliques in very large social networks", 19th International Conference on Extending Database Technology, ISBN 978-3-89318-070-7, pp.173-184, Bordeaux, France, 2016.

Andreas Barmann et al, "The clique problem with multiple- ¨ choice constraints under a cycle-free dependency graph", Discrete Applied Mathematics, Vol. 283, pp.59-77, ELSEVIER, 2020.

Atul Srivastava et al, "Maximum clique finder: MCF", IJITEE, Volume 7, Issue 2, 2018.

Benchmark maximum_clique problem, fmascia/maximum_clique/DIMACSbenchmark, (last update, 26 Oct 2015).

Benchmark maximum_clique problem,, (last updated: Dec. 1, 2014).

Bharath Pattabiraman et al, "Fast algorithms for the maximum clique problem on massive graphs with applications to overlapping community detection", Internet Mathematics, Volume 11, Issue 4-5, 421-448, Taylor & Francis Group, LLC, 2015.

Bo Huang, "Finding maximum clique with a genetic algorithm", The Pennsylvania State University, Master of Science, 2002.

Dam Thanh Phuong, Ngo Manh Tuong, Khoa Thu Hoai, "Maximum clique problem - applications and computational challenges", Journal of Science & Technology – Issue Natural Science & Engineering, Thai Nguyen University, ISSN: 1859-2171, Vol.102, No.2, pp.13-17, 2013. (Vietnamese).

Do Minh Vu, "Bees algorithm to solve the max clique problem", Master of Computer Science, Sai Gon University, 2020. (Vietnamese).

Elena Marchiori, "Genetic, Iterated and multistart local search for the maximum clique Problem", Applications of Evolutionary Computing, pp.112–121, Springer, 2002.

Emmanuel Hebrard, George Katsirelos, "Conflict directed clause learning for the maximum weighted clique problem", Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pp.1316-1323, 2018.

Giannis Nikolentzos et al, "K-clique-graphs for dense subgraph discovery", Machine Learning and Knowledge Discovery in Database, pp.617–633, 2017.

George Manoussakis, Algorithms for cliques in inductive kindependent graphs, University Paris Sud, France, 2016.

Golkar Mohammad Javad et al, "Maximum clique problem solving using imperialist competitive algorithm and a greedy method for generating initial population", Indian Journal of Scientific Research, Vol. 7, Issue 1, pp.442-448, 2014.

Huynh Thanh Tan, Nguyen Van Thanh, "A improved local search for the maximum clique problem",National Conference, X, Fundamental and Applied Information Technology - FAIR’2017; Da Nang University, Natural Science and Technology Publishing House. 17-18/08/2017, ISBN:978- 604-913-614-6.pp.148-155. (Vietnamese).

Huynh Thi Chau Ai, "Approximate algorithm to solve the max clique problem", Master of Computer Science, Sai Gon University, 2019. (Vietnamese).

Jack J. Dongarra (2014). Performance of various computers using standard linear equations

software, University of Manchester, pp.1-109 (

Jose L. Walteros, Austin Buchanan, "Why is maximum clique often easy in practice?", Operations Research, Vol. 68, No. 6, pp.1866–1895, INFORMS, 2020.

José Angel Riveaux Merino, "An exact algorithm for the maximum quasi-clique problem", International Transactions in Operational Research, pp.2199-2229, WILEY, 2019.

Kengo Katayama, Akihiro Hamamoto, Hiroyuki Narihisa, "An effective local search for the maximum clique problem", Information Processing Letters, Volume 95, Issue 5, pp.503- 511, Elsevier, 2005.

Krishna Kumar Singh, Ajeet Kumar Pandey, "Survey of algorithms on maximum clique problem", IARJSET, Vol. 2, Issue 2, pp.15-20, 2015.

Melisew Tefera Belachew, Nicolas Gillis, "Solving the maximum clique problem with symmetric rank-one nonnegative matrix approximation", Journal of Optimization Theory and Applications, Vol. 173, pp.279-296, Springer, 2017.

Mochamad Suyudi, Sukono et al, "Branch and bound algorithm for finding the maximum clique problem", Proceedings of the International Conference on Industrial Engineering and Operations Management, Bandung, Indonesia, pp.2734-2742, IEOM Society International, 2018.

Mohammad Soleimani-Pouri et al, "Finding a maximum clique using ant colony optimization and particle swarm optimization in social networks", ASONAM ’12: Proceedings of the 2012 International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012), pp.58-61, IEEE, 2012.

Muhammad Fayaz et al, "Approximate maximum clique algorithm (amca): a clever technique for solving the maximum clique problem through near optimal algorithm for minimum vertex cover problem", International Journal of Control and Automation (IJCA), Vol. 11, No. 3, pp.35-44, SERSC Australia, 2018.

Nguyen Duc Nghia, Nguyen To Thanh, "Discrete Math", Viet Nam National University Press, HaNoi, pp. 147-260, 2009. (Vietnamese).

Nguyen Canh Nam, "On globally solving the maximum weighted clique problem", Vietnam National Foundation for Science and Technology Development (NAFOSTED),, Viet Nam, 2013.

Phan Tan Quoc, Nguyen Duc Nghia (2013). "Tabu search Algorithm for Solving Minimum Routing Cost Spanning Tree Problem". Journal on Information Technology & Communication, Ministry of Information and Communications, ISSN: 1589-3526, Vol. 3, pp.5-13. (Vietnamese).

Phan Tan Quoc, Nguyen Duc Nghia (2013). "Bees algorithm for solving minimum routing cost spanning tree problem". Journal of Computer Science and Cybernetics, ISSN: 1813- 9663, Vol. 29, No. 3, 2013, pp.265-276, Science and Technics Publishing House. (Vietnamese). [30] Phan Tan Quoc, "An analysis on the intensification and the diversification properties in metaheuristic algorithms to solve optimization problems", National conference on information and communication technology, Can Tho University, ISBN:978-604-919-456-6, 2015. (Vietnamese).

Phan Tan Quoc, Huynh Thi Chau Ai, "Improved heuristic algorithms for solving maximum clique problem", National Conference, Fundamental and Applied Information Technology) - FAIR’2019, Institute of Information and Communication Technology; University of Science - Hue University, 07-08/06/2019. Natural Science and Technology Publishing House. ISBN: 978-604-913-915-4, pp.64-72. (Vietnamese).

Phan Tan Quoc, Huynh Thi Chau Ai, Nguyen Son Lam, Huynh Thanh Tan, "A improved variable neighborhood

search algorithm to solve the max clique problem", National Conference, XXII: Some selected issues of information and Communication Technology, Institute of Information and Communication Technology. Thai Binh University, 28- 29/6/2019. Science and Technics Publishing House, ISBN 978-604-67-1287-9. (Vietnamese).

Qinghua Wua, Jin-Kao Hao, "A review on algorithms for maximum clique problems", European Journal of Operational Research, Volume 242, Issue 3, pp.693-709, Elsevier, 2015.

Rachel Behar, Sara Cohen, "Finding all maximal connected s-cliques in social networks", Proceedings of the 21st International Conference on Extending Database Technology, ISBN 978-3-89318-078-3, pp.61-72, Vienna, Austria, 2018.

Ricardo C. Correa, Philippe Michelon, Bertrand Le Cun, Thierry Mautor, Diego Delle Donne, "A bit-parallel russian dolls search for a maximum cardinality clique in a graph",, 2015.

Ryan A. Rossi et al, "Fast maximum clique algorithms for large graphs", WWW ’14 Companion: Proceedings of the 23rd International Conference on World Wide Web, ACM, pp.365-366, 2014.

Satoshi Shimizu, Kazuaki Yamaguchi,and Sumio Masuda, A maximum edge-weight clique extraction algorithm based on branch-and-bound, Kobe University, pp.1-15, 2018.

Serge Fenet, Christine Solnon, "Searching for maximum cliques with ant colony optimization", Springer-Verlag Berlin Heidelberg, pp.236-245, 2003.

Shaowei Cai, Jinkun Lin, "Fast solving maximum weight clique problem in massive graphs", Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI), pp.568-574, 2016.

Truong Minh Hoang Thong, "Genetic algorithm to solve the max clique problem", Master of Computer Science, Sai Gon University, 2020. (Vietnamese).

Una Benlic, Jin-Kao Hao, "Breakout local search for maximum clique problems", Computers & Operations Research Volume 40, Issue 1, pp.192-206, Elsevier, 2013.

Vu Dinh Hoa, Do Trung Kien, "Parallel algorithm to solve the problem of determining the maximum clique on the graph", National Conference, XII: Some selected issues of Information and Communication Technology, pp.426-442, 2009. (Vietnamese).

Wayne Pullan, Franco Mascia, Mauro Brunato, "Cooperating local search for the maximum clique problem", Journal of Heuristics, Vol. 17, pp.181–199, Springer, 2010.

Yi Zhou, "Optimization algorithms for clique problems", grade de Docteur de l’Université d’Angers, pp.1-122, 2018.

Yuquan Guo et al, "Heuristic artificial bee colony algorithm for uncovering community in complex networks", Mathematical Problems in Engineering, pp.1-12, 2017.

Xin-She Yang. "Engineering optimization: An Introduction with Metaheuristic Applications", WILEY, 2010.

Xin-She Yang. "Nature-inspired metaheuristic algorithms". LUNIVER Press, 2010.

Phan Thanh Huan, Huynh Thi Chau Ai, Chau Le, Sa Lin, "Heuristic Approach for Solving the Maximum Clique

Problem on Simple Undirected and Unweighted Graph", Journal on Information Technology & Communication, Vol. 2021, No 1, pp.32-39, June, 2021. (Vietnamese).

János Barta, Roberto Montemanni, "The Maximum Clique Problem for Permutation Hamming Graphs", Journal of Optimization Theory and Applications, Volume 194, pp.492–507, Springer, 2022.

Wataru Nakasone, Morikazu Nakamura, "Maximal Clique Problem Formulation for Common Structure Detection in Many Graphs", 37th International Technical Conference on Circuits/Systems, Computers and Communications (ITCCSCC), Phuket, Thailand, IEEE, 2022.