Establishing herd immunity is hard even in simple geometric networks. (English) Zbl 1536.92118
Dewar, Megan (ed.) et al., Algorithms and models for the web graph. 18th international workshop, WAW 2023, Toronto, ON, Canada, May 23–26, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13894, 68-82 (2023).
The paper establishes that herd immunity is hard even in simple geometric networks. It studies the target set selection problem restricted to instances where the underlying graph is a unit disk graph. It is shown that target set selection problem is NP-complete on unit disk graphs even if the threshold function is bounded by a constant \(c\ge 2\), is equal to majority, or is unanimous. For grid graphs, it is shown that target set selection problem is NP-complete for constant and majority threshold and it is polynomial-time solvable for unanimous thresholds. Furthermore, the paper shows that the problem is solvable in polynomial-time on interval graphs even if the threshold function is unanimous.
For the entire collection see [Zbl 1521.68009].
For the entire collection see [Zbl 1521.68009].
Reviewer: Yilun Shang (Newcastle upon Tyne)
References:
| [1] | Araújo, RT; Sampaio, RM; dos Santos, VF; Szwarcfiter, JL, The convexity of induced paths of order three and applications: complexity aspects, Discret. Appl. Math., 237, 33-42 (2018) · Zbl 1380.05031 · doi:10.1016/j.dam.2017.11.007 |
| [2] | Ben-Zwi, O.; Hermelin, D.; Lokshtanov, D.; Newman, I., Treewidth governs the complexity of target set selection, Discrete Optim., 8, 1, 87-96 (2011) · Zbl 1248.90068 · doi:10.1016/j.disopt.2010.09.007 |
| [3] | Bessy, S.; Ehard, S.; Penso, LD; Rautenbach, D., Dynamic monopolies for interval graphs with bounded thresholds, Discret. Appl. Math., 260, 256-261 (2019) · Zbl 1409.05202 · doi:10.1016/j.dam.2019.01.022 |
| [4] | Blažej, V., Knop, D., Schierreich, Š.: Controlling the spread of two secrets in diverse social networks (student abstract). In: AAAI 2022, pp. 12919-12920. AAAI Press (2022). https://ojs.aaai.org/index.php/AAAI/article/view/21596 |
| [5] | Breu, H.; Kirkpatrick, DG, Unit disk graph recognition is NP-hard, Comput. Geom., 9, 1, 3-24 (1998) · Zbl 0894.68099 · doi:10.1016/S0925-7721(97)00014-X |
| [6] | Chen, N., On the approximability of influence in social networks, SIAM J. Discrete Math., 23, 3, 1400-1415 (2009) · Zbl 1203.68314 · doi:10.1137/08073617X |
| [7] | Chiang, CY; Huang, LH; Li, BJ; Wu, J.; Yeh, HG, Some results on the target set selection problem, J. Comb. Optim., 25, 4, 702-715 (2013) · Zbl 1273.90224 · doi:10.1007/s10878-012-9518-3 |
| [8] | Chopin, M.; Nichterlein, A.; Niedermeier, R.; Weller, M., Constant thresholds can make target set selection tractable, Theory Comput. Syst., 55, 1, 61-83 (2013) · Zbl 1319.68109 · doi:10.1007/s00224-013-9499-3 |
| [9] | Cicalese, F.; Cordasco, G.; Gargano, L.; Milanič, M.; Vaccaro, U., Latency-bounded target set selection in social networks, Theor. Comput. Sci., 535, 1-15 (2014) · Zbl 1358.05272 · doi:10.1016/j.tcs.2014.02.027 |
| [10] | Clark, BN; Colbourn, CJ; Johnson, DS, Unit disk graphs, Discrete Math., 86, 1, 165-177 (1990) · Zbl 0739.05079 · doi:10.1016/0012-365X(90)90358-O |
| [11] | Dahlhaus, E.; Johnson, DS; Papadimitriou, CH; Seymour, PD; Yannakakis, M., The complexity of multiterminal cuts, SIAM J. Comput., 23, 4, 864-894 (1994) · Zbl 0809.68075 · doi:10.1137/S0097539792225297 |
| [12] | Dimitrov, D.; Herrera-Viedma, E.; García-Lapresta, JL; Kacprzyk, J.; Fedrizzi, M.; Nurmi, H.; Zadrożny, S., The social choice approach to group identification, Consensual Processes, 123-134 (2011), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-20533-0_7 |
| [13] | Dreyer, PA; Roberts, FS, Irreversible \(k\)-threshold processes: graph-theoretical threshold models of the spread of disease and of opinion, Discret. Appl. Math., 157, 7, 1615-1627 (2009) · Zbl 1163.92035 · doi:10.1016/j.dam.2008.09.012 |
| [14] | Dvořák, P.; Knop, D.; Toufar, T., Target set selection in dense graph classes, SIAM J. Discrete Math., 36, 1, 536-572 (2022) · Zbl 1542.68142 · doi:10.1137/20M1337624 |
| [15] | Erdélyi, G.; Reger, C.; Yang, Y., The complexity of bribery and control in group identification, Auton. Agent. Multi-Agent Syst., 34, 1, 1-31 (2019) · doi:10.1007/s10458-019-09427-9 |
| [16] | Farber, M., Independent domination in chordal graphs, Oper. Res. Lett., 1, 4, 134-138 (1982) · Zbl 0495.05053 · doi:10.1016/0167-6377(82)90015-3 |
| [17] | Finbow, S.; MacGillivray, G., The firefighter problem: a survey of results, directions and questions, Australas. J. Comb., 43, 57-77 (2009) · Zbl 1179.05112 |
| [18] | Fleischner, H.; Sabidussi, G.; Sarvanov, VI, Maximum independent sets in 3- and 4-regular hamiltonian graphs, Discrete Math., 310, 20, 2742-2749 (2010) · Zbl 1257.05116 · doi:10.1016/j.disc.2010.05.028 |
| [19] | Fomin, FV; Heggernes, P.; van Leeuwen, EJ, The firefighter problem on graph classes, Theor. Comput. Sci., 613, 38-50 (2016) · Zbl 1333.05290 · doi:10.1016/j.tcs.2015.11.024 |
| [20] | Gallai, T., Über extreme punkt- und kantenmengen, Ann. Univ. Sci. Budapest, 2, 133-138 (1959) · Zbl 0094.36105 |
| [21] | Hartmann, TA; Tjoa, AM; Bellatreche, L.; Biffl, S.; van Leeuwen, J.; Wiedermann, J., Target set selection parameterized by clique-width and maximum threshold, SOFSEM 2018: Theory and Practice of Computer Science, 137-149 (2018), Cham: Springer, Cham · Zbl 1444.68144 · doi:10.1007/978-3-319-73117-9_10 |
| [22] | Hartnell, B.L.: Firefighter! an application of domination (1995) |
| [23] | Hliněný, P.; Kratochvíl, J., Representing graphs by disks and balls (a survey of recognition-complexity results), Discrete Math., 229, 1, 101-124 (2001) · Zbl 0969.68118 · doi:10.1016/S0012-365X(00)00204-1 |
| [24] | Huson, M.L., Sen, A.: Broadcast scheduling algorithms for radio networks. In: MILCOM 1995, vol. 2, pp. 647-651 (1995). doi:10.1109/MILCOM.1995.483546 |
| [25] | Kang, RJ; Müller, T., Sphere and dot product representations of graphs, Discrete Comput. Geom., 47, 3, 548-568 (2012) · Zbl 1238.05180 · doi:10.1007/s00454-012-9394-8 |
| [26] | Kasher, A., Rubinstein, A.: On the question “who is a J?” a social choice approach. Logique et Analyse 40(160), 385-395 (1997) · Zbl 0976.91013 |
| [27] | Kempe, D.; Kleinberg, J.; Tardos, É., Maximizing the spread of influence through a social network, Theory Comput., 11, 4, 105-147 (2015) · Zbl 1337.91069 · doi:10.4086/toc.2015.v011a004 |
| [28] | Mathieson, L., The parameterized complexity of editing graphs for bounded degeneracy, Theor. Comput. Sci., 411, 34-36, 3181-3187 (2010) · Zbl 1207.05200 · doi:10.1016/j.tcs.2010.05.015 |
| [29] | Matsui, T.; Akiyama, J.; Kano, M.; Urabe, M., Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs, Discrete and Computational Geometry, 194-200 (2000), Heidelberg: Springer, Heidelberg · Zbl 0955.05100 · doi:10.1007/978-3-540-46515-7_16 |
| [30] | Nichterlein, A.; Niedermeier, R.; Uhlmann, J.; Weller, M., On tractable cases of target set selection, Soc. Netw. Anal. Min., 3, 2, 233-256 (2013) · Zbl 1310.68115 · doi:10.1007/s13278-012-0067-7 |
| [31] | Peleg, D.: Majority voting, coalitions and monopolies in graphs. In: SIROCCO 1996, pp. 152-169. Carleton Scientific (1996) |
| [32] | Reddy, TVT; Krishna, DS; Rangan, CP; Rahman, MS; Fujita, S., Variants of spreading messages, WALCOM: Algorithms and Computation, 240-251 (2010), Heidelberg: Springer, Heidelberg · Zbl 1274.68689 · doi:10.1007/978-3-642-11440-3_22 |
| [33] | Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing. In: KDD 2002, pp. 61-70. ACM, New York (2002). doi:10.1145/775047.775057 |
| [34] | Valiant, LG, Universality considerations in VLSI circuits, IEEE Trans. Comput., 30, 2, 135-140 (1981) · Zbl 0455.94046 · doi:10.1109/TC.1981.6312176 |
| [35] | Yang, Y.; Dimitrov, D., How hard is it to control a group?, Auton. Agent. Multi-Agent Syst., 32, 5, 672-692 (2018) · doi:10.1007/s10458-018-9392-1 |
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.
