Positive influence domination in graphs (Q2082361)

The concept of positive influence dominating set has interesting applications in social network analysis. A subset \(D\) of \(V\) is called a positive influence dominating set (PIDS) of a graph \(G\) if every vertex \(v\) has at least half of its neighbors in \(D.\) Since an individual is inclined to hold positive opinion if more of his friends have a positive opinion and hence, a PIDS can produce a globally positive influence on the entire social network. Sharp lower bounds for the positive influence domination \(\gamma_{PT}(G)\) are presented. From the algorithmic perspective, it is proved that the decision version of the positive influence domination problem is NP-complete even when restricted to bipartite graphs and split graphs. Furthermore, the problem remains APX-complete on graphs with a maximum degree of three.