Hardness and Algorithmic Results for Roman \{3\}-Domination

Abstract

A Roman $\{3\}$-dominating function on a graph $G=(V,E)$ is a function $f:V\to \{0,1,2,3\}$ such that for each vertex $u\in V$, if $f(u)=0$ then ${\sum }_{v\in N(u)}f(v)\ge 3$ and if $f(u)=1$ then ${\sum }_{v\in N(u)}f(v)\ge 2$. The weight of a Roman $\{3\}$-dominating function $f$ is ${\sum }_{u\in V}f(u)$. The objective of \rtd{} is to compute a Roman $\{3\}$-dominating function of minimum weight. The problem is known to be NP-complete on chordal graphs, star-convex bipartite graphs and comb-convex bipartite graphs. In this paper, we study the complexity of \rtd{} and show that the problem is NP-complete on split graphs. In addition, we prove that the problem is W[2]-hard parameterized by weight. On the positive front, we present a polynomial-time algorithm for block graphs, thereby resolving an open question posed by Chaudhary and Pradhan [Discrete Applied Mathematics, 2024].

20 pages, 4 figures