Algorithmic complexity of triple Roman dominating functions on graphs

Given a graph $G=(V,E)$,  a  function  $f:V\to \{0,1,2,3,4\}$ is a triple Roman  dominating function (TRDF)  of $G$, for each vertex $v\in V$,  (i) if $f (v ) = 0 $, then  $v$ must have either one neighbour in $V_4$, or either two neighbours in $V_2 \cup  V_3$ (one neighbour in $V_3$) or either three neighbours in $V_2 $, (ii) if $f (v ) = 1 $, then $v$ must have either one neighbour in  $V_3 \cup  V_4$  or either two neighbours in $V_2 $, and if $f (v ) = 2 $, then $v$ must have one neighbour in $V_2 \cup  V_3\cup  V_4$. The triple Roman  domination number of $G$ is the  minimum weight of an TRDF  $f$  of $G$, where the weight of $f$ is $\sum_{v\in V}f(v)$.  The triple  Roman  domination problem is to compute the  triple Roman  domination number of a given graph.  In this paper, we study the triple  Roman  domination problem. We show that   the problem is NP-complete for  the  star convex bipartite  and the   comb convex bipartite graphs and is APX-complete for graphs of degree at~most~4. We propose a linear-time algorithm for computing  the triple Roman  domination number of proper interval graphs.  We also   give an $( 2 H(\Delta(G)+1) -1  )$-approximation algorithm  for solving the problem  for any graph $G$,  where   $  \Delta(G)$ is the maximum degree of $G$ and $H(d)$ denotes the first $d$ terms of the harmonic  series. In addition, we prove  that  for any $\varepsilon>0$  there is no  $(1/4-\varepsilon)\ln|V|$-approximation  polynomial-time   algorithm for solving  the problem on bipartite and split  graphs, unless NP $\subseteq$ DTIME $(|V|^{O(\log\log|V |)})$.