# Approximating a Minimum Dominating Set by Purification
## 3 Stage 1: The Clustering
While creating a new edge, the



Table 2 below presents the percentage of the improvement accomplished by purification procedures P1-P4, on average, for all the tested benchmark instances. On average over all the 1316 tested instances, a best solution among the four solutions generated by purification procedures P1-P4 is 9.68% smaller than the dominant set returned by P0. Purification procedures P1-P4 turn out to be more efficient for dense instances with about 40% of the improvement, though in absolute terms, the number of purified vertices for non-dense instances is higher. Table 3 presents results for 45 sample benchmark instances from [26] for which the optima solutions are known. This table compares the quality of the solutions obtained by purification procedures P1-P4 vs. the corresponding optimal solutions and upper bounds. The complete comparative analysis for all the 500 benchmark instances with known optimal solutions can be found in [26] and is also reflected in Figure 3. Over all the tested instances, our solutions, on average, contained 1/7 th part of the number of vertices established due to the best known upper bound \(U\), an improvement of 85.71% (see Fact 1 at the end of this section). Remarkably, among the 500 instances with the known optimum, an optimal solution is generated for 46.33% of the instances, whereas the average error over all the created non-optimal solutions is 1.01 vertices. \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline  & & & \multicolumn{6}{c}{**Purification Procedures**} \\ \cline{4-13} \(|V|\) & \(|E|\) & \multicolumn{2}{c}{**P0**} & \multicolumn{2}{c}{**P1**} & \multicolumn{2}{c}{**P2**} & \multicolumn{2}{c}{**P3**} & \multicolumn{2}{c}{**P4**} \\ \cline{3-13}  & & \(|\mathbf{S}|\) & \(|\mathbf{S^{*}}|\) & \(|\mathbf{S^{*}}|\) & \% & \(|\mathbf{S^{*}}|\) & \% & \(|\mathbf{S^{*}}|\) & \% & \(|\mathbf{S^{*}}|\) & \% \\ \hline
7350 & 7474 & 3177 & 2944 & 2744 & 6.79 & 2717 & 7.71 & 2722 & 7.54 & 2717 & 7.71 \\
7450 & 7497 & 3217 & 2980 & 2771 & 7.01 & 2772 & 6.98 & 2757 & 7.48 & 2751 & 7.68 \\
7550 & 7557 & 3299 & 3093 & 2844 & 8.05 & 2827 & 8.60 & 2835 & 8.34 & 2821 & 8.79 \\
7650 & 7696 & 3331 & 3095 & 2875 & 7.11 & 2849 & 7.95 & 2853 & 7.82 & 2846 & 8.05 \\
7700 & 7716 & 3322 & 3096 & 2875 & 7.14 & 2861 & 7.59 & 2862 & 7.56 & 2855 & 7.78 \\
7800 & 7804 & 3395 & 3176 & 2947 & 7.21 & 2933 & 7.65 & 2938 & 7.49 & 2924 & 7.93 \\
7950 & 7982 & 3480 & 3260 & 3022 & 7.30 & 3000 & 7.98 & 3004 & 7.85 & 3000 & 7.98 \\
8000 & 8126 & 3466 & 3215 & 2987 & 7.09 & 2985 & 7.15 & 2969 & 7.65 & 2957 & 8.02 \\
9900 & 24,411,032 & 16 & 14 & 13 & 7.14 & 13 & 7.14 & 13 & 7.14 & 13 & 7.14 \\
15,000 & 56,111,357 & 14 & 12 & 12 & 0 & 12 & 0 & 12 & 0 & 12 & 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: _Cont._ \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**\% P1** & **\% P2** & **\% P3** & **\% P4** \\ \hline
9.17 & 9.48 & 8.88 & 9.63 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Average results over all instances. As to the execution times, for the largest benchmark instances with 15,000 vertices, all four procedures finished in less than two seconds. Figure 4 represents the execution times for all the tested instances. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{\(|V|\)} & \multirow{2}{*}{\(|E|\)} & \multirow{2}{*}{\(\gamma(G)\)} & **P1** & **P2** & **P3** & **P4** \\ \cline{3-6}  & & & \(|S_{1}^{*}|\) & \(|S_{2}^{*}|\) & \(|S_{3}^{*}|\) & \(|S_{4}^{*}|\) \\ \hline



\hline \hline \end{tabular}
\end{table} 
Table 3: _Cont._

Figure 3: Results of purification procedures (\(\min\{S_{i}^{*}\}\)), \(\gamma(G)\), and \(U\). The upper bound \(U\) is due to the following known results. **Fact 1** ([4]). : _If \(G(V,E)\) is a connected graph of order \(n\), minimum degree \(\delta(G)\) and maximum degree \(\Delta(G)\), then \(\gamma(G)\leq\frac{n}{2}\), \(\gamma(G)\leq n-\Delta(G)\), and \(\gamma(G)\leq\frac{n(\ln(\delta(G)+1))}{\delta(G)+1}\).