# An Approximation Algorithm for a Variant of Dominating Set Problem
## 4 Algorithm for the TDS Problem
Figure 2: The optimal total dominating set, in which \(k=5\) and \(\Delta=5\). Then, we analyze all the increased \(x_{i}\) in the inner loop iterations. It is difficult to directly compute the sum of all the increased \(x_{i}\). Therefore, for each vertex \(v_{i}\), we introduce a new variable \(z_{i}\). All \(x_{i}\) is initialized as 0 in line 4 of Algorithm 1. When the vertex \(v_{i}\) increases the \(x_{i}\) over time, the increased \(x_{i}\) is equally distributed to the \(z_{j}\) of the vertices in \(\{v_{j}\in N(v_{i})\mid v_{j}\text{ which is colored white before the increment of }x_{i}\text{ at line 17}\}\). Hence, we can obtain that \(\sum z_{j}\) is equal to the sum of all the increased \(x_{i}\) in each outer loop iteration. So, we only need to show that all \(z_{i}\) are bounded, as then all the increased \(x_{i}\) are also bounded. Lemma 3: _For each vertex \(v_{i}\in V\), we can obtain \(z_{i}\leq\frac{1+\Delta^{1/k}}{\tau^{(1)}(v_{i})^{\frac{k}{k+1}}}\) when each outer loop iteration ends._  
Proof of Lemma 3.: Due to all \(z_{i}=0\) in line 4, we only need to analyze a single outer loop iteration \(\hbar\). From the execution of the algorithm, we know that all \(x_{i}\) are increased in line 17. Therefore, \(z_{i}\) can only be increased there if the vertex \(v_{i}\) is white. For each white vertex \(v_{i}\), we need to discuss two cases during the current outer loop \(\hbar\). The first case is that, when all inner loop iterations end, \(v_{i}\) is still white. The second case is that, when the remaining inner loop iterations end, the vertex \(v_{i}\) is or becomes black. For the first case, we can easily obtain \(\sum_{\bar{v}\in N(v_{i})}x_{j}\leq 1\). Since all the increased \(x\) are distributed among at least \(\tau^{(2)}(v_{j})^{\frac{\hbar}{k+1}}z_{i}\), we can obtain  
\[z_{i} \leq\sum_{v_{j}\in N(v_{i})}\frac{x_{j}}{\tau^{(2)}(v_{j})^{\frac {\hbar}{k+1}}}\] \[\leq\frac{1}{\tau^{(1)}(v_{i})^{\frac{\hbar}{k+1}}}, \tag{1}\]  
where the second inequality holds because \(\tau^{(1)}(v_{i})\) and \(\tau^{(2)}(v_{j})\) denote the maximum dynamic degree \(\tilde{\delta}(v_{i})\) in \(N(v_{i})\) and the second neighborhood of \(v_{i}\), respectively, so we have \(\tau^{(2)}(v_{j})\geq\tau^{(1)}(v_{i})\). In the second case, we can see that only white vertices can increase their \(z\). Since the \(\tilde{\delta}(v_{i})\) will become smaller over time, these active vertices \(v_{j}\in N(v_{i})\) become active in the previous iterations. Hence, we can see that each active vertex \(x_{j}\) contributes to the \(z_{i}\) at most  
\[\frac{x_{j}}{\tilde{\delta}(v_{i})}\leq\frac{1}{\tau^{(1)}(v_{i})^{\frac{ \hbar}{k+1}}}\cdot a^{(1)}(v_{j})^{-\frac{\hbar}{k+1}}.\]  
Due to \(v_{i}\) having \(a(v_{i})\) active vertices in \(N(v_{i})\), the upper bound of the increased \(z_{i}\) is  
\[\frac{1}{\tau^{(1)}(v_{i})^{\frac{\hbar}{k+1}}}\cdot\frac{1}{a^{( 1)}(v_{j})^{\frac{\hbar}{m+1}}}\cdot a(v_{i}) \leq\frac{1}{\tau^{(1)}(v_{i})^{\frac{\hbar}{k+1}}}\cdot\frac{1} {a(v_{i})^{\frac{\hbar}{m+1}}}\cdot a(v_{i})\] \[=\frac{a(v_{i})^{\frac{\hbar}{m+1}}}{\tau^{(1)}(v_{i})^{\frac{ \hbar}{k+1}}}, \tag{2}\]  
where the first inequality follows from \(a(v_{i})\leq a^{(1)}(v_{j})\). Combining these results with Lemma 2, by adding (1) and (2), we can obtain \[z_{i} \leq\frac{1}{\tau^{(1)}(v_{i})^{\frac{\hbar}{k+1}}}+\frac{a(v_{i})^{ \frac{1}{k+1}}}{\tau^{(1)}(v_{i})^{\frac{\hbar}{k+1}}}\] \[\leq\frac{1+(\Delta^{\frac{\pi i+1}{k}})^{\frac{1}{k+1}}}{\tau^{(1 )}(v_{i})^{\frac{\hbar}{k+1}}}\] \[=\frac{1+\Delta^{1/k}}{\tau^{(1)}(v_{i})^{\frac{\hbar}{k+1}}}.\]  
We complete the proof. Based on the two lemmas, we will analyze the correctness, approximation ratio, and time complexity of Algorithm 1 in the following. Firstly, we show that the algorithm outputs a feasible solution to the linear programming relaxation of the minimum total dominating set problem.