Research Projects

This project focuses on the algorithmic study of Secure Domination and Roman Domination, and their variants. These parameters are NP-hard for general graphs and remain NP-hard even for some important subclasses of graphs. The researchers aim to explore alternatives such as exact algorithms for restricted graph classes, approximation algorithms for general and restricted graph classes, different heuristics, lower bounds on approximation ratio, combinatorial bounds on parameters, and parameterized complexity. The project will study Secure domination, Secure total domination, Co-secure domination, Roman domination, Triple Roman domination, and Global triple Roman domination. Secure domination and Secure total domination problems have been studied by several researchers, but the complexity status of these problems is still unknown for many important graph classes. Co-secure domination is NP-complete for bipartite, chordal, and planar graphs, while linear-time algorithms are known only for trees and proper interval graphs. C-secure domination is an interesting domination parameter, but no other algorithmic results are available. Roman domination is well-studied but has limited results on parameterized complexity. Triple Roman Domination and Global Triple Roman domination are recently introduced domination parameters, but they are NP-hard for bipartite and chordal graphs. Further research is needed to explore these problems' parameterized complexity and potential solutions.