# Approximating a Minimum Dominating Set by Purification
## 3 Stage 1: The Clustering
The _outer cover set_ of vertex \(v\in T^{h-1}\) at iteration \(h\), \(OCS(v,h)\), is the set of neighbors of \(v\) from \(V\setminus S\), which are not adjacent with any firm vertex from set \(F^{h-1}\); i.e.,  
\[OCS(v,h)=N_{\overline{T^{h-1}}}(v)\setminus N_{\overline{S}}(F^{h-1}). \tag{1}\]  
The _inner cover set_ of vertex \(v\in T^{h-1}\) at iteration \(h\), \(ICS(v,h)\), is the set of yet non-firm neighbors of vertex \(v\) in \(T^{h-1}\), i.e.,  
\[ICS(v,h)=N_{\gamma^{h-1}}(v)\setminus F^{h-1}. \tag{2}\]Roughly, vertices with high \(|OCS(v,h)|\) and \(|ICS(v,h)|\) tend to be non-purified; vice versa, direct descendants of such a vertex with low outer and inner cover indices tend to be purified. An overall purification balance of vertex \(v\) is  
\[PB(v,h)=\alpha|OCS(v,h)|+\beta|ICS(v,h)|, \tag{3}\]  
where \(0\leq\alpha,\beta\leq 1\). The distinguished features of our procedures are defined below. **Procedure P1. ** At iteration \(h>0\), every cluster \(C\in T\) is traversed in a bottom-up fashion. For every non-leaf vertex \(x\) at a given level of cluster \(C\), if \(x\) is firm, its children without semi-private neighbors are purified. If \(x\) is not firm and has no firm children, it is set firm, and its children with no semi-private neighbors are purified, whereas the children with semi-private neighbors are set firm. If \(x\) has a firm child, the parent of \(x\) is set firm (unless it is already firm), and \(x\) is purified (see Algorithm 3):  
```
Input: Forest \(T=\{C_{1},C_{2},\ldots,C_{k}\}\). Output: \(S^{*}\). { minimal dominating set } {set vertices with private neighbors} \(F^{0}:=\) {set of vertices from \(T\) with private neighbors}; if\(F^{0}\) is dominating set then \(S^{*}:=F^{0}\); else for any \(C_{i}\in T\)do { in order } \(C_{i}^{0}:=C_{i}\); \(h:=0\); {Travel \(C_{i}\) by levels in ascending order} for any \(x\
ot\in\) leaf set in level \(j\) of \(C_{i}\)do if\(x\in F^{h}\)then \(C_{i}^{h+1}:=C_{i}^{h}\setminus\{\) children not a firm of \(x\) do not have semi-private neighbors}; else if\(x\) has non firm children then \(F^{h+1}:=F^{h}\cup\{x\}\); \(C_{i}^{h+1}:=C_{i}^{h}\setminus\{\) children of \(x\) do not have semi-private neighbors}; else if parent of \(x\) is not in \(F^{h}\)then \(F^{h+1}:=F^{h}\cup\{\) parent of \(x\}\); \(C_{i}^{h}:=C_{i}^{h}\setminus\{x\}\); else \(C_{i}^{h+1}:=C_{i}^{h}\setminus\{x\}\); endif endif endif \(h:=h+1\); endfor endfor \(S^{*}:=F^{h}\); endif
```  
**Algorithm 3** Procedure Purify 1 (P1)  
**Procedure P2. ** At any iteration \(h>1\), a non-firm vertex \(x\) with the maximum \(PB(x,h)\) is set firm (for each non-firm vertex \(v\), the sets \(OCS(v,h)\) and \(ICS(v,h)\) being updated, respectively). The procedure halts at iteration \(h\) if \(U^{h}=\emptyset\) and outputs dominant set \(F^{h}\) (see Algorithm 4):```
Input: Forest \(T=\{C_{1},C_{2},\ldots,C_{k}\}\). Output: \(S^{*}\). { minimal dominating set } \(F^{0}:=\{\)set of vertices from \(T\) with private neighbors}; \(P^{0}:=\emptyset\); if\(F^{0}\) is dominating set then \(S^{*}:=F^{0}\); else \(h:=0\); for any \(C_{i}\in T\)do { in order } while\(V(C_{i})\setminus(F^{h}\cup D^{h})\
eq\emptyset\)do \(v:=\) any vertex with the maximum PB\((v,h)\) in set \(V(C_{i})\setminus F^{h}\); \(F^{h+1}:=F^{h}\cup\{v\}\); \(P^{h+1}:=P^{h}\cup(N_{V(C_{i})}(v)\setminus F^{h})\); \(h:=h+1\); endwhile if\(F^{h}\) is dominating set then \(S^{*}:=F^{h}\);  break; endif endif
```

**Algorithm 4** Procedure Purify 2 (P2)

**Procedure P3. ** At any iteration \(h>1\), a vertex \(x\) with the minimum \(PB(x,h)\) is purified, and the vertices from \(T^{h-1}\) with semi-private neighbors from \(\overline{T}^{h-1}\) are set firm (for each non-firm vertex \(v\), the sets OCS\((v,h)\) and ICS\((v,h)\) being updated, respectively). The procedure halts at iteration \(h\) if \(U^{h}=\emptyset\) and outputs dominant set \(F^{h}\) (see Algorithm 5):

```
Input: Forest \(T=\{T(C_{1}),T(C_{2}),\ldots,T(C_{k})\}\). Output: \(S^{*}\).