# An Approximation Algorithm for a Variant of Dominating Set Problem
## 2 Related Work  
The concept of total domination in graphs was introduced in [14], and has been extensively studied in [18; 19; 20; 21]. [PERSON] et al. showed that the problem of finding an MTDS is NP-hard for general graphs [22] and is also MAX SNP-hard [23; 24; 25]. [PERSON] et al. [26] gave a linear time algorithm to compute the total domination number in a tree and showed that it is NP-complete to find an MTDS in undirected path graphs.  
[PERSON] et al. [27] proposed a heuristic algorithm to find a TDS whose size is at most \(n(1+\ln\delta)/\ln\delta\), where \(n\) is the number of vertices in \(G\) and \(\delta\geq 2\) is the minimum degree. An \((H_{\Delta}-\frac{1}{2})\)-approximation algorithm was presented in [28], where \(H_{i}=\sum\limits_{h=1}^{i}\frac{1}{h}\) is the \(i\)-th harmonic number. In [28], they also showed that there exist two constants, \(a\geq 3\) and \(b>0\), such that, for each \(\Delta\geq a\), it is NP-hard to approximate MTDS within factor \(\ln\Delta-b\ln\ln\Delta\) in bipartite graphs. [PERSON] [29] designed a greedy algorithm for the TDS problem; the performance ratio of the algorithm, \(\ln(\Delta-0.5)+1.5\), showed that it is NP-hard to approximate MTDS within factor \((1-\varepsilon)\ln|V|\) (\(\varepsilon>0\)) in sparse graphs, unless \(NP\subseteq DTIME(|V|^{O(\log\log|V|)})\), within factor \(391/390\) for three-bounded degree graphs, within factor \(681/680\) for three-regular graphs, and within factor \(250/249\) for four-regular graphs. More complexity results can be found in [20].  
[PERSON] et al. [30] showed that it is NP-hard to seek for a TDS \(T\) such that the subgraph \(G[T]\) belongs to a member of a given graph class, such as perfect graphs, bipartite graphs, asteroidal-triple-free graphs, interval graphs, unicyclic graphs, etc. By integrating a genetic algorithm and local search, [PERSON] et al. [31] designed a hybrid evolutionary algorithm for the TDS problem.  
In a planar graph without three cycles, a 16-approximation algorithm was presented in [16] for the TDS problem. [PERSON] and [PERSON] [17] presented a 9-approximation algorithm for the TDS problem in a planar graph without four cycles. [PERSON] [32] provided an algorithm to determine whether a graph satisfies \(\gamma_{t}(G)=2\gamma(G)\) or not, where \(\gamma_{t}(G)\) is the total domination number and \(\gamma(G)\) is the domination number of a graph \(G\). [PERSON] et al. [33] designed an improved local search framework to deal with the TDS problem by analyzing the algorithm in [31]. In [34], [PERSON] and [PERSON] first showed that it is NP-complete to find an MTDS in a given geometric unit disk graph. Next, they presented an 8-approximation algorithm for the TDS problem in the geometric unit disk graphs, with the running time of the algorithm as \(O(n\log k)\), where \(k\) is the size of the output result of their algorithm.  
By using the shifting strategy technique in [35], a polynomial time approximation scheme (PTAS) was given in [34] for the TDS problem in the geometric unit disk graphs.  
In a network, a scheduler is called fair if a continuously enabled node will eventually be selected by the scheduler. Otherwise, an unfair scheduler can only guarantee the progress of the global system [13]. For the minimal TDS problem, [PERSON] et al. [36] presented a self-stabilizing algorithm whose running time is exponential under the unfair central scheduler, i.e., only one enabled node performs a move step at a time. [PERSON] et al. [13] designed another self-stabilizing algorithm under the unfair distributed scheduler (any non-empty subset of enabled nodes will be selected to perform the move step); however, the running time of its algorithm is polynomial time.