# Approximating a Minimum Dominating Set by Purification
## 3 Stage 1: The Clustering
{ 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 \(T(C_{i})\in T\)do { in order } while\(T(C_{i})\setminus(F^{h}\cup D^{h})\
eq\emptyset\)do \(v:=\) any vertex with the minimum PB\((v,h)\) in set \(T(C_{i})\setminus F^{h}\); \(P^{h+1}:=P^{h}\cup\{v\}\); \(F^{h+1}:=F^{h}\cup\{\)all vertex in set \(T\setminus(F^{h}\cup P^{h+1})\) that have semi-private neighbor }; \(h:=h+1\); endwhile if\(F^{h}\) is dominating set then \(S^{*}:=F^{h}\);  break; endif endfor
```

**Algorithm 5** Procedure Purify 3 (P3)

Note that, for the example in Figure 2, \(|S|=3\) but \(\gamma(G)=2\); hence, set \(S\) can be purified. At iteration 0, Procedures P1-P3 set firm all vertices of forest \(T\) with private neighbors. The vertices \(v_{2}\) and \(v_{3}\) have as private neighbors vertices 4 and 8, respectively; so, \(F^{0}=\{v_{2},v_{3}\}\). Since \(F^{0}\) is a dominating set, \(S^{*}=F^{0}\), and the algorithm stops. **Procedure P4. ** (This procedure was basically suggested by one of the anonymous referees of [22], which is highly acknowledged by the authors of this paper). The _private neighborhood_\(pn(v,S)\) of vertex \(v\in S\subseteq V(G)\) is

\[pn(v,S)=\{u\in V:N(u)\cap S=\{v\}\}.\]

Let \(a\) and \(b\) be adjacent vertices from set \(T_{i}\), such that \(a\) is a leaf vertex added to set \(T_{i}\) after vertex \(b\). Procedure P4 processes vertex \(a\) first and then vertex \(b\), as follows (see Algorithm 6). ```
Input: A graph \(G(V,E)\) and dominating set \(S\). Output: \(S^{*}\). { minimal dominating set } \(S^{*}=\{v_{1},\ldots,v_{p}\}\); {vertices of \(S\) in the order they are added by [PERSON]} \(h:=p\); { iterative step } while\(h>0\)do if\(pn(v_{h},S^{*})=\emptyset\)then \(S^{*}:=S^{*}\setminus\{v_{h}\}\); {we purify vertex \(v_{h}\)} endif \(h:=h-1\); endwhile
```

**Algorithm 6** Procedure Purify 4 (P4)

We use the example of Figure 2 to demonstrate Procedure P4. Initially, \(S^{*}=S=\{v_{1},v_{2},v_{3}\}\). In iterations \(h=3\) and \(h=2\), \(pn(v_{3},S^{*})=1\) and \(pn(v_{2},S^{*})=1\), respectively, so these vertices cannot be purified. In iteration \(h=1\), \(pn(v_{1},S^{*})=0\), so this vertex is purified, \(S^{*}=\{v_{2},v_{3}\}\) and the procedure stops. Note that all four purification procedures find an optimal solution for our example. ## 5 Approximation Ratios

In this section, we derive approximation ratios for our algorithms. By [22], if \(|S|\leq 2\), then \(S\) is a minimum dominating set. Then, all the graphs \(G\) analyzed here will be such that \(\gamma(G)>2\). Note that \(G\) is a connected graph, and all \(x\in S^{*}\) has at least one semi-private neighbor (\(S^{*}\) be the output of purification procedures). Then, \(|S^{*}|\leq n/2\). In the next, we derive an approximation ratio of purification procedures. By [5], \(\gamma(G)\geq\frac{n}{\Delta+1}\). Then, \(\frac{n}{\Delta+1}\leq|S^{*}|\leq\frac{n}{2}\). Since \(|S^{*}|\geq\gamma(G)\), we obtain that an approximation ratio for purification is

\[\rho=\frac{|S^{*}|}{\gamma(G)}\leq\frac{\frac{n}{2}}{\frac{n}{\Delta+1}}= \frac{\Delta+1}{2}. \tag{4}\]

By [22], Algorithm Greedy achieves the approximation ratio \(\rho\leq ln(\Delta+1)+1\). Using these approximation ratios, we obtain an overall approximation ratio for purification procedures. \[\rho\leq\left\{ \begin{array}{ll}\frac{\Delta+1}{2},&\text{if }1\leq\Delta \leq 4\\ ln(\Delta+1)+1,&\text{otherwise.}\end{array} \right. \tag{5}\]

## 6 Experimental Results

In this section, we describe our computation experiments. We implemented our algorithms in C++ using Windows 10 operative system for 64 bits on a personal computer with Intel Core i7-9750H (2.6 GHz) and 16 GB of RAM DDR4. We generated different sets of problem instances using different pseudo-random methods for the generation of graphs. The order (the number of vertices) and the size (the number of edges) of each instance were determined randomly using the function \(random()\).