On some tractable and hard instances for partial incentives and target set selection

Dreyer, 2009, Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Discrete Appl. Math., 157, 1615, 10.1016/j.dam.2008.09.012

Kempe, 2015, Maximizing the spread of influence through a social network, Theory Comput., 11, 105, 10.4086/toc.2015.v011a004

Centeno, 2011, Irreversible conversion of graphs, Theoret. Comput. Sci., 412, 3693, 10.1016/j.tcs.2011.03.029

Chen, 2009, On the approximability of influence in social networks, SIAM J. Discrete Math., 23, 1400, 10.1137/08073617X

Ben-Zwi, 2011, Treewidth governs the complexity of target set selection, Discrete Optim., 8, 87, 10.1016/j.disopt.2010.09.007

Bessy, 2019, Dynamic monopolies for interval graphs with bounded thresholds, Discrete Appl. Math., 260, 256, 10.1016/j.dam.2019.01.022

Kynčl, 2017, Irreversible 2-conversion set in graphs of bounded degree, Discrete Math. Theor. Comput. Sci., 19, # 3

Cordasco, 2015, Optimizing spread of influence in social networks via partial incentives, Lecture Notes in Comput. Sci., 9439, 119, 10.1007/978-3-319-25258-2_9

Ackerman, 2010, Combinatorial model and bounds for target set selection, Theoret. Comput. Sci., 411, 4017, 10.1016/j.tcs.2010.08.021

Reichman, 2012, New bounds for contagious sets, Discrete Math., 312, 1812, 10.1016/j.disc.2012.01.016

Brause, 2018

Abrahamson, 1995, Fixed parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogues, Ann. Pure Appl. Logic, 73, 235, 10.1016/0168-0072(94)00034-Z

Chopin, 2014, Constant thresholds can make target set selection tractable, Theory Comput. Syst., 55, 61, 10.1007/s00224-013-9499-3

Hartmann, 2017, Target set selection parameterized by clique–width and maximum threshold, Lecture Notes in Comput. Sci., 10706, 137, 10.1007/978-3-319-73117-9_10

Papadimitriou, 1991, Optimization, approximation, and complexity classes, J. Comput. System Sci., 43, 425, 10.1016/0022-0000(91)90023-X

Baker, 1994, Approximation algorithms for NP-complete problems on planar graphs, J. ACM, 41, 153, 10.1145/174644.174650

Demaine, 2005, Bidimensionality: New connections between FPT algorithms and PTASs, 590

Demaine, 2008, The bidimensionality theory and its algorithmic applications, Comput. J., 51, 292, 10.1093/comjnl/bxm033

Alber, 2002, Fixed parameter algorithms for dominating set and related problems on planar graphs, Algorithmica, 33, 461, 10.1007/s00453-001-0116-5

Garey, 1976, Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237, 10.1016/0304-3975(76)90059-1

Kloks, 1994, vol. 842

Arnborg, 1987, Complexity of finding embeddings in a k-tree, SIAM J. Algebr. Discrete Methods, 8, 277, 10.1137/0608024

Chiang, 2013, Some results on the target set selection problem, J. Comb. Optim., 25, 702, 10.1007/s10878-012-9518-3

Booth, 1976, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13, 335, 10.1016/S0022-0000(76)80045-1

Bodlaender, 1998, A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1, 10.1016/S0304-3975(97)00228-4

Aazami, 2009, Approximation algorithms and hardness for domination with propagation, SIAM J. Discrete Math., 23.3, 1382, 10.1137/06066672X

Z. Dvorák, S. Norin, Treewidth of graphs with balanced separations, arXiv:1408.3869.

Lipton, 1979, A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 177, 10.1137/0136016