# Approximating a Minimum Dominating Set by Purification
## 3 Stage 1: The Clustering
Note that there is a difference between a minimal and a minimum dominating set. The latter one is optimal, whereas the former set is not necessarily optimal; however, it cannot be reduced by omitting any node from it. As we will see, our purification procedures return a minimal dominating set. In stage 2, Procedure P0 takes forest \(T\) as input, which, together with the initial dominating set \(S=\{v_{1},\ldots,v_{k}\}\), is constructed at stage 1. During the construction of set \(S\), the vertex \(v_{h}\) is inserted into the current forest \(T^{h-1}\) as a child of one of the previously inserted vertices \(v\in T^{h-1}\), such that \((v,v_{h})\in E(G)\), where \(v\in C\) (\(C\in T^{h-1}\)) is the vertex which is furthest away from the root in its cluster. If the root of another cluster in \(T^{h-1}\) is adjacent to vertex \(v_{h}\) in graph \(G\), it becomes a child of vertex \(v_{h}\). Note that the clusters with so-defined roots will be merged with the former cluster \(C\) into a new larger cluster. We may observe that, in Procedure P0, the clusters are generated in depth (resulting in clusters with high depth). Dealing with clusters with high depth has some advantages but also disadvantages. In Procedure P0, each cluster is traversed in a bottom-up fashion from a leaf to the root. We will refer to a sequence of four or three consecutive vertices on a path in the currently purified tree \(T^{h-1}(C_{i})\) as a _quadruple_ or _trio_, respectively. In Procedure P0, a quadruple \((a,b,c,d)\) or a trio \((a,b,c)\), forming sub-parts of the path, are identified. Given a quadruple \((a,b,c,d)\), the vertices \((b,c)\) are purified, unless these vertices possesses a _semi-private neighbor_, a vertex from set \(V(G)\setminus T^{h}\), which is the only (remained) neighbor of the former vertex from set \(T^{h}\). For a trio, a similar condition is verified only for vertex \(b\). As described above, two vertices can be purified at once. However, this might not be possible, either because there may exist no quadruple (the up going paths might be too short) or/and because a candidate vertex may possess a semi-private neighbor. It might be beneficial to set firm all vertices with a semi-private neighbor first (a firm vertex remains unpurified in the resultant dominant set). It may also be beneficial to leave a vertex possessing a considerable number of immediate descendants without semi-private neighbors unpurified in case all its immediate descendants are purified. Likewise, it might be good to leave a vertex unpurified if the number of its neighbors in \(\overline{S}\) as \"large enough\". The above and similar considerations are taken into account in four new purification procedures. The first three procedures P1-P3 set firm all vertices of forest \(T\) with private neighbors at iteration 0. If the so-formed set is dominating, all stop. Otherwise, three different disjoint subsets of set \(S\) forming a partition of \(S\) are distinguished, as defined below. 1. The set of firm vertices \(F^{h}\) (as noted above, \(F^{0}\) is the set of vertices from \(T\) with private neighbors; at iteration \(h>0\), \(F^{h}\) is the set of vertices from \(T\) with _semi-private_ neighbors). 2. The set of the pending vertices \(P^{h}\) formed by yet non-firm vertices which are neighbors of a firm vertex. 3. Set \(U^{h}\) consisting of the remaining yet unconsidered vertices. Iteratively, once \(F^{h}\) is determined, sets \(P^{h}\) and \(U^{h}\) are formed. The two purification parameters for each cluster vertex are defined below.