Spread of influence with incentives in edge-weighted graphs with emphasis on some families of graphs

Siavash Askari and Manouchehr Zaker ()
Additional contact information
Siavash Askari: Institute for Advanced Studies in Basic Sciences
Manouchehr Zaker: Institute for Advanced Studies in Basic Sciences

Journal of Combinatorial Optimization, 2024, vol. 47, issue 4, No 8, 19 pages

Abstract: Abstract Let $$G=(V, E)$$ G = ( V , E ) be a graph that represents an underlying network. Let $$\tau $$ τ (resp. $${\textbf{p}}$$ p ) be an assignment of non-negative integers as thresholds (resp. incentives) to the vertices of G. The discrete time activation process with incentives corresponding to $$(G, \tau , {\textbf{p}})$$ ( G , τ , p ) is the following. First, all vertices u with $${\textbf{p}}(u)\ge \tau (u)$$ p ( u ) ≥ τ ( u ) are activated. Then at each time t, every vertex u gets activated if the number of previously activated neighbors of u plus $${\textbf{p}}(u)$$ p ( u ) is at least $$\tau (v)$$ τ ( v ) . The optimal target vector problem (OTV) is to find the minimum total incentives $${\sum }_{v\in V} {\textbf{p}}(v)$$ ∑ v ∈ V p ( v ) that activates the whole network. We extend this model of activation with incentives, for graphs with weighted edges such that the spread of activation in the network depends on the weight of influence between any two participants. The new version is more realistic for the real world networks. We first prove that the new problem OTVW, is $$\texttt {NP}$$ NP -complete even for the complete graphs. Two lower bounds for the minimum total incentives are presented. Next, we prove that OTVW has polynomial time solutions for (weighted) path and cycle graphs. Finally, we extend the discussed model and OTV, for bi-directed graphs with weighted edges and prove that to obtain the optimal target vector in weighted bi-directed paths and cycles has polynomial time solutions.

Keywords: Target set selection; Dynamic monopoly; Target vector; Spread of influence; Edge-weighted graphs; Directed graphs; 05C69; 05C85; 05C20; 05C82 (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01164-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:4:d:10.1007_s10878-024-01164-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01164-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().