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

A Roman \3\-dominating function on a graph $G = (V, E)$ is a function f: V → \0, 1, 2, 3\ such that for each vertex u ∈ V, if $f(u) = 0$ then ∑v ∈ N(u) f(v) ≥ 3 and if $f(u) = 1$ then ∑v ∈ N(u) f(v) ≥ 2. The weight of a Roman \3\-dominating function f is ∑u ∈ V f(u). The objective of {} 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 {} 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].