{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T19:27:36Z","timestamp":1764962856549,"version":"3.46.0"},"reference-count":23,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T00:00:00Z","timestamp":1764374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Three optimization problems based on node-colored undirected graphs are the subject of the present study. These problems model real-world applications in several domains, such as cybersecurity, bioinformatics, and social networks, although they have a similar abstract representation. In all of the problems, the goal is to partition the graph into colorful connected components, which means that in each of the connected components, a color can appear in at most one node. The problems are optimized according to different objective functions, leading to different optimal partitions. We propose a compact Mixed Integer Linear Programming formulation for each of the three problems. These models are based on spanning trees, represented through multi-commodity flows. The compact nature of the new linear models is easier to handle than the approaches that previously appeared in the literature. These were based on models with an exponential number of constraints, which, therefore, required complex solving techniques based on the dynamic generation of constraints within a branch-and-cut framework. Computational experiments carried out on the standard benchmark instances for the problems show the potential of the new compact methods, which, once fed into modern state-of-the-art solvers, are able to obtain results better than the previous algorithmic approaches. As an outcome of the experimental campaign, a dozen instances of the different problems considered are closed for the first time.<\/jats:p>","DOI":"10.3390\/a18120759","type":"journal-article","created":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T18:42:02Z","timestamp":1764960122000},"page":"759","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Compact Models for Some Cluster Problems on Node-Colored Graphs"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0229-0465","authenticated-orcid":false,"given":"Roberto","family":"Montemanni","sequence":"first","affiliation":[{"name":"Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8128-2067","authenticated-orcid":false,"given":"Derek H.","family":"Smith","sequence":"additional","affiliation":[{"name":"Faculty of Computing, Engineering and Science, University of South Wales, Pontypridd CF37 1DL, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4155-0688","authenticated-orcid":false,"given":"Pongchanun","family":"Luangpaiboon","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, Thammasat School of Engineering, Thammasat University, Pathum Thani 12120, Thailand"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7600-9752","authenticated-orcid":false,"given":"Pasura","family":"Aungkulanon","sequence":"additional","affiliation":[{"name":"Department of Materials Handling and Logistics Engineering, Faculty of Engineering, King Mongkut\u2019s University of Technology North Bangkok, Bangkok 10800, Thailand"}]}],"member":"1968","published-online":{"date-parts":[[2025,11,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Przytycka, T.M., and Sagot, M.F. (2011). OMG! Orthologs in Multiple Genomes\u2014Competing Graph-Theoretical Formulations. Algorithms in Bioinformatics, Proceedings of the WABI 2011, Saarbr\u00fccken, Germany, 5\u20137 September 2011, Springer.","DOI":"10.1007\/978-3-642-23038-7"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Bruckner, S., H\u00fcffner, F., Komusiewicz, C., Niedermeier, R., Thiel, S., and Uhlmann, J. (2012). Partitioning into colorful components by minimum edge deletions. Combinatorial Pattern Matching, Proceedings of the 23rd Annual Symposium, CPM 2012, Helsinki, Finland, 3\u20135 July 2012, Springer.","DOI":"10.1007\/978-3-642-31265-6_5"},{"key":"ref_3","unstructured":"Adamaszek, A., and Popa, A. (2014). Algorithmic and hardness results for the colorful components problems. LATIN 2014: Theoretical Informatics, Proceedings of the 11th Latin American Symposium, Montevideo, Uruguay, 31 March\u20134 April 2014, Springer."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Archetti, C., Cerulli, M., and Sorgente, C. (2025). Branch-and-cut algorithms for colorful components problems. INFORMS J. Comput.","DOI":"10.1287\/ijoc.2024.0927"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00021","article-title":"Approximation algorithms for some graph partitioning problems","volume":"4","author":"He","year":"2000","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.tcs.2007.02.026","article-title":"The multi-multiway cut problem","volume":"377","author":"Avidor","year":"2007","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Misra, N. (2018). On the parameterized complexity of colorful components and related problems. International Workshop on Combinatorial Algorithms, Proceedings of the IWOCA 2018, Singapore, 16\u201319 July 2018, Springer.","DOI":"10.1007\/978-3-319-94667-2_20"},{"key":"ref_8","unstructured":"Bruckner, S., H\u00fcffner, F., Komusiewicz, C., Niedermeier, R., and Wernicke, S. (2013, January 13\u201317). Correcting interlanguage links in Wikipedia: A colorful components approach. Proceedings of the 22nd International Conference on World Wide Web, Rio de Janeiro, Brazil."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Chandrasekaran, K., Karp, R., Moreno-Centeno, E., and Vempala, S. (2011, January 23\u201325). Algorithms for Implicit Hitting Set Problems. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA.","DOI":"10.1137\/1.9781611973082.48"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1287\/opre.1120.1139","article-title":"The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment","volume":"61","author":"Karp","year":"2013","journal-title":"Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01589097","article-title":"A cutting plane algorithm for a clustering problem","volume":"45","author":"Wakabayashi","year":"1989","journal-title":"Math. Program."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Blin, G., and Popa, A. (2015). Approximation and hardness results for the maximum edges in transitive closure problem. Combinatorial Algorithms, Springer International Publishing.","DOI":"10.1007\/978-3-319-19315-1_2"},{"key":"ref_13","first-page":"62","article-title":"Complexity and approximation for colorful component problems","volume":"94","author":"Dondi","year":"2018","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1287\/opre.11.3.344","article-title":"Multi-commodity network flows","volume":"11","author":"Hu","year":"1963","journal-title":"Oper. Res."},{"key":"ref_15","unstructured":"Perron, L., and Didier, F. (2025, October 10). Google OR-Tools-CP-SAT. Available online: https:\/\/developers.google.com\/optimization\/cp\/cp_solver\/."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Montemanni, R., and Dell\u2019Amico, M. (2023). Solving the parallel drone scheduling traveling salesman problem via constraint programming. Algorithms, 16.","DOI":"10.3390\/a16010040"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"106514","DOI":"10.1016\/j.cor.2023.106514","article-title":"Parallel drone scheduling vehicle routing problems with collective drones","volume":"163","author":"Montemanni","year":"2024","journal-title":"Comput. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"100101","DOI":"10.1016\/j.ejco.2024.100101","article-title":"A compact model for the home healthcare routing and scheduling problem","volume":"13","author":"Montemanni","year":"2025","journal-title":"EURO J. Comput. Optim."},{"key":"ref_19","unstructured":"Ball, M.O., Magnanti, T.L., Monma, C.L., and Nemhauser, G.L. (1995). Optimal trees. Handbook in Operations Research and Management Science: Networks Models, Elsevier."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/s00357-024-09483-1","article-title":"Clustering with Minimum Spanning Trees: How Good Can It Be?","volume":"42","author":"Gagolewski","year":"2025","journal-title":"J. Classif."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/prot.20527","article-title":"Balibase 3.0: Latest developments of the multiple sequence alignment benchmark","volume":"61","author":"Thompson","year":"2005","journal-title":"Proteins Struct. Funct. Bioinform."},{"key":"ref_22","unstructured":"Gurobi Optimization, LLC (2025). Gurobi 12.0.3, Gurobi Optimization, LLC."},{"key":"ref_23","unstructured":"PassMark Software Pty Ltd (2025). CPU Benchmarks, PassMark Software Pty Ltd."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/12\/759\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T18:58:59Z","timestamp":1764961139000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/12\/759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,29]]},"references-count":23,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["a18120759"],"URL":"https:\/\/doi.org\/10.3390\/a18120759","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,29]]}}}