A heuristic for the convex recoloring problem in graphs. (English) Zbl 07771165
Summary: We consider a coloring as a function that assigns a color to a vertex, regardless of the color of its neighbors. In this sense, a coloring is said to be convex if every set of all same colored vertices induces a connected subgraph. The Convex Recoloring Problem finds the minimum number of recolored vertices needed to turn a coloring convex. This problem is most commonly studied considering trees due to its origins in Computational Biology, but in this paper, we focus on general graphs. We propose a heuristic based on the Greedy Randomized Adaptive Search Procedure to solve the problem. We present computational experiments for our heuristic and compare it to an Integer Linear Programming (ILP) model from the literature. In these experiments, our heuristic recolored at most one vertex more than the ILP model, and it was also able to give better solutions when the ILP model was unable to find the optimal solution within the time limit. We also introduce a set of benchmark instances for the problem.
{© 2020 The Authors. International Transactions in Operational Research © 2020 International Federation of Operational Research Societies}
{© 2020 The Authors. International Transactions in Operational Research © 2020 International Federation of Operational Research Societies}
MSC:
| 90-XX | Operations research, mathematical programming |
References:
| [1] | Bapteste, E., vanIersel, L., Janke, A., Kelchner, S., Kelk, S., McInerney, J.O., Morrison, D.A., Nakhleh, L., Steel, M., Stougie, L., Whitfield, J., 2013. Networks: expanding evolutionary thinking. Trends in Genetics29, 8, 439-441. |
| [2] | Bar‐Yehuda, R., Feldman, I., Rawitz, D., 2008. Improved approximation algorithm for convex recoloring of trees. Theory of Computing Systems43, 1, 3-18. · Zbl 1140.68071 |
| [3] | Bondy, J.A., Murty, U.S.R., 2011. Graph Theory. Springer, London. |
| [4] | Campêlo, M.B., Freire, A.S., Lima, K.R., Moura, P.F.S., Wakabayashi, Y., 2016. The convex recoloring problem: polyhedra, facets and computational experiments. Mathematical Programming156, 1-2, 303-330. · Zbl 1346.90609 |
| [5] | Campêlo, M.B., Huiban, C.G., Sampaio, R.M., Wakabayashi, Y., 2013. On the complexity of solving or approximating convex recoloring problems. Proceedings of the 19th International Computing and Combinatorics Conference (COCOON’2013), Springer, Berlin, Heidelberg, pp. 614-625. · Zbl 1382.68100 |
| [6] | Chopra, S., Erdem, E., Kim, E., Shim, S., 2016. Column generation approach to the convex recoloring problem on a tree. Proceedings of the 16th Modeling and Optimization: Theory and Applications Conference (MOPTA’2016), Springer International Publishing, Cham, Switzerland, pp. 39-53. · Zbl 1380.05057 |
| [7] | Chopra, S., Filipecki, B., Lee, K., Ryu, M., Shim, S., Vyve, M.V., 2017. An extended formulation of the convex recoloring problem on a tree. Mathematical Programming165, 2, 529-548. · Zbl 1379.92034 |
| [8] | Chor,B., Fellows, M., Ragan, M.A., Razgon, I., Rosamond, F., Snir, S., 2007. Connected coloring completion for general graphs: algorithms and complexity. Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON’2007), Springer, Berlin, Heidelberg, pp. 75-85. · Zbl 1206.05040 |
| [9] | Demšar, J., 2006. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research7, 1-30. · Zbl 1222.68184 |
| [10] | Dezős, B., Jüttner, A., Kovács, P., 2011. LEMON—an open source C++ graph template library. Electronic Notes in Theoretical Computer Science264, 5, 23-45. |
| [11] | Feo, T.A., Resende, M.G.C., 1995. Greedy randomized adaptive search procedures. Journal of Global Optimization6, 2, 109-133. · Zbl 0822.90110 |
| [12] | Frenkel, Z., Kiat, Y., Izhaki, I., Snir, S., 2017. Convex recoloring as an evolutionary marker. Molecular Phylogenetics and Evolution107, 209-220. |
| [13] | Goldberg, L.A., Goldberg, P.W., Phillips, C.A., Sweedyk, E., Warnow, T., 1995. Minimizing phylogenetic number to find good evolutionary trees. In Apostolico, A. (ed.), Crochemore, M. (ed.), Park, K. (ed.) (eds) Combinatorial Pattern Matching. Springer, Berlin, Heidelberg, pp. 102-127. |
| [14] | López‐Ibáñez, M., Dubois‐Lacoste, J., Pérez Cáceres, L., Stützle, T., Birattari, M., 2016. The irace package: iterated racing for automatic algorithm configuration. Operations Research Perspectives3, 43-58. |
| [15] | Moran, S., Snir, S., 2008. Convex recolorings of strings and trees: definitions, hardness results and algorithms. Journal of Computer and System Sciences74, 5, 850-869. · Zbl 1160.68025 |
| [16] | Moran, S., Snir, S., Sung, W.K., 2011. Partial convex recolorings of trees and galled networks: tight upper and lower bounds. ACM Transactions on Algorithms7, 4, 42. · Zbl 1295.05236 |
| [17] | Moura, P.F.S., 2017. Graph colorings and digraph subdivisions. PhD thesis, Instituto de Matemática e Estatística, Universidade de São Paulo. |
| [18] | Resende, M.G., Ribeiro, C.C., 2005. GRASP with path‐relinking: recent advances and applications. In Ibaraki, T. (ed.), Nonobe, K. (ed.), Yagiura, M. (ed.) (eds) Metaheuristics: Progress as Real Problem Solvers. Springer, Berlin, pp. 29-63. |
| [19] | Resende, M.G., Ribeiro, C.C., 2010. Greedy randomized adaptive search procedures: advances, hybridizations, and applications. In Gendreau, M. (ed.), Potvin, J.Y. (ed.) (eds) Handbook of Metaheuristics (2nd edn). Springer, Berlin, pp. 283-319. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
