Approximation algorithm for the minimum partial connected Roman dominating set problem

Given a graph $$G=(V,E)$$ G = ( V , E ) and a function $$r:V\mapsto \{0,1,2\}$$ r : V ↦ { 0 , 1 , 2 } , a node $$v\in V$$ v ∈ V is said to be Roman dominated if $$r(v)=1$$ r ( v ) = 1 or there exists a node $$u\in N_G[v]$$ u ∈ N G [ v ] such that $$r(u)=2$$ r ( u ) = 2 , where $$ N_G[v]$$ N G [ v ] is the closed neighbor set of v in G. For $$i\in \{0,1,2\}$$ i ∈ { 0 , 1 , 2 } , denote $$V_r^i$$ V r i as the set of nodes with value i under function r. The cost of r is defined to be $$c(r)=|V_r^1|+2|V_r^2|$$ c ( r ) = | V r 1 | + 2 | V r 2 | . Given a positive integer $$Q\le |V|$$ Q ≤ | V | , the minimum partial connected Roman dominating set (MinPCRDS) problem is to compute a minimum cost function r such that at least Q nodes in G are Roman dominated and the subgraph of G induced by $$V_r^1\cup V_r^2$$ V r 1 ∪ V r 2 is connected. In this paper, we give a $$(3\ln |V|+9)$$ ( 3 ln | V | + 9 ) -approximation algorithm for the MinPCRDS problem.