# Total Outer-Independent Domination Number: Bounds and Algorithms
## 3 Heuristic Algorithm  
Now, we present our heuristic for approximating a total outer-independent dominating set. This heuristic is divided into two stages: Stage 1 follows a greedy methodology to find a TOIDS, and Stage 2 consists of a purification procedure that delivers a minimal TOIDS. Stage 1 is further divided into two fundamental parts: the first part constructs a total dominating set, and the second part updates this set to ensure that its complement is independent. We need a few definitions to describe our heuristic. We denote by \(T_{h}\) the TOIDS formed by the heuristic in iteration \(h\). The dominated set in iteration \(h\) is denoted by \(I_{h}\); this vertex set is formed by the vertices that have at least one neighbor in \(T_{h}\). Please note that in the final iteration of Stage 1, the set \(I_{h}\) is an independent set. Finally, \(A_{h}\) denotes the vertex set that has no neighbors in \(T_{h}\) in iteration \(h\), i.e., \(N(A_{h})\cap T_{h}=\emptyset\). In general, our heuristic is a greedy algorithm that runs over several iterations. The iterative process in Stage 1 is guaranteed to converge, as in each iteration, a vertex is selected from \(I_{h}\) and added to \(T_{h}\), reducing the size of \(A_{h}\) or \(I_{h}\). Since these sets are subsets of \(V(G)\), the number of iterations is at most \(n\), ensuring termination in a finite number of steps. Below, we provide a detailed description of our heuristic. First, we select two vertices \(\{u,v\}\) where \(u\) is the vertex with the highest degree in \(V(G)\) and \(v\) is its neighbor with the highest number of neighbors not dominated by \(u\). Thus, initially \(T_{0}=\{u,v\}\), \(I_{0}=(N(u)\cup N(v))\setminus\{u,v\}\) and \(A_{0}=V\setminus(T_{0}\cup I_{0})\). Notice that these are disjoint sets and \(A_{0}\cup I_{0}\cup T_{0}=V\). The sets \(A_{h}\), \(I_{h}\) and \(T_{h}\) are disjoint and \(A_{h}\cup I_{h}\cup T_{h}=V\). If \(A_{0}=\emptyset\) then \(N[u]\cup N[v]=V(G)\) and \(T_{0}=\{u,v\}\) is a minimum total dominating set. Proof. : By Remark 2 and \(A_{0}=\emptyset\), it follows immediately that \(I_{0}=V\setminus T_{0}\). This implies that all vertices in \(V(G)\) have a neighbor in \(T_{0}\). Please note that by the construction of the algorithm, \((u,v)\in E(G)\). Since \(|T_{0}|=2\), then \(T_{0}\) is minimum, a TDS cannot contain fewer than two vertices. A direct consequence of the previous lemma is the following observation. If \(A_{0}=\emptyset\) and \(I_{0}\) is an independent set, then \(T_{0}=\{u,v\}\) is a minimum TOIDS. The initial sets are updated iteratively at each iteration \(h>0\), resulting in the current sets of vertices \(T_{h}\), \(I_{h}\), and \(A_{h}\), where \(T_{h}\) is the partial total outer-independent dominating set. Each iteration \(h>0\) begins if \(A_{h}\
eq\emptyset\) or \(I_{h}\) is not an independent set. In the first iterative part of _Stage 1_, for each iteration, we choose a vertex \(v\in I_{h-1}\) such that \(N_{A_{h-1}}[v]\) is as large as possible. Then, we add \(v\) to \(T_{h}\), i.e., \(T_{h}=T_{h-1}\cup\{v\}\). Please note that \(v\) is chosen to maximize the number of adjacent vertices among those that do not yet have neighbors in \(T_{h-1}\). At this point, the sets \(A_{h}\) and \(I_{h}\) are updated accordingly. In the second iterative part of _Stage 1_, each iteration runs if the set \(I_{h-1}\) is not yet an independent set. Thus, we choose a vertex \(u\in I_{h-1}\) such that \(N_{I_{h-1}}[u]\) is as large as possible, then we add \(u\) to \(T_{h}\), i.e., \(T_{h}=T_{h-1}\cup u\). Please note that \(u\) is the vertex that has the most neighbors in \(I_{h-1}\). At this point, the sets \(A_{h}\) and \(I_{h}\) are updated accordingly. At the end of Stage 1, we obtain a TOIDS of the graph \(G\) in \(T_{h}\). Up to this point, the algorithm may have included redundant vertices in \(T_{h}\). Therefore, in Stage 2, we proceed to apply a purification procedure that yields a minimal TOIDS of \(G\). The purification procedure is described in Section 3.