Convex Recoloring of General Graphs: Formulations, Polyhedra, and Computational Experiments
2026-06-29 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a problem called convex recoloring, where you want to change the colors of some graph vertices so that each color forms a connected group, while changing as few colors as possible. This problem is hard even on simple graphs like paths and is important in biology for studying evolutionary trees. They focus on general graphs, not just trees, and develop four mathematical models to solve the problem exactly. Through experiments, they find that one method using a representatives model with a branch-and-cut algorithm works best overall.
vertex coloringconvex coloringgraphconnected subgraphconvex recoloring problemNP-hardmixed-integer linear programmingbranch-and-cut algorithmpolytopesphylogenetic trees
Authors
Boyue Lin, Phablo F. S. Moura, Roel Leus
Abstract
A vertex coloring of a graph is convex if the vertices of each color induce a connected subgraph. In the convex recoloring problem (CR), the goal is to find a convex coloring while minimizing the weight of recolored vertices, i.e., vertices assigned a color different from their original one. This problem was originally motivated by the study of phylogenetic trees in bioinformatics and is NP-hard even on paths. Most existing research focuses on trees, with only limited results available for general graphs. We advance the state of the art by developing exact solution methods for CR on general graphs. In particular, we propose four mixed-integer linear programming formulations, including a compact flow-based model and a representatives model, and design corresponding solution methods. We compare the polytopes associated with the linear relaxation of the proposed formulations. Computational experiments on benchmark instances and on new synthetic instances show that a branch-and-cut algorithm based on the representatives formulation performs best overall.