Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287220221201Algorithmic aspects of total Roman $\{2\}$-domination in graphs1831921426410.22049/cco.2021.27063.1189ENChakradhar PNational Institute of Technology, WarangalVenkata Subba Reddy PNational Institute of Technology, WarangalJournal Article20201229For a simple, undirected, connected graph $G$, a function $h : V \rightarrow \lbrace 0, 1, 2 \rbrace$ is called a total Roman $\{2\}$-dominating function (TR2DF) if for every vertex $v$ in $V$ with weight $0$, either there exists a vertex $u$ in $N_G(v)$ with weight $2$, or at least two vertices $x, y$ in $N_G(v)$ each with weight $1$, and the subgraph induced by the vertices with weight more than zero has no isolated vertices. The weight of TR2DF $h$ is $\sum_{p \in V} h(p)$. The problem of determining TR2DF of minimum weight is called minimum total Roman \{2\}-domination problem (MTR2DP). We show that MTR2DP is polynomial time solvable for bounded treewidth graphs, threshold graphs and chain graphs. We design a $2 (\ln(\Delta - 0.5) + 1.5)$-approximation algorithm for the MTR2DP and show that the same cannot have $(1 - \delta) \ln |V|$ ratio approximation algorithm for any $\delta > 0$ unless $P = NP$. Next, we show that MTR2DP is APX-hard for graphs with $ \Delta=4$. Finally, we show that the domination and TR2DF problems are not equivalent in computational complexity aspects.https://comb-opt.azaruniv.ac.ir/article_14264_93fdd90572f39e706ad1feba0e1d4260.pdf