Branch-and-Cut Algorithms for Colorful Components Problems
- 1 May 2026
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 38 (3) , 693-709
Abstract
We tackle three optimization problems in which a colored graph, where each node is assigned a color, must be partitioned into colorful connected components. A component is defined as colorful if each color appears at most once. The problems differ in the objective function, which determines which partition is the best one. These problems have applications in community detection, cybersecurity, and bioinformatics. We present integer nonlinear formulations, which are then linearized using standard techniques. To solve these formulations, we develop exact branch-and-cut algorithms, embedding various improving techniques, such as valid inequalities, bounds limiting the number of variables, and warm-start and preprocessing techniques. Extensive computational tests on benchmark instances demonstrate the effectiveness of the proposed procedures. The branch-and-cut algorithms can solve reasonably sized instances efficiently. To the best of our knowledge, we are the first to propose an exact algorithm for solving these problems. History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms & Applications. Funding: The work of M. Cerulli was partially funded by project “SEcurity and RIghts in the CyberSpace” [Grant PE00000014] under the MUR National Recovery and Resilience Plan funded by the European Union - NextGenerationEU. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0927 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0927 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Exact and Heuristic Solution Approaches for the Cluster Deletion Problem on General GraphsNetworks, 2025
- A survey on blockchain shardingISA Transactions, 2023
- Mathematical programming formulations for the Collapsed k-Core ProblemEuropean Journal of Operational Research, 2023
- The maximum clique interdiction problemEuropean Journal of Operational Research, 2019
- Graph modification problem for some classes of graphsJournal of Discrete Algorithms, 2016
- Matching interdictionDiscrete Applied Mathematics, 2010
- BAliBASE 3.0: Latest developments of the multiple sequence alignment benchmarkProteins: Structure, Function, and Bioinformatics, 2005
- Cluster graph modification problemsDiscrete Applied Mathematics, 2004
- A cutting plane algorithm for a clustering problemMathematical Programming, 1989
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problemsMathematical Programming, 1976