Genetic Algorithm and Integer Linear Programming for the Total Roman Domination Problem

• Heric da Silva Cruz UFC
• Atílio Gomes Luiz UFC

DOI: https://doi.org/10.5753/etc.2025.8041

Abstract

Given a graph G = (V,E), a function f : V → {0, 1, 2} is a total Roman dominating function (TRDF) if every v ∈ V with f(v) = 0 has a neighbor u ∈ V with f(u) = 2, and every v ∈ V with f(v) > 0 has a neighbor u ∈ V with f(u) > 0. The weight of f is given by ω(f) = ∑_v∈V f(v), and the total Roman domination number of G is γ_tR(G) = min{ω(f) : f is a TRDF of G}. In this work, we propose an integer linear program and a genetic algorithm to compute γ_tR(G), evaluating the effectiveness of the latter on various instances.

References

Abdollahzadeh Ahangar, H., Henning, M., Samodivkin, V., and G. Yero, I. (2016). Total roman domination in graphs. Applicable Analysis and Discrete Mathematics, 10:17–17.

Billore, A. and Reddy, P. V. S. (2023). Genetic algorithm based approach for solving roman 3-domination problem. In 2023 International Conference on Computer, Electronics & Electrical Engineering & their Applications (IC2E3), pages 1–6.

Cai, Q., Fan, N., Shi, Y., and and, S. Y. (2022). Integer linear programming formulations for double roman domination problem. Optimization Methods and Software, 37(1):1–22.

Cockayne, E. J., Dreyer, P. A., Hedetniemi, S. M., and Hedetniemi, S. T. (2004). Roman domination in graphs. Discrete Mathematics, 278(1):11–22.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., USA, 1st edition.

Goldberg, D. E. and Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. volume 1 of Foundations of Genetic Algorithms, pages 69–93. Elsevier.

Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press, Cambridge, MA, USA.

Katoch, S., Chauhan, S. S., and Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 80:8091–8126.

Khandelwal, A., Srivastava, K., and Saran, G. (2021). On roman domination of graphs using a genetic algorithm. In Singh, V., Asari, V. K., Kumar, S., and Patel, R. B., editors, Computational Methods and Data Engineering, pages 133–147, Singapore. Springer Singapore.

Kora, P. and Yadlapalli, P. (2017). Crossover operators in genetic algorithms: A review. International Journal of Computer Applications, 162:34–36.

Liu, C.-H. and Chang, G. J. (2013). Roman domination on strongly chordal graphs. Journal of Combinatorial Optimization, 26(3):608–619.

López-Ibáñez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Birattari, M., and Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43–58.

National Institute of Standards and Technology. Matrix Market: A Visual Repository of Test Data for Sparse Matrix Algorithms. Disponível em: [link]. Data de acesso: Março de 2025.

Poureidi, A. and Fathali, J. (2023). Algorithmic results in roman dominating functions on graphs. Information Processing Letters, 182:106363.

Rossi, R. A. and Ahmed, N. K. (2015). The network data repository with interactive graph analytics and visualization. In AAAI. Disponível em: [link]. Data de acesso: Março de 2025.