{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T02:28:33Z","timestamp":1773109713630,"version":"3.50.1"},"reference-count":34,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T00:00:00Z","timestamp":1679875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>The Maximum Common Subgraph problem has been long proven NP-hard. Nevertheless, it has countless practical applications, and researchers are still searching for exact solutions and scalable heuristic approaches. Driven by applications in molecular science and cyber-security, we concentrate on the Maximum Common Subgraph among an indefinite number of graphs. We first extend a state-of-the-art branch-and-bound procedure working on two graphs to N graphs. Then, given the high computational cost of this approach, we trade off complexity for accuracy, and we propose a set of heuristics to approximate the exact solution for N graphs. We analyze sequential, parallel multi-core, and parallel-many core (GPU-based) approaches, exploiting several leveraging techniques to decrease the contention among threads, improve the workload balance of the different tasks, reduce the computation time, and increase the final result size. We also present several sorting heuristics to order the vertices of the graphs and the graphs themselves. We compare our algorithms with a state-of-the-art method on publicly available benchmark sets. On graph pairs, we are able to speed up the exact computation by a 2\u00d7 factor, pruning the search space by more than 60%. On sets of more than two graphs, all exact solutions are extremely time-consuming and of a complex application in many real cases. On the contrary, our heuristics are far less expensive (as they show a lower-bound for the speed up of 10\u00d7), have a far better asymptotic complexity (with speed ups up to several orders of magnitude in our experiments), and obtain excellent approximations of the maximal solution with 98.5% of the nodes on average.<\/jats:p>","DOI":"10.3390\/computation11040069","type":"journal-article","created":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T06:46:19Z","timestamp":1679899579000},"page":"69","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The Multi-Maximum and Quasi-Maximum Common Subgraph Problem"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-7553-4839","authenticated-orcid":false,"given":"Lorenzo","family":"Cardone","sequence":"first","affiliation":[{"name":"Dipartimento di Automatica e Informatica, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6835-8277","authenticated-orcid":false,"given":"Stefano","family":"Quer","sequence":"additional","affiliation":[{"name":"Dipartimento di Automatica e Informatica, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1142\/S0218001404003228","article-title":"Thirty Years of Graph Matching in Pattern Recognition","volume":"18","author":"Conte","year":"2004","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"key":"ref_2","first-page":"60","article-title":"The Small World Problem","volume":"2","author":"Milgram","year":"1967","journal-title":"Psychol. Today"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1086\/210318","article-title":"Networks, Dynamics, and the Small-world Phenomenon","volume":"105","author":"Watts","year":"1999","journal-title":"Am. J. Sociol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/324133.324140","article-title":"Authoritative Sources in a Hyperlinked Environment","volume":"46","author":"Kleinberg","year":"1999","journal-title":"J. ACM (JACM)"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"i138","DOI":"10.1093\/bioinformatics\/btg1018","article-title":"Deriving Phylogenetic Trees from the Similarity Analysis of Metabolic Pathways","volume":"19","author":"Heymans","year":"2003","journal-title":"Bioinformatics"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"O6","DOI":"10.1186\/1758-2946-5-S1-O6","article-title":"FMCS: A Novel Algorithm for the Multiple MCS Problem","volume":"5","author":"Dalke","year":"2013","journal-title":"J. Cheminform."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Park, Y., and Reeves, D. (2011, January 22\u201324). Deriving Common Malware Behavior through Graph Clustering. Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security (ASIACCS\u201911), Hong Kong, China.","DOI":"10.1145\/1966913.1966986"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","article-title":"Finding All Cliques of an Undirected Graph (algorithm 457)","volume":"16","author":"Bron","year":"1973","journal-title":"Commun. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0020-0190(76)90049-1","article-title":"Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques","volume":"4","author":"Barrow","year":"1976","journal-title":"Inf. Process. Lett."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/BF02575586","article-title":"A Note on the Derivation of Maximal Common Subgraphs of two Directed or Undirected Graphs","volume":"9","author":"Levi","year":"1973","journal-title":"Calcolo"},{"key":"ref_11","unstructured":"Vismara, P., and Valery, B. (2008). Communications in Computer and Information Science, Springer."},{"key":"ref_12","unstructured":"McCreesh, C., Ndiaye, S.N., Prosser, P., and Solnon, C. (2016). Principles and Practice of Constraint Programming, Proceedings of the 22nd International Conference, CP 2016, Toulouse, France, 5\u20139 September 2016, Springer. Lecture Notes in Computer Science."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2523","DOI":"10.1016\/j.dam.2012.01.026","article-title":"The Maximum Common Edge Subgraph Problem: A Polyhedral Investigation","volume":"160","author":"Bahiense","year":"2012","journal-title":"Discret. Appl. Math."},{"key":"ref_14","unstructured":"Bai, Y., Xu, D., Gu, K., Wu, X., Marinovic, A., Ro, C., Sun, Y., and Wang, W. (2020, January 30). Neural Maximum Common Subgraph Detection with Guided Subgraph Extraction. Proceedings of the International Conference on Learning Representations (ICLR 2020), Addis Ababa, Ethiopia."},{"key":"ref_15","unstructured":"Meila, M., and Zhang, T. (2021, January 18\u201324). GLSearch: Maximum Common Subgraph Detection via Learning to Search. Proceedings of the Machine Learning Research, 38th International Conference on Machine Learning, Virtual Event."},{"key":"ref_16","first-page":"2392","article-title":"A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems","volume":"34","author":"Liu","year":"2020","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Quer, S., Marcelli, A., and Squillero, G. (2020). The Maximum Common Subgraph Problem: A Parallel and Multi-Engine Approach. Computation, 8.","DOI":"10.3390\/computation8020048"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1021\/ci100297y","article-title":"MultiMCS: A Fast Algorithm for the Maximum Common Substructure Problem on Multiple Molecules","volume":"51","author":"Hariharan","year":"2011","journal-title":"J. Chem. Inf. Model."},{"key":"ref_19","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2022). Introduction to Algorithms, The MIT Press. [4th ed.]."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"McCreesh, C., Prosser, P., and Trimble, J. (2017, January 19\u201325). A Partitioning Algorithm for Maximum Common Subgraph Problems. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17), Melbourne, Australia.","DOI":"10.24963\/ijcai.2017\/99"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/spe.4380120103","article-title":"Backtrack Search Algorithms and the Maximal Common Subgraph Problem","volume":"12","author":"McGregor","year":"1982","journal-title":"Softw. Pract. Exp."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1137\/0215075","article-title":"Finding a Maximum Clique in an Arbitrary Graph","volume":"15","author":"Balas","year":"1986","journal-title":"SIAM J. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1023\/A:1021271615909","article-title":"Maximum Common Subgraph Isomorphism Algorithms for the Matching of Chemical Structures","volume":"16","author":"Raymond","year":"2002","journal-title":"J. Comput.-Aided Mol. Des."},{"key":"ref_24","unstructured":"Ndiaye, S.M., and Solnon, C. (2011). Principles and Practice of Constraint Programming (CP 2011), Springer."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/s10479-011-1019-8","article-title":"Polyhedral Study of the Maximum Common Induced Subgraph Problem","volume":"199","author":"Piva","year":"2012","journal-title":"Ann. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1021\/acs.jcim.5b00036","article-title":"Efficient Heuristics for Maximum Common Substructure Search","volume":"55","author":"Englert","year":"2015","journal-title":"J. Chem. Inf. Model."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Hoffmann, R., McCreesh, C., and Reilly, C. (2017, January 4\u20139). Between Subgraph Isomorphism and Maximum Common Subgraph. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.11137"},{"key":"ref_28","unstructured":"McCreesh, C. (2017). Solving Hard Subgraph Problems in Parallel. [Ph.D. Thesis, University of Glasgow]."},{"key":"ref_29","first-page":"20170014","article-title":"CytoMCS: A Multiple Maximum Common Subgraph Detection Tool for Cytoscape","volume":"14","author":"Simon","year":"2017","journal-title":"J. Integr. Bioinform."},{"key":"ref_30","unstructured":"Foggia, P., Sansone, C., and Vento, M. (2001, January 23\u201325). A Database of Graphs for Isomorphism and Sub-Graph Isomorphism Benchmarking. Proceedings of the 3rd IAPR TC-15 International Workshop on Graph-Based Representations, Ischia, Italy."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1016\/S0167-8655(02)00248-9","article-title":"A Large Database of Graphs and its Use for Benchmarking Graph Isomorphism Algorithms","volume":"24","author":"Foggia","year":"2003","journal-title":"Pattern Recogn. Lett."},{"key":"ref_32","unstructured":"(2023, March 23). Available online: https:\/\/mivia.unisa.it\/datasets\/graph-database\/arg-database\/."},{"key":"ref_33","unstructured":"(2023, March 23). Available online: https:\/\/github.com\/stefanoquer\/Multi-Maximum-Common-Subgraph."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","article-title":"Progressive Sequence Alignment as a Prerequisitetto Correct Phylogenetic Trees","volume":"25","author":"Feng","year":"1987","journal-title":"J. Mol. Evol."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/4\/69\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:04:04Z","timestamp":1760123044000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/4\/69"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,27]]},"references-count":34,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,4]]}},"alternative-id":["computation11040069"],"URL":"https:\/\/doi.org\/10.3390\/computation11040069","relation":{},"ISSN":["2079-3197"],"issn-type":[{"value":"2079-3197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,27]]}}}