Improved Total Domination and Total Roman Domination in Unit Disk Graphs

Let G=(V, E) be a simple undirected graph with no isolated vertex. A set D_t⊆ V is a total dominating set of G if (i) D_t is a dominating set, and (ii) the set D_t induces a subgraph with no isolated vertex. The total dominating set of minimum cardinality is called the minimum total dominating set, and the size of the minimum total dominating set is called the total domination number (γ_t(G)). Given a graph G, the total dominating set (TDS) problem is to find a total dominating set of minimum cardinality. A Roman dominating function (RDF) on a graph G is a function f:V→{0,1,2} such that each vertex v∈ V with f(v)=0 is adjacent to at least one vertex u∈ V with f(u)=2. A RDF f of a graph G is said to be a total Roman dominating function (TRDF) if the induced subgraph of V_1∪ V_2 does not contain any isolated vertex, where V_i={u∈ V|f(u)=i}. Given a graph G, the total Roman dominating set (TRDS) problem is to minimize the weight, W(f)=∑_u∈ V f(u), called the total Roman domination number (γ_tR(G)). In this paper, we are the first to show that the TRDS problem is NP-complete in unit disk graphs (UDGs). Furthermore, we propose a 7.17- factor approximation algorithm for the TDS problem and a 6.03- factor approximation algorithm for the TRDS problem in geometric unit disk graphs. The running time for both algorithms is notably bounded by O(nlogk), where n represents the number of vertices in the given UDG and k represents the size of the independent set in (i.e., D and V_2 in TDS and TRDS problems, respectively) the given UDG.