# Total Outer-Independent Domination Number: Bounds and Algorithms
If \(H_{1}\), \(H_{2}\),..., \(H_{k}\) with \(k\geq 2\) are the connected components of a graph \(G(V,E)\) with \(\delta(G)\geq 1\), then any TOIDS of \(G(V,E)\) is the union of TOIDSs from each connected component \(H_{i}\), for \(i=1,\ldots,k\). This is expressed in the following simple result. **Remark 1**. : _Let \(H_{1}\), \(H_{2}\),..., \(H_{k}\) with \(k\geq 2\) be the components of a non-connected graph \(G(V,E)\) that has no isolated vertices. Then_  
\[\gamma_{t}^{ai}(G)=\sum_{i=1}^{k}\gamma_{t}^{ai}(H_{i}).\]  
Aligned with the previous remark, we will henceforth restrict our analysis to TOIDS in nontrivial connected graphs. The study of TOIDS has gained considerable attention in recent years, owing to their valuable practical applications and extensive theoretical properties [4; 12; 13; 14; 15]. The objective is to identify a TOIDS with the smallest cardinality, which is an _optimal_ total outer-independent dominating set. However, as demonstrated in [4], this problem has been proven to be \(NP\)-complete. A problem is considered NP-complete if it is part of the NP class (nondeterministic polynomial time), and every other NP problem can be reduced to it in polynomial time. In simpler terms, an NP-complete problem is as hard as any other problem within NP. If a polynomial-time solution is discovered for any NP-complete problem, then all problems in NP would be solvable in polynomial time. Since no polynomial-time algorithm is currently known for NP-complete problems, research often focuses on approximation algorithms, heuristics, and integer programming formulations to obtain efficient solutions for practical instances. In [5], a polynomial-time algorithm is proposed to compute \(\gamma_{t}^{ai}(G)\) for trees. In addition, refs. [4; 14; 15; 16] have presented various upper and lower bounds for the problem. As far as we know, no further results have been reported concerning this issue. In particular, to the best of our knowledge, no exact or approximation algorithms have been previously suggested for the TOIDS problem in general graph classes. This paper presents new lower and upper bounds for \(\gamma_{t}^{ai}(G)\). We also propose an exact solution approach using an integer linear programming (ILP) formulation alongside a heuristic method and a purification procedure to reduce the size of the total outer-independent dominating set produced by the heuristic. Additionally, we provide experimental results and computational analyses to assess the performance of both the ILP and heuristic methods across 500 graph instances. Our ILP approach successfully found optimal solutions for graphs with up to 9100 vertices. Specifically, we computed \(\gamma_{t}^{oi}(G)\) for the 500 graph with \(50\leq|V(G)|\leq 9100\), which were randomly generated and can now be used as benchmarks for future research. These \(\gamma_{t}^{oi}(G)\) values and the corresponding instances are publicly available in [17]. Interestingly, in about 28.69% of the cases where the exact algorithm produced an optimal solution, the heuristic also yielded an optimal result. For the remaining instances, the average absolute error was roughly 1.012 vertices, with an average approximation ratio of 1.0032. In summary, our work contributes to the understanding and advancement of the total outer-independent dominating set problem, offering insights into its structural properties and providing a practical algorithm for its computation. Section 2 explores new upper and lower bounds for \(\gamma_{t}^{oi}(G)\) and establishes relationships with other domination and independence parameters, along with an ILP formulation. Section 3 presents our heuristic, defines several graph families for which it provides an optimal solution, and outlines a purification process. Finally, Section 4 provides a detailed overview of our experimental results.