# Approximating a Minimum Dominating Set by Purification
## 3 Stage 1: The Clustering  
As briefly noted, the cluster \(C_{i}\) is a rooted tree, a sub-graph of graph \(G\) associated with some connected component of the graph induced by set \(S\). Initially, a set of clusters, \(C_{1},\ldots,C_{l}\), form a partition of set \(S\). We denote the union of these trees by \(T\). In a cluster, the vertices of each connected component can be represented in different ways as trees. During the traversal of these trees, special conditions are verified, and some vertices are omitted (purified). We generate the clusters during the construction of the initial dominating set \(S\). This construction is based on the greedy procedure from [22], further referred to as _Greedy_. It works in a number of iterations, which is upper-bounded by \(n\). At each iteration \(h\geq 1\), one specially selected vertex, denoted by \(v_{h}\), is added to the dominant set \(S_{h-1}\) of the previous iteration, i.e., \(S_{h}:=S_{h-1}\cup\{v_{h}\}\), where initially \(S_{0}=\emptyset\). \(S_{h-1}\) is the partial dominant set of iteration \(h-1\). At each iteration \(h\), the _active degree_ of a vertex \(v\in\overline{S_{h-1}}\) is \(|N(v)\setminus[S_{h-1}\cup N(S_{h-1})]|\). At each iteration \(h\), vertex \(v_{h}\) is a vertex of \(\overline{S_{h-1}}\) with the maximum active degree. Note that \(v_{1}\) is a vertex with the maximum degree in graph \(G\). A vertex is said to be covered at iteration \(h\) if it has at least one neighbor in the set \(S_{h-1}\). Greedy halts when \(S_{h}\) is a dominating set of \(G\). At that iteration, all uncovered vertices with active degree 0 (if any) are included in the set \(S_{h}\). A formal description is provided in Algorithm 1. Throughout this section, \(v_{h}\) is used for the vertex with the maximum active degree selected by _Greedy_ at iteration \(h\); hence, \(S=\{v_{1},\ldots,v_{k}\}\) is the dominant set of Stage 1. ```
Input: A graph \(G\). Output: A dominating set \(S\) of \(G\). \(h:=1\); \(i:=1\); \(S_{0}:=\emptyset\); \(T^{0}:=\emptyset\); { iterative step } while\(S_{h}\) is not a dominating set of graph \(G\)do \(h:=h+1\); \(v_{h}:=\) any vertex of \(\overline{S_{h-1}}\) with maximum active degree; \(S_{h}:=S_{h-1}\cup\{v_{h}\}\); \([T^{h},j]:=\)Cluster_Generation(\(v_{h}\), \(T^{h-1}\), \(h\), \(i\)); endwhile
```  
**Algorithm 1** Algorithm Greedy  
Our aim is to _purify_ this set, i.e., omit some vertices from that set so that the reduced set remains dominant. A combination of a particular clustering and traversal method results in a particular purification procedure. The four purification procedures that we propose here apply the same rules for the creation of the clusters. Unlike the purification procedure P0, which is oriented on the creation of clusters in depth, here, Stage 1 creates clusters in width. Iteratively, every next vertex \(v_{h}\) is included in the partial forest \(T^{h-1}\) at iteration \(h\), \(h=1,\ldots,k\), as follows:  
* Initially, we let \(T^{0}:=\emptyset\) and \(T^{1}:=C_{1}:=v_{1}\)
* For \(h>1\),
* If \(N_{V(T^{h-1})}(v_{h})=\emptyset\), then we create a new cluster \(C_{i}:=v_{h}\) and {update \(T^{h}\)} \(T^{h}:=T^{h-1}\cup C_{i}\)
* If \(N_{V(T^{h-1})}(v_{h})=\{x\}\), \(x\in T\) (i.e., \(|N_{V(T^{h-1})}(v_{h})|=1\)), then \(T^{h}\) is \(T^{h-1}\) complemented by vertex \(v_{h}\), a new child of vertex \(x\)
* If \(|N_{V(T^{h-1})}(v_{h})|>1\), we create a new cluster \(C_{i}\) with root \(v_{h}\) and with the immediate successors from \(N_{V(T^{h-1})}(v_{h})\). In this case, cluster \(C_{i}\) includes one or more clusters from \(T^{h-1}\) (these clusters disappear as individual clusters in forest \(T^{h}\)). This kind of a union may yield a cycle (see Figure 1). To avoid this, we eliminate a required number of edges from \(T^{h-1}\) incident with vertices in \(N_{V(T^{h-1})}(v_{h})\). Below, we give a formal description of the procedure (see Algorithm 2). Figure 1: Forests \(T^{h-1}\) and \(T^{h}\) (the red edge in \(T^{h-1}\) is omitted in \(T^{h}\) and yellow edges are added in \(T^{h}\). minimal one.