Positive influence domination in graphs (Q2082361)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Positive influence domination in graphs |
scientific article |
Statements
Positive influence domination in graphs (English)
0 references
4 October 2022
0 references
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.
0 references
positive influence dominating set
0 references
positive influence domination number
0 references
bounds
0 references
NP-complete
0 references
APX-complete
0 references
0 references