# An Approximation Algorithm for a Variant of Dominating Set Problem
## 4 Algorithm for the TDS Problem  
In this section, based on the LP relaxation techniques and the definition of the maximum dynamic degree in the second neighborhood of the vertex, we present a distributed approximation algorithm for the TDS problem by integrating the techniques in [37; 38]. Similarly to the assumption about dominating sets in [39; 40], for each vertex \(v_{i}\), if the vertex satisfies \(\sum_{v_{j}\in N(v_{i})}x_{j}\geq 1\), we say that the vertex is covered, and it will be colored black. Initially all vertices are colored white. Denote the _dynamic degree_ of a vertex \(v_{i}\) by \(\tilde{\delta}(v_{i})\), and use it to compute the number of white vertices in \(N(v_{i})\). Hence, when the algorithm starts, we have \(\tilde{\delta}(v_{i})=\delta(v_{i})\). Before analyzing our algorithm, we give a brief description of the algorithm. We introduce a variable \(x_{i}\) to every vertex \(v_{i}\), \(x_{i}\) is initialized as 0, as the algorithm runs, it gradually increases. The outer loop iteration \(\hbar\) is mainly to reduce \(\tilde{\delta}(v_{i})\). In the outer loop iteration of the algorithm, let \(\tau^{(1)}(v_{i})\) and \(\tau^{(2)}(v_{i})\) denote the maximum dynamic degree in \(N(v_{i})\) and the second neighborhood of \(v_{i}\), respectively. In each inner loop iteration, only the vertices that satisfy \(\tilde{\delta}(v_{i})\geq\tau^{(2)}(v_{i})^{\frac{\hbar}{\hbar+1}}\) increase the corresponding \(x_{i}\). We call these vertices _active_. For a white vertex \(v_{i}\), denote the number of active vertices in \(N(v_{i})\) by \(a(v_{i})\). If the vertex \(v_{i}\) is colored black, let \(a(v_{i})=0\). For each vertex \(v_{j}\in N(v_{i})\), let \(a^{(1)}(v_{i})\) denote the maximum \(a(v_{j})\). The key to solving the total dominating set problem in this paper is how to use the maximum dynamic degree in the second neighborhood of the vertex to design Algorithm 1. First, we illustrate the execution of Algorithm 1 with an example in Figure 1, where \(k=5\) and \(\Delta=5\). Figure 1a is the topology graph of the network with \(n=12\), the \(\tilde{\delta}(v_{i})\) of each vertex is marked on the graph, initial values of variables \(x_{i}\), \(\tilde{\delta}(v_{i})\), \(\tau^{(2)}(v_{i})\) are shown in Table 1. In Figure 1b, when \(\hbar=k-1=4\) and \(m=4\), \(v_{6},v_{8}\) satisfy \(\tilde{\delta}(v_{i})\geq\tau^{(2)}(v_{i})^{\frac{\hbar}{\hbar+1}}\), \(v_{6},v_{8}\) are active vertices, hence \(v_{6},v_{8}\) are selected, then the corresponding \(x_{6},x_{8}\) of \(v_{6},v_{8}\) are changed from 0 to \(a^{(1)}(v_{i})^{-\frac{m}{m+1}}\approx 0.57\). According to lines 20-22 of Algorithm 1, \(v_{7}\) satisfies \(\sum_{v_{j}\in N(v_{7})}x_{j}\geq 1\), hence \(v_{7}\) is colored black and we need to update \(\tilde{\delta}(v_{i})\). New values of variables \(\tau^{(2)}(v_{i})^{\frac{\hbar}{\hbar+1}}\), \(a(v_{i})\), \(a^{(1)}(v_{i})\), \(x_{i}\), \(\tilde{\delta}(v_{i})\) are shown in Table 1. When \(m=3\), new values of variables \(a(v_{i})\), \(a^{(1)}(v_{i})\), \(x_{i}\), \(\tilde{\delta}(v_{i})\) are shown in Table 1, we continue to execute the algorithm, and \(v_{4},v_{5},v_{11},v_{12}\) are colored black in Figure 1c. When \(m:2\to 0\), the dynamic degrees \(\tilde{\delta}(v_{i})\) of all vertices are less than the corrsponding \(\tau^{(2)}(v_{i})^{\frac{\hbar}{5}}\), so the outer iteration \(\hbar=4\) ends, and we update \(\tau^{(2)}(v_{i})\) in Table 1. By continuing to execute Algorithm 1, when \(\hbar:3\to 0\) and \(m:4\to 0\), the coloring process of all vertices and the changes in \(\tilde{\delta}(v_{i})\) are shown in Figure 1d-f. Initially, all \(x_{i}=0\). By executing the algorithm, the final \(x_{i}\) of all vertices is shown in Figure 1g. So, we can determine that the size of the output solution of Algorithm 1 is \(\sum\limits_{i=1}^{12}x_{i}=4+0.57=4.57\). The optimal TDS for this example is shown in Figure 2. Hence, we can see that the optimal TDS in this case is \(\{v_{4},v_{6},v_{8},v_{9}\}\), so its size is 4.