# Total Outer-Independent Domination Number: Bounds and Algorithms
## 3 Heuristic Algorithm
Finally, further experiments on graphs from real-world applications would be necessary to assess the generalizability of our approach beyond the tested instances. Table 1 presents the values of \(\gamma_{t}^{ai}(G)\) for 39 instances out of the 500 analyzed using CPLEX. These instances were randomly selected from the full dataset. Additionally, \(T\) and \(T^{*}\) represent the solutions provided by our heuristic in Stages 1 and 2, respectively. The values of \(\gamma_{t}^{ai}(G)\) shown in Table 1 can be compared with the solutions obtained by the heuristic. This comparison enables an assessment of the accuracy and effectiveness of the heuristic in estimating \(\gamma_{t}^{ai}(G)\) for the analyzed instances. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Graph**} & \multirow{2}{*}{\(|\mathbf{V}|\)} & \multirow{2}{*}{\(|\mathbf{E}|\)} & \multicolumn{4}{c}{**ILP Formulation**} & \multicolumn{4}{c}{**Heuristic TOID**} \\ \cline{4-9}  & & & & \multicolumn{2}{c}{**Stage 1**} & \multicolumn{2}{c}{**Stage 2 (Purify)**} \\ \cline{4-9}  & & & \(\gamma_{t}^{ai}(G)\) & **Time (s)** & **Time (s)** & \(|\mathbf{T}|\) & **Time (s)** & \(|\mathbf{T^{*}}|\) \\ \hline BD0\_1 & 50 & 306 & 37 & 0.230068 & 0. Figure 3 presents a comparison between the solutions produced by our Heuristic TOID and the optimal values obtained by CPLEX for instances with up to 9100 vertices. Our heuristic successfully found the optimal solution in 28.69% of the instances. For the cases where the optimal solution was not achieved, the average absolute error was approximately 1.012 vertices. Figure 4 shows the approximation ratio of our heuristic in those instances where the optimal solution was not found. For these instances, the minimum approximation ratio was 1.00028, the maximum was 1.05555, and the average was 1.0032. Figure 4 also reveals a clear trend toward reducing the approximation ratio as the number of vertices increases. This result highlights the strong performance of our heuristic in terms of approximation ratio for instances with a larger number of vertices. The low approximation ratios demonstrate the high quality of our heuristic in efficiently providing near-optimal solutions. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & & & & & & & \multicolumn{3}{c}{**Heuristic TOID**} \\ \cline{4-9}
**Graph** & \(|V|\) & \(|E|\) & & & & & **Stage 1** & **Stage 2 (Purify)** \\ \cline{4-9}  & & & & \(\gamma_{t}^{ai}(G)\) & **Time (s)** & **Time (s)** & \(|T|\) &



The execution time of CPLEX and the heuristic varies depending on the density of the analyzed instances. In our analysis, graph density is defined as \(\frac{2m}{n(n-1)}\). Figure 4(a),b compare the time taken by CPLEX to find \(\gamma_{t}^{ai}(G)\) with the time taken by the heuristic to find a feasible solution, considering graph density. Figure 4(a) shows the execution time for instances with a density of less than 0.1. For these instances, CPLEX performed better; on average, it was approximately 48.15 times faster than the heuristic. CPLEX successfully solved instances of this type with up to 9100 vertices. However, for instances with more than 9100 vertices, CPLEX ran out of available memory on the system and failed to find the optimal solution. Whereas the heuristic was not constrained by memory capacity, successfully solving instances with more than 14,000 vertices. Figure 4(b) shows the execution time for instances with a density greater than 0.1. For these instances, the heuristic outperformed CPLEX, being approximately 650.32 times faster on average. CPLEX was able to solve instances of this type with up to 1100 vertices, while the heuristic successfully solved instances with up to 14,100 vertices in less than two hours without reaching the memory limit (see BD4_xx instances in Table 1). In instances where the heuristic identified the optimal solution, i.e., a \(\gamma_{t}^{ai}(G)\)-set, regardless of the instance density, the heuristic

Figure 4: Approximation Ratio. Figure 3: Approximation results vs. \(\gamma_{t}^{ai}(G)\).