Hardness and algorithmic results for Roman \{3\}-domination

A Roman $\{3\}$-dominating function on a graph $G = (V, E)$ is a function $f: V \rightarrow \{0, 1, 2, 3\}$ such that for each vertex $u \in V$, if $f(u) = 0$ then $\sum\limits_{v \in N(u)} f(v) \geq 3$ and if $f(u) = 1$ then $\sum\limits_{v \in N(u)} f(v) \geq 2$. The weight of a Roman $\{3\}$-dominating function $f$ is $\sum\limits_{u \in V} f(u)$. The objective of the \rtd{} problem 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, while it admits linear-time algorithms for bounded treewidth graphs, chain graphs and threshold graphs. In this paper, we initiate the study on parameterized complexity of the \rtd{} problem and prove that it is W[2]-hard parameterized by weight. Although the problem is FPT parameterized by treewidth (and hence by vertex cover number), we show that it does not admit a polynomial kernel parameterized by vertex cover number unless coNP $\subseteq$ NP$\slash$poly. Furthermore, we strengthen the known hardness result on chordal graphs by proving that it remains NP-complete on split graphs, a subclass of chordal graphs. On the positive side, we present a polynomial-time algorithm for block graphs, thereby resolving an open question posed by Chaudhary and Pradhan [Discrete Applied Mathematics, 2024].