On algorithmic complexity of double Roman domination (Q2197468)

A double Roman dominating function on a graph \(G=(V,E)\) is a function \(f:V\rightarrow \{0,1,2,3\}\) such that every vertex \(v \in V\) with \(f(v)=0\) is either adjacent to a vertex \(u\) with \(f(u)=3\) or two distinct vertices \(x\) and \(y\) with \(f(x)=f(y)=2\), and every vertex \(v \in V\) with \(f(v)=1\) is adjacent to a vertex \(u\) with \(f(u)\geq 2\). The weight of \(f\) is the sum \(f(V)=\sum_{v \in V}f(v)\). The minimum weight of a double Roman domination function of \(G\), denoted by \(\gamma_{\mathrm{dR}}(G)\) is called the double Roman domination number of graph \(G\). A graph \(G\) is a double Roman graph if \(\gamma_{\mathrm{dR}}(G)=3\gamma(G)\), where \(\gamma(G)\) is the domination number of \(G\). In the paper under review, the authors prove (a) the decision problem associated with double Roman domination is NP-complete even when restricted to planar graphs (b) the problem of deciding whether a given graph is double Roman is NP-hard even when restricted to bipartite or chordal graphs. The authors also propose a linear algorithm to compute the domination number and the double Roman domination number of a given unicyclic graph and conclude with a linear algorithm to decide whether a given unicyclic graph is double Roman graph.