Unique Response Roman Domination: Complexity and Algorithms.

A function f : V (G) → { 0 , 1 , 2 } is called a Roman dominating function on G = (V (G) , E (G)) if for every vertex v with f (v) = 0 , there exists a vertex u ∈ N G (v) such that f (u) = 2 . A function f : V (G) → { 0 , 1 , 2 } induces an ordered partition (V 0 , V 1 , V 2) of V(G), where V i = { v ∈ V (G) : f (v) = i } for i ∈ { 0 , 1 , 2 } . A function f : V (G) → { 0 , 1 , 2 } with ordered partition (V 0 , V 1 , V 2) is called a unique response Roman function if for every vertex v with f (v) = 0 , | N G (v) ∩ V 2 | ≤ 1 , and for every vertex v with f (v) = 1 or 2, | N G (v) ∩ V 2 | = 0 . A function f : V (G) → { 0 , 1 , 2 } is called a unique response Roman dominating function (URRDF) on G if it is a unique response Roman function as well as a Roman dominating function on G. The weight of a unique response Roman dominating function f is the sum f (V (G)) = ∑ v ∈ V (G) f (v) , and the minimum weight of a unique response Roman dominating function on G is called the unique response Roman domination number of G and is denoted by u R (G) . Given a graph G, the Min-URRDF problem asks to find a unique response Roman dominating function of minimum weight on G. In this paper, we study the algorithmic aspects of Min-URRDF. We show that the decision version of Min-URRDF remains NP-complete for chordal graphs and bipartite graphs. We show that for a given graph with n vertices, Min-URRDF cannot be approximated within a ratio of n 1 - ε for any ε > 0 unless P = NP . We also show that Min-URRDF can be approximated within a factor of Δ + 1 for graphs having maximum degree Δ . On the positive side, we design a linear-time algorithm to solve Min-URRDF for distance-hereditary graphs. Also, we show that Min-URRDF is polynomial-time solvable for interval graphs, and strengthen the result by showing that Min-URRDF can be solved in linear-time for proper interval graphs, a proper subfamily of interval graphs. [ABSTRACT FROM AUTHOR]