# Total Outer-Independent Domination Number: Bounds and Algorithms
## 3 Heuristic Algorithm
The pseudo-code for the heuristic is shown as follows (see Algorithm 1). ```
Input: A graph \(G(V,E)\). Output: A minimal total outer-independent dominating set \(T^{*}\). \(h:=0\); \(u:=\) is the vertex with the maximum degree in \(V(G)\); \(v:=\) is a vertex in \(N(u)\) such that \(|N(v)\setminus N(u)|\) be maximum; \(T_{0}:=\{u,v\}\); \(I_{0}:=(N(u)\cup N(v))\setminus\{u,v\}\); \(A_{0}:=V\setminus(T_{0}\cup I_{0})\); {first iterative part of Stage 1} while\(A_{h}+\emptyset\)do \(h:=h+1\); \(v_{h}:=\) a vertex \(v\in I_{h-1}\) such that \(N_{A_{h-1}}[v]\) be maximum; \(T_{h}:=T_{h-1}\cup\{v_{h}\}\); \(I_{h}=N(T_{h})\setminus T_{h}\); \(A_{h}:=V(G)\setminus(T_{h}\cup I_{h})\); endwhile {second iterative part of Stage 1} while\(I_{h}\) is not an independent set do \(h:=h+1\); \(u_{h}:=\) a vertex \(u\in I_{h-1}\) such that \(N_{I_{h-1}}[u]\) be maximum; \(T_{h}:=T_{h-1}\cup\{u_{h}\}\); \(I_{h}=Ih-1\setminus\{u_{h}\}\); endwhile {Stage 2} \(T^{*}:=\)\(\mathit{Purify}(G,T_{h})\);
```  
**Algorithm 1** Heuristic TOID  
Theorem 4.1: _Stage 1 of the Heuristic TOID runs in at most \(n-3\) iterations, taking \(O(n^{3})\) time._  
Proof. : The total number of iterations in the loops of Stage 1 is bounded by \(|A_{0}|+|I_{0}|\leq n-2\). Please note that the bound is reached for the graph \(K_{n}\) and \(\alpha(K_{n})=1\). Then, Stage 1 performs \(n-3\) iterations. In iteration \(h=0\), for each vertex \(u\in V(G)\), the neighborhood \(N(u)\) is determined by summing all the entries equal to \(1\) in the row associated with vertex \(u\). The selection of the maximum takes \(O(n^{2})\) time. Similarly, for each vertex \(v\in N(u)\), the value \(|N(v)\setminus N(u)|\) is computed by summing all the entries equal to \(1\) in the row corresponding to vertex \(v\), provided that the entries for vertex \(u\) are not both \(1\). In each iteration, \(h\geq 1\), \(N_{A_{h-1}}(v)+1\) is calculated for every vertex \(v\in I_{h-1}\) by counting all the \(1\) entries in the row corresponding to that vertex, if the entries are simultaneously \(1\) in \(N_{A_{h-1}}\). Similarly, \(N_{I_{h-1}}(u)+1\) is calculated for every vertex \(u\in I_{h-1}\). Given that each row consists of \(n\) entries and there are fewer than \(n\) rows to check, the computation of \(N_{A_{h-1}}(v)+1\) or \(N_{I_{h-1}}(u)+1\), along with the selection of the maximum, requires \(O(n^{2})\) time. Following the same idea, we can determine if the set \(I_{h}\) is independent if, for every vertex \(u\in I_{h}\), it holds that \(N_{I_{h}}(u)=\emptyset\). Please note that \(|A_{0}|<n\) and \(|I_{0}|<n\). Therefore, the total number of iterations in the loops of Stage 1 is bounded by \(n\). Hence, Stage 1 finds a total outer-independent dominating set in \(O(n^{3})\) time. **Proposition 5**. : _Let \(G\) be a connected split graph with maximum clique \(K\) and independent set \(I\). Then, the Heuristic TOID finds an optimal solution for the graph \(G\) if, in iteration \(i\) of the second iterative part of Stage 1, there is no vertex \(v\in I\) such that \(N_{I_{h+i-1}}(v)=K\setminus T_{h+i-1}\)._  
Proof. : Clearly, every vertex in \(K\) has a higher degree than the vertices in \(V\setminus K\). Then, in iteration \(h=0\), Heuristic TOID will select the vertices \(u,v\in K\) such that \(N(u)\cup N(v)\) is maximized, forming the set \(T_{0}=\{u,v\}\). Since \(T_{0}\) dominates all the vertices in \(K\), and \(V\setminus K\) is an independent set, in every iteration \(h\geq 1\) of the first iterative part of Stage 1, \(v_{h}\) is a vertex in \(K\setminus T_{h-1}\) with the largest number of undominated neighbors in \(V\setminus K\), and \(T_{h}\) is updated as \(T_{h}=T_{h-1}\cup v_{h}\). The first iterative part stops when all the vertices in \(V\setminus K\) are dominated. If \(T_{h}=K\), then \(V\setminus K\) is an independent set, and the second iterative part of Stage 1 is skipped, proceeding directly to Stage 2.