Meta-Heuristic Algorithms for Quasi Total Double Roman Domination Problem

¹ Department of Computer Science and Engineering, National Institute of Technology Andhra Pradesh, Tadepalligudem 534101, Andhra Pradesh, India
² Department of Computer Science and Engineering, National Institute of Technology Warangal, Hanamkonda 506004, Hanamkonda, Telangana, India
³ Department of Computer Science and Engineering, National Institute of Technology Warangal, Hanamkonda 506004, Telangana, India

^* Corresponding author: pvsr@nitw.ac.in

Received: 17 March 2025
Accepted: 1 August 2025

Abstract

Ensuring the resilience and security of complex networks, such as communication or power grids, requires strategies that can withstand failures and attacks. One such approach involves the use of domination models in graph theory. In this work, we focus on the quasi total double Roman domination problem (QTDRDP), a combinatorial optimization problem that models multi-layered defense strategies on graphs. Solving this problem involves assigning integer weights to nodes under specific constraints, aiming to minimize the total weight while maintaining strong structural security. Since computing the optimal assignment is NP-hard, we propose two metaheuristic approaches: one based on genetic algorithm (GA) and the other on artificial bee colony (ABC) optimization. To evaluate their effectiveness, we conducted experiments across multiple graph instances. The ABC algorithm achieved 120 successes out of 124 trials, significantly outperforming the GA algorithm. Statistical analysis confirms this difference is highly significant, with a critical p-value of 4.560507128 × 10⁻³¹, leading us to reject the null hypothesis. These results demonstrate that the ABC approach is more robust and efficient for solving the QTDRDP.