# An Approximation Algorithm for a Variant of Dominating Set Problem
## 4 Algorithm for the TDS Problem
The performance ratio of Algorithm 1 is \(\frac{4.57}{4}\approx 1.14\) in this case. Second, we give some lemmas that will be used to analyze the approximation ratio of Algorithm 1. ```
1:Input: Given a graph \(G=(V,E)\), a positive integer \(k\). 2:A feasible solution \(\overline{\pi}\) for \(LP_{MTDS}\). 3: initially \(x_{i}:=0\), \(\tilde{\delta}(v_{i}):=\delta(v_{i})\), \(V^{\prime}:=V\);
4: calculate \(\delta^{(2)}(v_{i})\), set \(\tau^{(2)}(v_{i}):=\delta^{(2)}(v_{i})\);
5:for\(\hbar:=k-1\) to 0 by \(-1\)do
6: (\(\star\)\(\delta(v_{i})\), set \(z_{i}:=0\)\(\star\))
7:for\(m:=k-1\) to 0 by \(-1\)do
8:if\(\tilde{\delta}(v_{i})\geq\tau^{(2)}(v_{i})^{\frac{2}{k+1}}\), \(v_{i}\in V^{\prime}\)then
9: send 'active vertex' to all neighbors
10:endif
11: calculate \(a(v_{i}):=|\{v_{j}\in N(v_{i})|\text{the vertex $v_{j}$ is active vertex}\}|\)
12:if the vertex \(v_{i}\) is colored 'black'then
13:\(a(v_{i}):=0\)
14:endif
15: send \(a(v_{i})\) to all vertices in \(N(v_{i})\);
16: calculate \(a^{(1)}(v_{i}):=\max_{j\in N(v_{i})}\{a(v_{j})\}\);
17: (\(\star\)\(a(v_{i}),a^{(1)}(v_{i})\)\(\star\))
18:if\(\delta(v_{i})\geq\tau^{(2)}(v_{i})^{\frac{2}{k+1}}\), \(v_{i}\in V^{\prime}\)then
19:\(x_{i}:=\max\{x_{i},a^{(1)}(v_{i})^{-\frac{m}{m+1}}\}\)
20:endif
21: send \(x_{i}\) to all vertices in \(N(v_{i})\);
22:if\(\sum_{v_{j}\in N(v_{i})}x_{j}\geq 1\)then
23: the vertex \(v_{i}\) is colored 'black'
24:endif
25: send the color of vertex \(v_{i}\) to all vertices in \(N(v_{i})\);
26: update \(\tilde{\delta}(v_{i}):=|\{v_{j}\in N(v_{i})|\text{the vertex $v_{j}$ is white}\}|\)
27:endfor
28: (\(\star\)\(z_{i}\)\(\star\))
29: send \(\tilde{\delta}(v_{i})\) to all vertices in \(N(v_{i})\);
30: calculate \(\tau^{(1)}(v_{i}):=\max_{j\in N(v_{i})}\{\tilde{\delta}(v_{j})\}\);
31: send \(\tau^{(1)}(v_{i})\) to all vertices in \(N(v_{i})\);
32: update \(\tau^{(2)}(v_{i}):=\max_{j\in N(v_{i})}\{\tau^{(1)}(v_{j})\}\);
33:if\(\tilde{\delta}(v_{i})=\tau^{(2)}(v_{i})=0\)then
34:\(V^{\prime}=:V^{\prime}-\{v_{i}\}\)
35:endif
36:if\(V^{\prime}\
eq\emptyset\)then
37: continue to execute the algorithm
38:endif
39:endfor
```  
**Algorithm 1** Approximating \(LP_{MTDS}\)  
**Lemma 1**. : _When each outer loop iteration \(\hbar\) starts, for each vertex \(v_{i}\in V\), we can obtain_  
\[\tilde{\delta}(v_{i})\leq\Delta^{\frac{\hbar+1}{k}}.\]  
Proof of Lemma 1.: We prove it by using induction. Firstly, when \(\hbar=k-1\), the condition \(\Delta^{\frac{\hbar+1}{k}}=\Delta\). Due to \(\tilde{\delta}(v_{i})\) being the dynamic degree in \(N(v_{i})\) and \(\Delta\) being the maximum degree, it is clear that \(\tilde{\delta}(v_{i})\leq\Delta\). Secondly, in order to prove that the other iterations also hold, we use the algorithm in [37] to approximate \(LP_{MTDS}\) (the modified algorithm will be available in Appendix A), where all vertices know \(\Delta\) in their algorithm. Thus, similar to their algorithmic analysis, in the last step (\(m=0\)) of the preceding outer loop iteration \(\hbar+1\), the \(x_{i}\) of all vertices with \(\tilde{\delta}(v_{i})\geq\Delta^{\frac{h+1}{k}}\) is changed to \(1\). Hence, all vertices in \(N(v_{i})\) will be colored black, so \(\tilde{\delta}(v_{i})\) will be changed to \(0\). Thus, the dynamic degrees of all vertices with \(\tilde{\delta}(v_{i})\geq\Delta^{\frac{h+1}{k}}\) is changed to \(0\), and the dynamic degrees of the other vertices clearly satisfy this inequality \(\tilde{\delta}(v_{i})\leq\Delta^{\frac{h+1}{k}}\). Therefore, by using the algorithm in [37], we can verify that \(\tilde{\delta}(v_{i})\leq\Delta^{\frac{h+1}{k}}\) holds when each outer loop iteration \(\hbar\) starts. Hence, for our algorithm, we only need to show that the \(x_{i}\) of all vertices with \(\tilde{\delta}(v_{i})\geq\Delta^{\frac{h}{k}}\) is changed to \(1\) when each inner loop iteration ends (\(m=0\)). According to lines \(17\)-\(19\) of Algorithm 1, we can see that the \(x_{i}\) of all vertices with \(\tilde{\delta}(v_{i})\geq\tau^{(2)}(v_{i})^{\frac{h}{k+1}}\) are changed to \(1\) when \(m=0\).