# Total Outer-Independent Domination Number: Bounds and Algorithms
## 3 Heuristic Algorithm
If there exists a vertex \(v\in K\) such that \(N_{V\setminus K}(v)=\emptyset\), the procedure \(Purity(G,T_{h})\) removes this vertex from the set \(T_{h}\) and returns a set \(T^{*}\) with \(|K|-1\) vertices. Otherwise, the cardinality of \(T_{h}\) cannot be reduced, and \(T^{*}=T_{h}\). In either case, by the proof of Proposition 2, this is an optimal solution. If \(|T_{h}|<|K|\), then \(I_{h}=V\setminus T_{h}\) is not an independent set and has \(r=|K|-|T_{h}|\) vertices from \(K\) in \(I_{h}\). Please note that these \(r\) vertices form a \(K_{r}\) graph. Therefore, in the second iterative part of Stage 1, since in every iteration \(i<r\), there is no vertex \(v\in I\) such that \(N_{I_{h+i-1}}(v)=K\setminus T_{h+i-1}\), \(r-1\) vertices from the set \(K\setminus T_{h}\) are removed from \(I_{h}\) and added to \(T_{h}\) to ensure that \(I_{h}\) becomes an independent set. Then, \(|T_{h+r-1}|=|K|-1\). The current set \(T_{h+r-1}\) does not allow purification by the proof of Proposition 2, and \(T^{*}=T_{h+r-1}\) is an optimal solution. _Purify Procedure_  
In Theorem 2.3 of [13], [PERSON] et al. demonstrate that:  
**Lemma 2**. : _Let \(T\) be a TOIDS. \(T\) is a minimal set if and only if, for each vertex \(x\in T\), one of the following conditions holds:_  
1. _There exists a vertex_ \(y\in V(G)\) _such that_ \(N(y)\cap T=\{x\}\)_._
2. _There exists a vertex_ \(w\in V\setminus T\) _that is adjacent to_ \(x\)_._  
Following these ideas, the objective of this subsection is to propose a purification procedure that yields a minimal total outer-independent domination set (see Algorithm 2). Below are two definitions that we will use in the purification procedure. The _private neighborhood_ of a vertex \(x\in T\subseteq V(G)\), denoted by \(pn(x,T,G)\), is given by  
\[pn(x,T,G)=\{y\in V|N(y)\cap T=\{x\}\}.\]  
A vertex in \(pn(x,T,G)\) is referred to as a _private neighbor_ of \(x\). These definitions are equivalent to condition \((i)\) in Lemma 2. Please note that all vertices in the set \(D^{*}\) formed in this way satisfy one of the conditions proposed in Lemma 2, making it a minimal total outer-independent dominating set for the graph \(G\). Using similar reasoning as in the proof of Theorem 5, it follows that the purification procedure can be executed in time \(O(kn^{2})=O(n^{3})\). **Theorem 6**. : _Purify runs in at most \(k\) iterations, and its time complexity is \(O(n^{3})\)._```
Input: A TOIDS \(T_{h}\) and a graph \(G(V,E)\). Output: A minimal TOIDS \(T^{*}\). \(T^{*}=\{v_{1},...,v_{k}\}\); {vertices of \(T_{h}\) in the sequence in which they were included by Stage 1} \(h:=k\); while\(h>0\)do if\(pn(v_{h},T^{*},G)=\emptyset\wedge N_{V\setminus T^{*}}(v_{h})=\emptyset\)then \(T^{*}:=T^{*}\setminus\{v_{h}\}\); {we purify vertex \(v_{h}\)} endif \(h:=h-1\); endwhile
```

**Algorithm 2** Purify

## 4 Experimental Results

This section provides an overview of our computational analysis. We implemented the ILP formulation and Heuristic TOID in C++ using the CPLEX library, both running on a Windows 11 operating system for 64-bit architecture. The experiments were conducted on a personal computer equipped with an Intel Core i7-9750H processor (2.6 GHz) and 16 GB of DDR4 RAM. Our algorithm was tested on a set of 500 benchmark instances from [17; 32; 33]. Since no benchmark instances for the TOIDS problem previously existed, we used optimal values from CPLEX alongside established upper and lower bounds to evaluate heuristic performance. While our computational experiments provide valuable insights into the performance of the proposed heuristic and ILP formulation, some limitations should be considered. First, since no standard benchmark instances existed for this problem, the generated dataset may not fully represent the characteristics of real-world graphs. Second, computational constraints limited the exact resolution of larger instances using CPLEX, which may affect the evaluation of the heuristic's performance in such cases.