Total Positive Influence Domination in Graphs: Bounds, Exact Optimization, and Heuristics

Abstract We study the total positive influence domination problem (TPIDS), in which every vertex must have at least $\lceil d(v)/2\rceil$ neighbors in the selected set. We establish lower and upper bounds in terms of classical graph parameters and introduce a new lower bound based on the degree sequence, which can be computed in linear time once the degree sequence is available. We characterize minimal total positive influence dominating sets through private influence vertices and develop a purification procedure that transforms feasible solutions into minimal ones while preserving feasibility. We also formulate the optimization problem as a binary integer linear program and propose a constructive greedy heuristic based on support-vertex initialization and a maximum-total-active-degree selection rule. Both the heuristic and the purification procedure admit adjacency-list implementations running in $O(n+m)$ time. We prove an instance-dependent harmonic approximation guarantee $H(\kappa(G))$ for the heuristic, where $\kappa(G)\leq\Delta(G)$; thus, $H(\kappa(G))\leq H(\Delta(G))$, with a possible improvement of at most $\ln(\Delta(G)/\kappa(G))$ in the approximation factor. Computational experiments on 1196 benchmark instances show that the heuristic produces feasible solutions for all instances and that the three purification strategies produce feasible minimal TPIDS, consistently with the corresponding theoretical guarantees. Purification strictly reduces the solution cardinality in 89.38% of the instances. On the 76 instances with certified optimality, purification reduces the average absolute error from 3.20 to 2.37 vertices and the average relative error from 4.80% to 3.55%.