# Total Outer-Independent Domination Number: Bounds and Algorithms
## 3 Heuristic Algorithm
was, on average, 594 times faster than CPLEX. These findings, along with the excellent approximation ratios shown in Figure 4, emphasize the critical role of heuristics in solving large-scale problems that are computationally infeasible for exact methods. The results reported for our heuristic include the purification stage (Stage 2). The purification process proved effective in practice, as illustrated in Figure 6. In this figure, \(|T|\) and \(|T^{*}|\) represent the number of vertices in the TOIDS before and after purification, respectively. In 99.59% of the analyzed instances, Stage 1 did not yield minimal TOIDS, i.e., Stage 1 produced TOIDS with redundant vertices. The purification process in Stage 2 of our heuristic exhibited different behaviors depending on the graph density. For graphs with a density lower than 0.1, an average of 191.68 vertices were removed, with a minimum of 28 and a maximum of 316. In these instances, on average, 6.81% of the vertices provided by Stage 1 were eliminated. In contrast, for graphs with a density greater than 0.1, the purification process had a significantly smaller impact. The average number of vertices removed was only 2.80, with a minimum of 0 and a maximum of 5. In these cases, the purification step reduced, on average, only 1.09% of the vertices provided by Stage 1. These results highlight that the purification procedure is notably more effective in sparse graphs, where a larger proportion of vertices can be removed, while in denser graphs, the final solution remains almost unchanged after Stage 2. Figures 6(a),b display boxplots illustrating the distribution of purified vertices in graphs with varying densities. The box represents the interquartile range (IQR), encompassing the central 50% of the data. The line within the box marks the median, which is the middle value. The whiskers represent the range of data that is not considered outliers, while any points outside this range are considered outliers. In Figure 6(a), which corresponds to graphs with a density of 0.1 or higher, we observe that the purified vertices are concentrated between 0 and 3. This suggests that the number of purified vertices is generally low in high

Figure 5: Time ILP formulation vs. Heuristic TOID. density graphs, indicating a better quality of the solution delivered by Stage 1. However, Stage 2 is still needed to guarantee a minimal TOIDS. In contrast, Figure 6(b), representing graphs with very low density (almost trees), shows a much wider spread in the values. The number of purified vertices is significantly higher, ranging from 28 to 316 vertices. This indicates that in low-density graphs, where the structure is more dispersed and less connected, the purification process has a much more significant impact. In these cases, it is more likely that many redundant or non-essential vertices can be removed. In summary, Stage 1 of our heuristic tends to be more effective in higher-density graphs, while it faces greater challenges in very low-density graphs. Figure 6: Stage 1 vs. Stage 2 of Heuristic TOID. Figure 7: Distribution of the number of purified vertices. ## 5 Conclusions

In this work, we introduced new lower and upper bounds for \(\gamma_{t}^{oi}(G)\) and presented both an ILP formulation and a heuristic algorithm for addressing the total outer-independent domination problem. As no prior algorithm had been developed for this specific problem, we utilized the optimal solutions generated by CPLEX for our ILP model as a basis for evaluating the performance of our heuristic. Our experiments employed well-established benchmark instances originally designed for the classical domination problem. CPLEX successfully solved 500 of these instances, which included graphs with up to 9100 vertices. In addition, our heuristic consistently produced high-quality solutions for the same benchmarks, achieving an average error of 1.012 vertices across all tested instances. We also identified certain families of graphs where our heuristic guarantees optimal solutions.