Global total domination number: exact and approximate results

A nonempty set $S\subseteq V$ is a global total dominating set (GTDS) in a graph $G=(V,E)$ if every vertex in both $G$ and its complement $\overline{G}$ is adjacent to at least one vertex in $S$. The problem of finding a GTDS with the minimum cardinality ${\gamma }_t^g(G)$ is $NP$-hard, whereas no exact or approximation algorithm is known for the problem. We derive several new bounds and exact results for ${\gamma }_t^g(G)$, particularly for graphs of diameter $2$ and triangle-free graphs. We propose an integer linear programming (ILP) model, as a natural adaptation of a previous model for the global dominating set problem. We build three heuristic algorithms that we evaluate against optimal solutions for benchmark instances with up to 10,700 vertices, the only benchmark instances which were solved by the ILP solver CPLEX using our ILP model. At least one of our heuristics generated an optimal solution for 41% of the instances for which CPLEX proved optimality, while for the remaining instances in this subset, the average absolute deviation from the optimum was only 1.58 vertices. In total, we report the behavior of the heuristics for over 1,100 instances with up to 25,000 vertices. In particular, Heuristics H2 and H3 run in time $O(n^3)$, and all proposed methods obtained solutions within 5 minutes in our computational experiments.