Algorithmic complexity of weakly connected Roman domination in graphs.

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 } which satisfies the following conditions is called a weakly connected Roman dominating function (WCRDF) of G with weight h (V) = ∑ p ∈ V h (p). (C1). For all q ∈ V with h (q) = 0 there exists a vertex r such that (q , r) ∈ E and h (r) = 2 and (C2). The graph with vertex set V (G) and edge set { (p , z) : h (p) ≥ 1 or h (z) ≥ 1 or both } is connected. The problem of determining WCRDF of minimum weight is called minimum weakly connected Roman domination problem (MWCRDP). In this paper, we show that MWCRDP is polynomial time solvable for bounded treewidth graphs, threshold graphs and chain graphs. We design a 2 (1 +) (1 + ln (Δ − 1)) -approximation algorithm for the MWCRDP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless P = N P. Next, we show that MWCRDP is APX-hard for graphs with Δ = 4. We also show that the domination and weakly connected Roman domination problems are not equivalent in computational complexity aspects. Finally, two different integer linear programming formulations for MWCRDP are proposed. [ABSTRACT FROM AUTHOR]