## 4 Definitions and Basic Properties  
Before we proceed to estimate the approximation ratio for the dominating set returned by the algorithm, we need to introduce additional definitions. First, we will introduce a mapping between vertices selected by the algorithm and vertices of the optimal dominating set. This mapping will allow us to relate the vertices chosen by the algorithm, which will enable us to effectively bound the number of selected vertices and prove a more accurate approximation ratio. Definition 8: Let \(\Gamma\) be the set of vertices selected by the algorithm, consisting of two subsets:  
\[\Gamma_{1}:=\bigcup_{v\in V}\{\beta_{1}(v)\}\]  
\[\Gamma_{2}:=\bigcup_{v\in V}\{\beta_{2}(v)\}\]  
Note that \(\Gamma_{2}\) may contain vertices that are not added to the set \(D_{2}\), as some vertices \(\beta_{2}(v)\) might be replaced by \(\gamma(v)\) during the second phase of the algorithm. Furthermore, we define the following:  
* \(\mathbf{\Psi}_{2}^{\prime}\)--the set of vertices \(\beta_{2}(v)\) selected in the second phase of the algorithm and not added to \(D_{2}\). * \(\mathbf{\Psi}_{2}\)--the set of vertices \(\gamma(v)\) selected in the second phase of the algorithm and added to \(D_{2}\). Additionally, we divide the sets \(\Gamma_{1}\) and \(\Gamma_{2}\) into internal and external vertices:  
\[\Gamma_{1}^{IN}:=\{v\in\Gamma_{1}:\exists_{B\in\mathcal{B}}:v\in B^{IN}\}\]  
\[\Gamma_{1}^{OUT}:=\{v\in\Gamma_{1}:\exists_{B\in\mathcal{B}}:v\in B^{IN}\}\]  
\[\Gamma_{2}^{IN}:=\{v\in\Gamma_{2}:\exists_{B\in\mathcal{B}}:v\in B^{IN}\}\]  
\[\Gamma_{2}^{OUT}:=\{v\in\Gamma_{2}:\exists_{B\in\mathcal{B}}:v\in B^{IN}\}\]  
Finally, \(\Gamma=\Gamma_{1}\cup\Gamma_{2}\)--the set of all vertices \(\beta(v)\) selected by the algorithm (not necessarily added to \(D_{2}\)). Now we are ready to define the alpha function that will help us estimate the number of vertices added to the dominating set \(D\). This function will map the vertices selected by our algorithm to the vertices in the optimal dominating set, allowing us to establish a relationship between our solution and the optimal one. Definition 9: Let \(\alpha:\Gamma\to M\) be a function that assigns to vertices from \(\Gamma\) (selected as \(\beta(v)\) in phases 1 and 2 of the algorithm) a vertex \(m\in M\). The function \(\alpha\) is defined by the following cases:  
**Case 1:** When a vertex \(m\in M\) adds to the set \(D\) a vertex, as follows:  
* \(\beta_{1}(m)\), where \(\beta_{1}(m)\in(V\setminus M)\cup\{m\}\) then \(\alpha(\beta_{1}(m)):=m\). * \(\beta_{2}(m)\), where \(\beta_{2}(m)\in(V\setminus M)\cup\{m\}\) then \(\alpha(\beta_{2}(m)):=m\). _(c)_ \(\gamma(m)\)_, where_ \(\gamma(m)\in(V\setminus M)\cup\{m\}\) _then_ \(\alpha(\gamma(m)):=m\)_._  
_Case 2: When a vertex_ \(v\in V\setminus M\)_, such that_ \(m(v)=m\) _(from the definition of bunches), adds to the set_ \(D\) _a vertex, as follows:_  
_(a)_ \(\beta_{1}(v)\)_, where_ \(\beta_{1}(v)\in(V\setminus M)\cup\{m\}\) _then_ \(\alpha(\beta_{1}(v))=m\)_._  
_(b)_ \(\beta_{2}(v)\)_, where_ \(\beta_{2}(v)\in(V\setminus M)\cup\{m\}\) _then_ \(\alpha(\beta_{2}(v))=m\)_._  
_(c)_ \(\gamma(v)\)_, where_ \(\gamma(v)\in(V\setminus M)\cup\{m\}\) _then_ \(\alpha(\gamma(v))=m\)_._  
_For all other cases,_ \(\alpha(v)=\emptyset\)_._  
In summary, the function \(\alpha\) works as follows: if a vertex \(v\in M\) adds a vertex \(u\) to the set \(D\) then \(\alpha(u):=v\). Similarly, when a vertex \(v\in V\setminus M\) adds a vertex \(u\) to the set \(D\) then \(\alpha(u):=m(v)\), where \(m(v)\) is the vertex from \(M\) associated with \(v\) in the bunch definition. The function \(\alpha\) plays a crucial role in the analysis of the algorithm by mapping the vertices selected by the algorithm to the vertices of the optimal dominating set \(M\). This allows us to track which vertices from \(M\) are \"responsible\" for the vertices chosen by the algorithm.