×

Vaccinate your trees! (English) Zbl 1426.91118

Summary: For a graph \(G\) and an integer-valued function \({\tau}\) on its vertex set, a dynamic monopoly is a set of vertices of \(G\) such that iteratively adding to it vertices \(u\) of \(G\) that have at least \(\tau(u)\) neighbors in it eventually yields the vertex set of \(G\). We study two vaccination problems, where the goal is to maximize the minimum order of such a dynamic monopoly
either by increasing the threshold value of \(b\) vertices beyond their degrees,
or by removing \(b\) vertices from \(G\),
where \(b\) is a given non-negative integer corresponding to a budget. We show how to solve these problems efficiently for trees.

MSC:

91B24 Microeconomic theory (price theory and economic markets)
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ackerman, E.; Ben-Zwi, O.; Wolfovitz, G., Combinatorial model and bounds for target set selection, Theoret. Comput. Sci., 411, 4017-4022 (2010) · Zbl 1235.90168
[2] Ben-Zwi, O.; Hermelin, D.; Lokshtanov, D.; Newman, I., Treewidth governs the complexity of target set selection, Discrete Optim., 8, 87-96 (2011) · Zbl 1248.90068
[3] Bhawalkar, K.; Kleinberg, J.; Lewi, K.; Roughgarden, T.; Sharma, A., Preventing unraveling in social networks: the anchored k-core problem, SIAM J. Discrete Math., 29, 1452-1475 (2015) · Zbl 1327.68173
[4] Britton, T.; Janson, S.; Martin-Löf, A., Graphs with specified degree distributions, simple epidemics, and local vaccination strategies, Adv. in Appl. Probab., 39, 922-948 (2007) · Zbl 1134.60007
[5] Centeno, C. C.; Dourado, M. C.; Penso, L. D.; Rautenbach, D.; Szwarcfiter, J. L., Irreversible conversion of graphs, Theoret. Comput. Sci., 412, 3693-3700 (2011) · Zbl 1220.05109
[6] Centeno, C. C.; Rautenbach, D., Remarks on dynamic monopolies with given average thresholds, Discuss. Math. Graph Theory, 35, 133-140 (2015) · Zbl 1307.05172
[7] Chiang, C.-Y.; Huang, L.-H.; Li, B.-J.; Wu, J.; Yeh, H.-G., Some results on the target set selection problem, J. Comb. Optim., 25, 702-715 (2013) · Zbl 1273.90224
[8] Cicalese, F.; Cordasco, G.; Gargano, L.; Milanič, M.; Peters, J.; Vaccaro, U., Spread of influence in weighted networks under time and budget constraints, Theoret. Comput. Sci., 586, 40-58 (2015) · Zbl 1327.68175
[9] Chang, C.-L.; Lyuu, Y.-D., Triggering cascades on strongly connected directed graphs, Theoret. Comput. Sci., 593, 62-69 (2015) · Zbl 1331.05093
[10] Chen, N., On the approximability of influence in social networks, SIAM J. Discrete Math., 23, 1400-1415 (2009) · Zbl 1203.68314
[11] Deijfen, M., Epidemics and vaccination on weighted graphs, Math. Biosci., 232, 57-65 (2011) · Zbl 1217.92074
[12] Domingos, P.; Richardson, M., Mining the network value of customers, (Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2001)), 57-66
[13] Dreyer, P. A.; Roberts, F. S., Irreversible k-threshold processes: graph-theoretical threshold models of the spread of disease and of opinion, Discrete Appl. Math., 157, 1615-1627 (2009) · Zbl 1163.92035
[14] Gentner, M.; Rautenbach, D., Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees, Theoret. Comput. Sci., 667, 93-100 (2017) · Zbl 1358.05162
[15] Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence through a social network, Theory Comput., 11, 105-147 (2015) · Zbl 1337.91069
[16] Khoshkhah, K.; Zaker, M., On the largest dynamic monopolies of graphs with a given average threshold, Canad. Math. Bull., 58, 306-316 (2015) · Zbl 1312.05109
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.