Hardness results of global Roman domination in graphs (Q6069177)

A Roman dominating function of \(G=(V,E)\) is a function \(f: V\rightarrow \{0, 1, 2\}\) such that every vertex \(v\) for which \(f(v)=0\) has a neighbor \(u\) with \(f(u)=2\). The weight of a Roman dominating function (RDF) \(f\) is \(w(f)=\sum_{v\in V}f(v)\). The Roman domination number of a graph \(G\), denoted by \(\gamma_R(G)\), is the minimum weight of all possible RDFs on \(G\). A global Roman dominating function (GRDF) of a graph \(G\) is a function \(f: V\rightarrow \{0, 1, 2\}\) such that \(f\) is a Roman dominating function of both \(G\) and its complement \(G\). The weight of \(f\) is \(f(V)=\sum_{u\in V} f (u)\). The minimum weight of a GRDF in a graph \(G\) is known as the global Roman domination number of \(G\) and is denoted by \(\gamma_{gR}(G)\). The authors show the NP-completeness of Decide Global Roman Domination in bipartite graphs and chordal graphs. They propose a polynomial-time algorithm for finding a minimum weight GRDF in threshold graphs. Also, they propose an approximation algorithm with approximation ratio \(4(1+\ln|V|)\), to approximate Minimum Global Roman Domination in a graph and show that Minimum Global Roman Domination cannot be approximated within \((1-\epsilon)\ln|V|\) for any \(\epsilon>0\) unless P=NP. Some open problems are presented in the last section.