# Approximating a Minimum Dominating Set by Purification
## 1 Introduction  
In a simple connected graph \(G=(V,E)\) with \(|V|=n\) vertices and \(|E|=m\) edges, a subset of vertices \(S\subseteq V\) is a _dominating set_ in graph \(G\) if any vertex \(v\in V\) is adjacent to some vertex from this subset unless vertex \(v\) itself belongs to set \(S\). The general objective is to find an _optimal solution_, a dominating set with the minimum possible size \(\gamma(G)\). The domination problem is known to be _NP-hard_[1], being among the hardest problems in the family. It is closely related to other well-known graph optimization problems such as set cover, graph coloring and independent set. The problem of domination in graphs was formalized in [2; 3]. Currently, this topic has been detailed in the two well-known books by [4; 5]. The theory of domination in graphs is an area of increasing interest in discrete mathematics and combinatorial computing, in particular, because of a number of important real-life applications,for example, in facility location problems in street networks [6; 7; 5], in monitoring electric power systems with the aim of minimizing stage measurement units [8], in electric power networks [9], and in the analysis of food web robustness [10]. Different versions of the graph domination problem have been utilized to model clustering in wireless ad hoc networks [11; 12; 13; 14]. A number of other important graph-theoretic problems including set cover, maximum independent set and chromatic number are reducible to the dominance problem [5]. Dominating sets also find applications in the study of social networks [15; 16; 17]. Due to the complexity of the problem, major efforts have been made towards the development of heuristic algorithms. Among the earliest related works, we can mention that of [PERSON] [18], who described an approximation algorithm with an approximationratio \(\ln\left(\frac{n}{\gamma}\right)+1+\frac{1}{\gamma}\) for the related weighted set cover problem; here and later, \(\gamma\) is the optimal objective value. Iteratively, the algorithm selects a vertex \(v\) minimizing \(\frac{w_{v}}{f(\mathbb{C}\cup\{v\})-f(\mathbb{C})}\), where \(w_{v}\) is the weight of vertex \(v\), and \(f(\mathbb{C})=|\cup_{v\in\mathbb{C}}N[v]|\) until \(f(\mathbb{C})=|S|\). Adopting this algorithm, [PERSON] [19] solved the domination problem showing that the cardinality of the dominating set created by his algorithm is upper-bounded by \(n+1-\sqrt{2m+1}\). Later, [PERSON] et al. [20] and [PERSON] et al. [21] presented heuristic algorithms designed for special types of graphs estimating the performance of their algorithms solely with an experimental study. Recently, [22] described a heuristic algorithm with a better performance. Little work has been carried out in the development of exact algorithms. To the best of our knowledge, the only exact algorithms which do better than a complete enumeration are described in [23; 24; 25]. In [23; 24], the authors show that their algorithms run in times \(O(1.4969^{n})\) and \(O(1.4689^{n})\), respectively, without presenting experimental evidence of the practical performance of their algorithms. Although these bounds are notably better than \(2^{n}\), they remain too impractical. Quite recently, in [25], two exact algorithms, an implicit enumeration algorithm and an alternative integer linear programming (ILP) formulation were proposed. The authors also described an approximation algorithm. On the one hand, it gave solutions of notably better quality than the previously known approximation algorithms for the benchmark instances with up to 2100 vertices, some of them being solved in less than 1 min. The algorithm found an optimal solution for 61.54% of these instances. On the other hand, it failed to create solutions within a reasonable time limit for the graphs with 3000 and more vertices. In contrast, for large-scale practical problems, the heuristic from [22] gave solutions within the time limit of 50 s for graphs with up to 14,000 vertices.