# An Approximation Algorithm for a Variant of Dominating Set Problem
## 4 Algorithm for the TDS Problem
Therefore, we only need to prove that \(\tau^{(2)}(v_{i})^{\frac{h}{k+1}}\leq\Delta^{\frac{h}{k}}\) for each vertex \(v_{i}\). Figure 1: An illustration of Algorithm 1, in which \(k=5\) and \(\Delta=5\). (**a**) is the topology graph, \(\tilde{\delta}(v_{i})\) of each vertex is marked on the graph. (**b**) When \(\hbar=k-1=4\) and \(m=4\), \(v_{7}\) is colored black and we update \(\tilde{\delta}(v_{i})\). (**c**) When \(\hbar=k-1=4\) and \(m:3\to 0\), \(v_{4},v_{5},v_{11},v_{12}\) are colored black and we update \(\tilde{\delta}(v_{i})\). (**d**) When \(\hbar=k-2=3\) and \(m:4\to 0\), \(v_{3},v_{6},v_{10}\) are colored black and we update \(\tilde{\delta}(v_{i})\). (**e**) When \(\hbar=k-3=2\) and \(m:4\to 0\), \(v_{8},v_{9}\) are colored black and we update \(\tilde{\delta}(v_{i})\). (**f**) When \(\hbar=k-4=1\) and \(m:4\to 0\), \(v_{1},v_{2}\) are colored black and we update \(\tilde{\delta}(v_{i})\). By executing the algorithm, the final \(x_{i}\) of all vertices is shown in (**g**). Based on the induction hypothesis, we can obtain, for each vertex \(v_{i}\), \(\tilde{\delta}(v_{i})\leq\Delta^{\frac{h+1}{k+1}}\) in each outer loop iteration start. As \(\tau^{(2)}(v_{i})\) is the maximum dynamic degree in the second neighborhood of \(v_{i}\), we can obtain \(\tau^{(2)}(v_{i})\leq\Delta^{\frac{h+1}{k}}\) for each vertex \(v_{i}\). Hence, we have  
\[\tau^{(2)}(v_{i})^{\frac{h}{k+1}}\leq\Delta^{\frac{h+1}{k}\cdot\frac{h}{k+1}}= \Delta^{\frac{h}{k}}.\]  
We complete the proof. **Lemma 2**: _Before assigning a new \(x_{i}\) to \(v_{i}\), for each vertex \(v_{i}\in V\), we can obtain_  
\[a(v_{i})\leq\Delta^{\frac{m+1}{k}}.\]  
Proof of Lemma 2.: We also prove it by using induction. Firstly, when \(m=k-1\), \(\Delta^{\frac{m+1}{k}}=\Delta\). According to the definitions of \(a(v_{i})\) and \(\Delta\), it is clear that \(a(v_{i})\leq\Delta\). Secondly, when \(m\
eq k-1\), we need to prove that all vertices \(v_{i}\) with \(a(v_{i})>\Delta^{\frac{m}{k}}\) are colored black when the inner loop iteration ends. We apply the induction hypothesis to the other inner loop iterations, so we can obtain \(a(v_{i})\leq\Delta^{\frac{m+1}{k}}\) for each vertex \(v_{i}\). Hence, the \(x_{j}\) of each active vertex \(v_{j}\) is assigned in line 17 as  
Table 1.0  
If each vertex \(v_{i}\) has more than \(\Delta^{\frac{m}{k}}\) active vertices in \(N(v_{i})\), \(v_{i}\) will be covered. So, the conclusion holds. \begin{table}
\begin{tabular}{c c c c c c c c c c c c c} \hline \hline  & \multicolumn{3}{c}{\(v_{1}\)} & \(v_{2}\) & \(v_{3}\) & \(v_{4}\) & \(v_{5}\) & \(v_{6}\) & \(v_{7}\) & \(v_{8}\) & \(v_{9}\) & \(v_{10}\) & \(v_{11}\) & \(v_{12}\) \\ \hline \multirow{4}{*}{initial} & \(x_{i}\) & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \cline{2-11}  & \(\tilde{\delta}(v_{i})\) & 1 & 1 & 1 & 2 & 1 & 5 & 3 & 4 & 3 & 2 & 3 & 2 \\ \cline{2-11}  & \(\tau^{(2)}(v_{i})\) & 4 & 4 & 5 & 5 & 5 & 4 & 5 & 5 & 4 & 4 & 5 & 5 \\ \hline \multirow{4}{*}{\(\hbar=4\)} & \(\tau^{(2)}(v_{i})^{\frac{2}{3}}\) & 3.03 & 3.03 & 3.62 & 3.62 & 3.62 & 3.03 & 3.62 & 3.03 & 3.03 & 3.62 & 3.62 \\ \cline{2-11}  & \(a(v_{i})\) & 0 & 1 & 0 & 1 & 1 & 0 & 2 & 0 & 1 & 1 & 1 & 1 \\ \cline{2-11}  & \(a^{(1)}(v_{i})\) & 1 & 0 & 1 & 0 & 0 & 2 & 1 & 2 & 1 & 1 & 2 & 1 \\ \cline{2-11}  & \(x_{i}\) & 0 & 0 & 0 & 0 & 0 & 0.57 & 0 & 0.57 & 0 & 0 & 0 & 0 \\ \cline{2-11}  & \(\tilde{\delta}(v_{i})\) & 1 & 1 & 1 & 2 & 1 & 4 & 3 & 3 & 3 & 2 & 2 & 2 \\ \hline \multirow{4}{*}{\(\hbar=4\)} & \(a(v_{i})\) & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \cline{2-11}  & \(a^{(1)}(v_{i})\) & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ \cline{2-11}  & \(x_{i}\) & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0.57 & 0 & 0 & 0 & 0 \\ \cline{2-11}  & \(\tilde{\delta}(v_{i})\) & 1 & 1 & 0 & 2 & 1 & 0 & 2 & 3 & 3 & 2 & 1 & 1 \\ \cline{2-11}
2\(\stackrel{{ m}}{{0}}\) & \(\tau^{(2)}(v_{i})\) & 3 & 3 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 2 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Initial and new values of some variables.