# Approximating a Minimum Dominating Set by Purification
## 3 Stage 1: The Clustering
Hence,_

\[U=\min\left\{\frac{n}{2},n-\Delta(G),\frac{n(\ln(\delta(G)+1))}{\delta(G)+1}\right\} \tag{7}\]

_is a valid upper bound on \(\gamma(G)\)._

## 7 Conclusions

We studied the purification process for the domination set problem in graphs and proposed four purification procedures that enhance solutions by 9.68% compared to the earlier state-of-the-art algorithm. Remarkably, among the 500 instances with a known optimum, optimal solutions were achieved for 46.33%, with an average error of 1.01 vertices for the remaining instances. We also derived approximation ratios for our purification procedures. Although our purification procedures create minimal dominating sets, they are not necessarily optimal. As we can observe from our experimental study, there are problem instances, for which only one of the proposed purification procedures delivers the best obtained solution, whereas for some other instances, the best solution is delivered by another heuristic (see Tables 1 and 2). It is a challenging question to develop a single best possible purification procedure, one that, for any (non-minimal) dominating set, always omits the maximum possible number of (redundant) vertices. Another direction for future related work is to extend our procedures to more general domination and other related graph optimization problems. Investigation, E.P.I., J.M.S.A. and N.V.; writing--review and editing, E.P.I. and N.V.; Resources, UAEMor administrated by J.A.H.-A. All authors have read and agreed to the published version of the manuscript. This research was partial supported by funding from CCyTEM. **Data Availability Statement:** [[https://data.mendeley.com/datasets/rr5](https://data.mendeley.com/datasets/rr5) bkj6 dw5/5]([https://data.mendeley.com/datasets/rr5](https://data.mendeley.com/datasets/rr5) bkj6 dw5/5) (accessed on 3 April 2024). **Conflicts of Interest:** The authors declare no conflicts of interest. ## References

* (1) [PERSON]; [PERSON] _Computers and Intractability_; Freeman: San Francisco, CA, USA, 1979; Volume 174. * (2) [PERSON] _The Theory of Graphs and Its Applications_; Methuen & Co, Ltd.: London, UK, 1962. * (3) [PERSON] _Theory of Graphs_; AMS Colloquium Publications: Providence, RI, USA, 1962; Volume 38. * (4) [PERSON]; [PERSON]; [PERSON] _Domination in Graphs_; Advanced Topics; [PERSON] Publications: New York, NY, USA, 1998. * (5) [PERSON] _Domination in Graphs_; Advanced Topics; Routledge: London, UK, 2017; Volume 2. Figure 4: Execution time of purification procedures. (a) Maximum execution times among P1–P4 for all instances. (b) Execution times for individual procedures. * [PERSON] and [PERSON] (2021) [PERSON]; [PERSON] Heuristics for k-domination models of facility location problems in street networks. _Comput. Oper. Res._**2021**, _133_, 105368. [CrossRef]
* [PERSON] et al. (1994) [PERSON]; [PERSON]; [PERSON] The k-neighbor, r-domination problems on interval graphs. _Eur. J. Oper. Res._**1994**, _79_, 352-368. [CrossRef]
* [PERSON] and [PERSON] (2005) [PERSON]; [PERSON] Power domination problem in graphs. In Proceedings of the International Computing and Combinatorics Conference, Kunming, China, 16-19 August 2005; Springer: Berlin/Heidelberg, Germany, 2005; pp. 818-828. [CrossRef]
* [PERSON] et al. (2002) [PERSON]; [PERSON]; [PERSON]; [PERSON] Domination in graphs applied to electric power networks. _SIAM J. Discret. Math._**2002**, _15_, 519-529. [CrossRef]
* [PERSON] et al. (2021) [PERSON] [PERSON]; [PERSON]; [PERSON]; [PERSON] Robustness Analysis of Trophic Networks using Outer k-independent Total Dominant Sets. In _Modelacion Matematica IV Biomatematicas, Epidemologia, Ingenieria_; Universidad Tecnologica de la Mixteca: Huajuapan de Leon, Mexico, 2021; Volume 4, pp. 3-18. * [PERSON] and [PERSON] (2006) [PERSON]; [PERSON] [PERSON] Graph domination, coloring and cliques in telecommunications. In _Handbook of Optimization in Telecommunications_; Springer: Berlin/Heidelberg, Germany, 2006; pp. 865-890.