Abstract
A coloring of the vertices of a graph \(G\) is convex if the vertices receiving a common color induce a connected subgraph of \(G\). We address the convex recoloring problem: given a graph \(G\) and a coloring of its vertices, recolor a minimum number of vertices of \(G\), so that the resulting coloring is convex. This problem is known to be \(\fancyscript{NP}\)-hard even when \(G\) is a path. We show an integer programming formulation for arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and the corresponding separation algorithms. We also present a branch-and-cut algorithm that we have implemented for the special case of trees, and show the computational results obtained with a large number of instances. We consider instances which are real phylogenetic trees. The experiments show that this approach can be used to solve instances up to \(1500\) vertices in 2 h, comparing favorably to other approaches that have been proposed in the literature.
Similar content being viewed by others
References
Bodlaender, H.L., Fellows, M.R., Langston, M.A., Ragan, M.A., Rosamond, F.A., Weyer, M.: Quadratic kernelization for convex recoloring of trees. Algorithmica 61(2), 362–388 (2011)
Campêlo, M., Lima, K.R., Moura, P.F., Wakabayashi, Y.: Polyhedral studies on the convex recoloring problem. Electron. Notes Discrete Math. 44(0), 233–238 (2013); [In: Proceedings of LAGOS’13 - VII Latin-American Algorithms, Graphs and Optimization Symposium]
Campêlo, M.B., Huiban, C.G., Sampaio, R.M., Wakabayashi, Y.: On the complexity of solving or approximating convex recoloring problems. Lecture Notes in Computer Science 7936, 614–625 (2013); [In: Proceedings of the 19th International Conference on Computing and Combinatorics]
Chor, B., Fellows, M., Ragan, M., Razgon, I., Rosamond, F., Snir, S.: Connected coloring completion for general graphs: algorithms and complexity. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4598, 75–85 (2007)
Kammer, F., Tholey, T.: The complexity of minimum convex coloring. Discrete Appl. Math. 160, 810–833 (2012)
Kanj, I.A., Kratsch, D.: Convex recoloring revisited: Complexity and exact algorithms. In: Proceedings of the 15th Annual International Conference on Computing and Combinatorics, COCOON ’09, pp. 388–397 (2009)
Lima, K.R., Wakabayashi, Y.: Convex recoloring of paths. Electron. Notes Discrete Math. 37(0), 165–170 (2011); In: LAGOS’11 - VI Latin-American Algorithms, Graphs and Optimization Symposium
Moran, S., Snir, S.: Convex recolorings of strings and trees: definitions, hardness results, and algorithms. In: Proceedings WADS 2005: 9th International Workshop on Algorithms and Data Structures, pp. 218–232 (2005)
Moran, S., Snir, S.: Efficient approximation of convex recolorings. J. Comput. Syst. Sci. 73(7), 1078–1089 (2007)
Moran, S., Snir, S.: Convex recolorings of strings and trees: definitions, hardness results and algorithms. J. Comput. Syst. Sci. 74(5), 850–869 (2008)
Moran, S., Snir, S., Sung, W.K.: Partial convex recolorings of trees and galled networks: tight upper and lower bounds. ACM Trans. Algorithms 7(4), 42:1–42:20 (2011)
Ponta, O., Hüffner, F., Niedermeier, R.: Speeding up dynamic programming for some NP-hard graph recoloring problems. In: Proceedings of the 5th international conference on Theory and applications of models of computation, TAMC’08, pp. 490–501. Springer, (2008)
Razgon, I.: A \(2^{O(k)}poly(n)\) algorithm for the parameterized convex recoloring problem. Inf. Process. Lett. 104(2), 53–58 (2007)
Acknowledgments
The authors thank the referees for the comments and suggestions that helped improving the presentation of this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by CNPq (Proc. 141997/2009-5, 477203/2012-4, 303987/2010-3, 307627/2010-1, 480608/2011-3, 132998/2011-4, 456792/2014-7), Fapesp (Proc. 2012/17585-9, 2013/03447-6, 2013/19179-0) and Projects USP MaCLinC/NUMEC, CAPES STIC-AmSud and FUNCAP/PRONEM.
Rights and permissions
About this article
Cite this article
Campêlo, M., Freire, A.S., Lima, K.R. et al. The convex recoloring problem: polyhedra, facets and computational experiments. Math. Program. 156, 303–330 (2016). https://doi.org/10.1007/s10107-015-0880-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-015-0880-7