# An Approximation Algorithm for a Variant of Dominating Set Problem
## 4 Algorithm for the TDS Problem
Theorem 3.1: _The output result \(\tilde{x}\) of Algorithm 1 is a feasible solution to linear programming relaxation of minimum total dominating set problem \(LP_{MTDS}\)._  
Proof of Theorem 3.1.: According to the execution of Algorithm 1, \(v_{i}\) will be colored 'black' only when the vertex \(v_{i}\) satifies \(\sum_{v_{j}\in N(v_{i})}x_{j}\geq 1\), i.e., \(x_{i}\) belongs to the feasible solution of \(LP_{MTDS}\). For each vertex \(v_{i}\), we can obtain \(\delta(v_{i})=0\) and \(\tau^{(2)}(v_{i})=0\) at the end of the iteration (\(\hbar=0,m=0\)), so the algorithm will terminate and all vertices are colored 'black'. Hence, the output result \(\tilde{x}\) of Algorithm 1 is a feasible solution for \(LP_{MTDS}\). Secondly, we analyze the approximation ratio of Algorithm 1. Theorem 3.2: _For a given network graph \(G\) and a positive integer \(k\), Algorithm 1 is a \(k(1+\Delta^{\frac{1}{k}})\Delta^{\frac{1}{k}}\)-approximation for the minimum total dominating set problem in \(G\)._  
Proof of Theorem 3.2.: According to the above description of \(z_{j}\), \(\sum z_{j}\) is equal to the sum of all the increased \(x_{i}\) in each outer loop iteration of Algorithm 1. From Lemma 3, we know that the \(z_{j}\) of all vertices satisfy \(z_{j}\leq\frac{1+\Delta^{1/k}}{\tau^{(1)}(v_{j})^{\frac{\hbar}{k+1}}}\) when each outer loop iteration ends. So, for each vertex \(v_{i}\), the sum of the \(z_{j}\) in \(N(v_{i})\) of the vertex \(v_{i}\) in the outer loop iteration is at most  
Figure 2:0 Figure 2:1 Figure 2:2 Figure 2:3  
where the second inequality holds because \(\tau^{(1)}(v_{j})\) is the maximum dynamic degree \(\tilde{\delta}(v_{i})\) in \(N(v_{j})\), \(v_{i}\in N(v_{j})\), hence \(\tau^{(1)}(v_{j})\geq\tilde{\delta}(v_{i})\). The fourth inequality follows from Lemma 1, \(\tilde{\delta}(v_{i})\leq\Delta^{\frac{1+1}{k}}\). Next, for each vertex \(v_{j}\), if we let \(y_{j}:=\frac{z_{j}}{(1+\Delta^{\frac{1}{k}})\Delta^{\frac{1}{k}}}\), then we can see that \(\sum_{v_{j}\in N(v_{i})}y_{j}\leq 1\) holds for each vertex \(v_{i}\in V\); hence, the \(\tilde{y}\) is a feasible solution of \(DLP_{MTDS}\). According to the weak duality theorem of linear programming, we can see that \(\sum y_{j}\) is a lower bound of an optimal TDS (\(TDS_{OPT}\)). Therefore, for each outer loop iteration, we can obtain  
Figure 2:4  
On the other hand, there are \(k\) iterations in the outer loop. So, we can obtain  
Figure 2:5  
We complete the proof. Finally, we analyze the running time of Algorithm 1. Theorem 3: _The number of communication rounds for Algorithm 1 is \(4k^{2}+O(k)\)._  
Proof of Theorem 3.: Firstly, it can be seen from the execution of the algorithm that every inner loop iteration needs to send four messages to all its neighbors in the algorithm, and there are \(k\) inner loop iterations, so it takes \(4k\) communication rounds. Secondly, every outer loop iteration needs to send two messages to all neighbors in the algorithm; hence, it takes \(4k+2\) communication rounds for each outer loop iteration. There are \(k\) outer loop iterations, so it takes \(k(4k+2)\) communication rounds for all outer loop iterations. Finally, we need to calculate some values before the outer loop iteration starts, which takes \(O(k)\) communication rounds. Hence, we can see that the number of communication rounds in the algorithm is \(k(4k+2)+O(k)=4k^{2}+O(k)\).