{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T02:34:41Z","timestamp":1773110081126,"version":"3.50.1"},"reference-count":51,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T00:00:00Z","timestamp":1589760000000},"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 of two graphs is the largest possible common subgraph, i.e., the common subgraph with as many vertices as possible. Even if this problem is very challenging, as it has been long proven NP-hard, its countless practical applications still motivates searching for exact solutions. This work discusses the possibility to extend an existing, very effective branch-and-bound procedure on parallel multi-core and many-core architectures. We analyze a parallel multi-core implementation that exploits a divide-and-conquer approach based on a thread pool, which does not deteriorate the original algorithmic efficiency and it minimizes data structure repetitions. We also extend the original algorithm to parallel many-core GPU architectures adopting the CUDA programming framework, and we show how to handle the heavily workload-unbalance and the massive data dependency. Then, we suggest new heuristics to reorder the adjacency matrix, to deal with \u201cdead-ends\u201d, and to randomize the search with automatic restarts. These heuristics can achieve significant speed-ups on specific instances, even if they may not be competitive with the original strategy on average. Finally, we propose a portfolio approach, which integrates all the different local search algorithms as component tools; such portfolio, rather than choosing the best tool for a given instance up-front, takes the decision on-line. The proposed approach drastically limits memory bandwidth constraints and avoids other typical portfolio fragility as CPU and GPU versions often show a complementary efficiency and run on separated platforms. Experimental results support the claims and motivate further research to better exploit GPUs in embedded task-intensive and multi-engine parallel applications.<\/jats:p>","DOI":"10.3390\/computation8020048","type":"journal-article","created":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T11:34:14Z","timestamp":1589801654000},"page":"48","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["The Maximum Common Subgraph Problem: A Parallel and Multi-Engine Approach"],"prefix":"10.3390","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6835-8277","authenticated-orcid":false,"given":"Stefano","family":"Quer","sequence":"first","affiliation":[{"name":"Dipartimento di Automatica e Informatica, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1441-5798","authenticated-orcid":false,"given":"Andrea","family":"Marcelli","sequence":"additional","affiliation":[{"name":"Cisco Systems, Talos Security Intelligence and Research Group, 06250 Sophia Antipolis, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5784-6435","authenticated-orcid":false,"given":"Giovanni","family":"Squillero","sequence":"additional","affiliation":[{"name":"Dipartimento di Automatica e Informatica, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,5,18]]},"reference":[{"key":"ref_1","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_2","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_3","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 26th International Joint Conference on Artificial Intelligence (IJCAI\u201917), Melbourne, Australia.","DOI":"10.24963\/ijcai.2017\/99"},{"key":"ref_4","unstructured":"Mattson, T., Sanders, B., and Massingill, B. (2004). Patterns for Parallel Programming, Addison-Wesley Professional. [1st ed.]."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"McCool, M., Reinders, J., and Robison, A. (2012). Structured Parallel Programming: Patterns for Efficient Computation, Morgan Kaufmann Publishers Inc.. [1st ed.].","DOI":"10.1016\/B978-0-12-415993-8.00003-7"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"52027","DOI":"10.1109\/ACCESS.2018.2870283","article-title":"A Fast MPEG\u2019s CDVS Implementation for GPU Featured in Mobile Devices","volume":"6","author":"Garbo","year":"2018","journal-title":"IEEE Access"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Cabodi, G., Camurati, P., Garbo, A., Giorelli, M., Quer, S., and Savarese, F. (2019). A Smart Many-Core Implementation of a Motion Planning Framework along a Reference Path for Autonomous Cars. Electronics, 8.","DOI":"10.3390\/electronics8020177"},{"key":"ref_8","unstructured":"(2019, October 01). The SAT Competition Web Page. Available online: http:\/\/www.satcompetition.org\/."},{"key":"ref_9","unstructured":"(2019, October 01). The SMT Competition Web Page. Available online: https:\/\/smt-comp.github.io\/2019\/index.html."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Festa, P., Sellmann, M., and Vanschoren, J. (2016). Portfolios of Subgraph Isomorphism Algorithms. Learning and Intelligent Optimization, Springer International Publishing.","DOI":"10.1007\/978-3-319-50349-3"},{"key":"ref_11","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 Recognit. Lett."},{"key":"ref_12","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_13","doi-asserted-by":"crossref","unstructured":"Bunke, H., Foggia, P., Guidobaldi, C., Sansone, C., and Vento, M. (2002, January 6\u20139). A Comparison of Algorithms for Maximum Common Subgraph on Randomly Connected Graphs. Proceedings of the Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), Windsor, ON, Canada.","DOI":"10.1007\/3-540-70659-3_12"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"99","DOI":"10.7155\/jgaa.00139","article-title":"Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs","volume":"11","author":"Conte","year":"2007","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Le Thi, H.A., Bouvry, P., and Pham Dinh, T. (2008). Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms. Modelling, Computation and Optimization in Information Systems and Management Sciences, Springer.","DOI":"10.1007\/978-3-540-87477-5"},{"key":"ref_16","unstructured":"Minot, M., and Ndiaye, S.N. (2014, January 8\u201312). Searching for a Maximum Common Induced Subgraph by Decomposing the Compatibility Graph. Proceedings of the Workshop in Bridging the Gap Between Theory and Practice in Constraint Solvers (CP2014), Lyon, France."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.knosys.2015.05.012","article-title":"Approximating the Maximum Sommon Subgraph Isomorphism Problem with a Weighted Graph","volume":"85","author":"Chen","year":"2015","journal-title":"Knowl. Based Syst."},{"key":"ref_18","unstructured":"Bunke, H., Foggia, P., Guidobaldi, C., and Vento, M. (July, January 30). Graph Clustering Using the Weighted Minimum Common Supergraph. Proceedings of the 4th IAPR International Conference on Graph Based Representations in Pattern Recognition (GbRPR\u201903), York, UK."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/S0036144502415960","article-title":"A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching","volume":"46","author":"Blondel","year":"2004","journal-title":"SIAM Rev."},{"key":"ref_20","unstructured":"Zager, L.A. (2005). Graph Similarity and Matching. [Ph.D. Thesis, Massachussetts Institute of Technology]."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1016\/S0167-8655(97)00060-3","article-title":"On a relation between graph edit distance and maximum common subgraph","volume":"18","author":"Bunke","year":"1997","journal-title":"Pattern Recognit. Lett."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1016\/S0167-8655(01)00017-4","article-title":"A graph distance metric combining maximum common subgraph and minimum common supergraph","volume":"22","author":"Venero","year":"2001","journal-title":"Pattern Recognit. Lett."},{"key":"ref_23","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_24","doi-asserted-by":"crossref","unstructured":"Ndiaye, S.M., and Solnon, C. (2011, January 12\u201316). CP Models for Maximum Common Subgraph Problems. Proceedings of the 17th International Conference of Principles and Practice of Constraint Programming, Perugia, Italy.","DOI":"10.1007\/978-3-642-23786-7_48"},{"key":"ref_25","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_26","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_27","doi-asserted-by":"crossref","unstructured":"McCreesh, C., Ndiaye, S.N., Prosser, P., and Solnon, C. (2016). Clique and Constraint Models for Maximum Common (connected) Subgraph Problems. International Conference on Principles and Practice of Constraint Programming, Springer.","DOI":"10.1007\/978-3-319-44953-1_23"},{"key":"ref_28","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_29","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_30","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_31","doi-asserted-by":"crossref","unstructured":"Pesant, G. (2015). A Parallel, Backjumping Subgraph Isomorphism Algorithm Using Supplemental Graphs. Principles and Practice of Constraint Programming, Springer International Publishing.","DOI":"10.1007\/978-3-319-23219-5"},{"key":"ref_32","unstructured":"Rousseau, L.M., and Stergiou, K. (2019). Sequential and Parallel Solution-Biased Search for Subgraph Algorithms. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Springer International Publishing."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Minot, M., Ndiaye, S., and Solnon, C. (2015, January 9\u201311). A Comparison of Decomposition Methods for the Maximum Common Subgraph Problem. Proceedings of the IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI), Vietri sul Mare, Italy.","DOI":"10.1109\/ICTAI.2015.75"},{"key":"ref_34","unstructured":"McCreesh, C. (2017). Solving Hard Subgraph Problems in Parallel. [Ph.D. Thesis, University of Glasgow]."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Hoffmann, R., Mccreesh, C., Ndiaye, S.N., Prosser, P., Reilly, C., Solnon, C., and Trimble, J. (2018). Observations from Parallelising Three Maximum Common (Connected) Subgraph Algorithms. International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Springer.","DOI":"10.1007\/978-3-319-93031-2_22"},{"key":"ref_36","unstructured":"Kimmig, R., Meyerhenke, H., and Strash, D. (June, January 29). Shared Memory Parallel Subgraph Enumeration. Proceedings of the IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Lake Buena Vista, FL, USA."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"McCreesh, C., and 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.","DOI":"10.1145\/2742359"},{"key":"ref_38","unstructured":"Trimble, J. (2019, October 01). McSplit Implementations. Available online: https:\/\/github.com\/ciaranm\/cpaior2018-parallel-mcs-paper\/tree\/master\/james-cpp-parallel."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1145\/358080.358103","article-title":"Anomalies in Parallel Branch-and-bound Algorithms","volume":"27","author":"Lai","year":"1984","journal-title":"Commun. ACM"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1109\/TC.1986.5009434","article-title":"Coping with Anomalies in Parallel Branch-and-Bound Algorithms","volume":"C-35","author":"Li","year":"1986","journal-title":"IEEE Trans. Comput."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Ferreira, A., and Rolim, J. (1995). Asynchronous parallel branch and bound and anomalies. Parallel Algorithms for Irregularly Structured Problems, Springer.","DOI":"10.1007\/3-540-60321-2"},{"key":"ref_42","first-page":"421","article-title":"Embarrassingly Parallel Search in Constraint Programming","volume":"57","author":"Malapert","year":"2016","journal-title":"J. Artif. Int. Res."},{"key":"ref_43","first-page":"135","article-title":"Hardware Model Checking Competition 2014: An Analysis and Comparison of Model Checkers and Benchmarks","volume":"9","author":"Cabodi","year":"2016","journal-title":"Int. J. Satisf. Boolean Model. Comput. (JSAT)"},{"key":"ref_44","unstructured":"Bordeaux, L., Hamadi, Y., and Samulowitz, H. (2003, January 9\u201310). Experiments with Massively Parallel Constraint Solving. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, Acapulco, Mexico."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1613\/jair.2490","article-title":"SATzilla: Portfolio-based Algorithm Selection for SAT","volume":"32","author":"Xu","year":"2008","journal-title":"J. Artif. Intell. Res."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/s10601-008-9051-2","article-title":"A self-adaptive multi-engine Solver for Quantified Boolean Formulas","volume":"14","author":"Pulina","year":"2009","journal-title":"Constraints"},{"key":"ref_47","first-page":"245","article-title":"ManySAT: A Parallel SAT Solver","volume":"6","author":"Hamadi","year":"2009","journal-title":"Int. J. Satisf. Boolean Model. Comput."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Hellerman, S., and Rarick, D.C. (1972). The Partitioned Preassigned Pivot Procedure (P4). Sparse Matrices Their Appl., 67\u201376.","DOI":"10.1007\/978-1-4615-8675-3_6"},{"key":"ref_49","unstructured":"Gomes, C.P., Selman, B., and Kautz, H. (1998, January 26\u201330). Boosting Combinatorial Search Through Randomization. Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98) Tenth Conference on Innovative Applications of Artificial Intelligence (IAAI-98), Madison, WI, USA."},{"key":"ref_50","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_51","doi-asserted-by":"crossref","first-page":"1","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."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/8\/2\/48\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:30:04Z","timestamp":1760175004000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/8\/2\/48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,18]]},"references-count":51,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,6]]}},"alternative-id":["computation8020048"],"URL":"https:\/\/doi.org\/10.3390\/computation8020048","relation":{},"ISSN":["2079-3197"],"issn-type":[{"value":"2079-3197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,18]]}}}