algorithmic aspects of total roman {2}-domination in graphs

for a simple, undirected, connected graph g, a function h:v→{0,1,2} 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 ng(v) with weight 2, or at least two vertices x,y in ng(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 ∑p∈vh(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(δ−0.5)+1.5)-approximation algorithm for the mtr2dp and show that the same cannot have (1−δ)ln|v| ratio approximation algorithm for any δ 0 unless p=np. next, we show that mtr2dp is apx-hard for graphs with δ=4. finally, we show that the domination and tr2df problems are not equivalent in computational complexity aspects.