On some tractable and hard instances for partial incentives and target set selection
From MaRDI portal
Publication:2010927
DOI10.1016/j.disopt.2019.05.004zbMath1506.91132arXiv1805.10086WikidataQ127728240 ScholiaQ127728240MaRDI QIDQ2010927
Stefan Ehard, Dieter Rautenbach
Publication date: 28 November 2019
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.10086
91D30: Social networks; opinion dynamics
68R10: Graph theory (including graph drawing) in computer science
91B24: Microeconomic theory (price theory and economic markets)
68W25: Approximation algorithms
Related Items
Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree, Target set selection with maximum activation time, Target set selection for conservative populations, Fast and frugal targeting with incentives, Domination and convexity problems in the target set selection model
Cites Work
- Unnamed Item
- Unnamed Item
- Combinatorial model and bounds for target set selection
- New bounds for contagious sets
- Treewidth governs the complexity of target set selection
- Irreversible conversion of graphs
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Optimization, approximation, and complexity classes
- Some simplified NP-complete graph problems
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- Dynamic monopolies for interval graphs with bounded thresholds
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Some results on the target set selection problem
- Constant thresholds can make target set selection tractable
- Treewidth of graphs with balanced separations
- Optimizing Spread of Influence in Social Networks via Partial Incentives
- On the Approximability of Influence in Social Networks
- Complexity of Finding Embeddings in a k-Tree
- A Separator Theorem for Planar Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Irreversible 2-conversion set in graphs of bounded degree
- Target Set Selection Parameterized by Clique-Width and Maximum Threshold
- Approximation Algorithms and Hardness for Domination with Propagation
