{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T09:47:55Z","timestamp":1780739275667,"version":"3.54.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T00:00:00Z","timestamp":1680825600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T00:00:00Z","timestamp":1680825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009448","name":"Universit\u00e0 degli Studi della Campania Luigi Vanvitelli","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009448","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the problem of keeping under control the spread of harmful items in networks, such as the contagion proliferation of diseases or the diffusion of fake news. We assume the linear threshold model of diffusion where each node has a threshold that measures the node\u2019s resistance to the contagion. We study the parameterized complexity of the problem: Given a network, a set of initially contaminated nodes, and two integers <jats:italic>k<\/jats:italic> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u2113<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, is it possible to limit the diffusion to at most <jats:italic>k<\/jats:italic> other nodes of the network by immunizing at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u2113<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> nodes? We consider several parameters associated with the input, including the bounds <jats:italic>k<\/jats:italic> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u2113<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the maximum node degree <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Delta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0394<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the number <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\zeta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b6<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of initially contaminated nodes, the treewidth, and the neighborhood diversity of the network. We first give <jats:italic>W<\/jats:italic>[1] or <jats:italic>W<\/jats:italic>[2]-hardness results for each of the considered parameters. Then we give fixed-parameter algorithms for some parameter combinations.<\/jats:p>","DOI":"10.1007\/s00453-023-01118-y","type":"journal-article","created":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T05:02:29Z","timestamp":1680843749000},"page":"3376-3405","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Immunization in the Threshold Model: A Parameterized Complexity Study"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9148-9769","authenticated-orcid":false,"given":"Gennaro","family":"Cordasco","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luisa","family":"Gargano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adele A.","family":"Rescigno","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,4,7]]},"reference":[{"key":"1118_CR1","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Li, S., Markarian, C., Meyer auf der Heide, F., Podlipyan, P.: Modular-width: an auxiliary parameter for parameterized parallel complexity. In: Proc. of Frontiers in Algorithmics (FAW\u201917), LNCS 10336 (2017)","DOI":"10.1007\/978-3-319-59605-1_13"},{"key":"1118_CR2","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1038\/35019019","volume":"404","author":"R Albert","year":"2000","unstructured":"Albert, R., Jeong, H., Barab\u00e1si, A.-L.: Error and attack tolerance of complex networks. Nature 404, 378\u2013382 (2000)","journal-title":"Nature"},{"issue":"1","key":"1118_CR3","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.disopt.2010.09.007","volume":"8","author":"O Ben-Zwi","year":"2011","unstructured":"Ben-Zwi, O., Hermelin, D., Lokshtanov, D., Newman, I.: Treewidth governs the complexity of target set selection. Discret. Optim. 8(1), 87\u201396 (2011). https:\/\/doi.org\/10.1016\/j.disopt.2010.09.007. (ISSN 1572-5286,)","journal-title":"Discret. Optim."},{"issue":"3","key":"1118_CR4","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.1137\/14097032X","volume":"29","author":"K Bhawalkar","year":"2015","unstructured":"Bhawalkar, K., Kleinberg, J., Lewi, K., Roughgarden, T., Sharma, A.: Preventing unraveling in social networks: the anchored $$k$$-core problem. SIAM J. Discret. Math. 29(3), 1452\u20131475 (2015)","journal-title":"SIAM J. Discret. Math."},{"key":"1118_CR5","doi-asserted-by":"publisher","unstructured":"Bogunovic, I.: Robust Protection of Networks against Cascading Phenomena, Master Thesis. ETH Z\u00fcrich (2012). https:\/\/doi.org\/10.3929\/ethz-a-007580645","DOI":"10.3929\/ethz-a-007580645"},{"key":"1118_CR6","doi-asserted-by":"crossref","unstructured":"Chen, P., David, M., Kempe, D.: Better vaccination strategies for better people. In: Proceedings 11th ACM Conference on Electronic Commerce (EC-2010) (2010)","DOI":"10.1145\/1807342.1807370"},{"key":"1118_CR7","doi-asserted-by":"crossref","unstructured":"Cordasco, G., Gargano, L., Mecchia, M., Rescigno, A.A., Vaccaro, U.: A fast and effective heuristic for discovering small target sets in social networks. In: Proc. of the 9th International conference on combinatorial optimization and applications (COCOA\u201915) (2015)","DOI":"10.1007\/978-3-319-26626-8_15"},{"key":"1118_CR8","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2018.05.030","volume":"810","author":"G Cordasco","year":"2020","unstructured":"Cordasco, G., Gargano, L., Lafond, M., Narayanan, L., Rescigno, A.A., Vaccaro, U., Wu, K.: Whom to befriend to influence people. Theoret. Comput. Sci. 810, 26\u201342 (2020)","journal-title":"Theoret. Comput. Sci."},{"key":"1118_CR9","doi-asserted-by":"crossref","unstructured":"Cordasco, G., Gargano, L., Rescigno, A. A.: Influence propagation over large scale social networks. In: Proc. of IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM\u201915), 1531\u20131538 (2015)","DOI":"10.1145\/2808797.2808888"},{"key":"1118_CR10","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2018.02.024","volume":"764","author":"G Cordasco","year":"2019","unstructured":"Cordasco, G., Gargano, L., Rescigno, A.A.: Active influence spreading in social networks. Theoret. Comput. Sci. 764, 15\u201329 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"1118_CR11","doi-asserted-by":"crossref","unstructured":"Cordasco, G., Gargano, L., Rescigno, A.A.: On finding small sets that influence large networks. Soc Netw Anal Min 6(11) (2016)","DOI":"10.1007\/s13278-016-0408-z"},{"issue":"6","key":"1118_CR12","doi-asserted-by":"publisher","first-page":"1804","DOI":"10.1007\/s00453-017-0390-5","volume":"80","author":"G Cordasco","year":"2018","unstructured":"Cordasco, G., Gargano, L., Mecchia, M., Rescigno, A.A., Vaccaro, U.: Discovering small target sets in social networks: a fast and effective algorithm. Algorithmica 80(6), 1804\u20131833 (2018)","journal-title":"Algorithmica"},{"issue":"4","key":"1118_CR13","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1002\/net.21756","volume":"71","author":"G Cordasco","year":"2018","unstructured":"Cordasco, G., Gargano, L., Rescigno, A.A., Vaccaro, U.: Evangelism in social networks: algorithms and complexity. Networks 71(4), 346\u2013357 (2018)","journal-title":"Networks"},{"key":"1118_CR14","doi-asserted-by":"crossref","unstructured":"Cordasco, G., Gargano, L., Rescigno, A. A.: Iterated type partitions. In:Proceedings of International Workshop on Combinatorial Algorithms (IWOCA\u201920), pp. 195\u2013210 (2020)","DOI":"10.1007\/978-3-030-48966-3_15"},{"key":"1118_CR15","doi-asserted-by":"crossref","unstructured":"Cordasco, G., Gargano, L., Rescigno, A. A.: Vertex separation in networks. In Proc. of the 8th International Conference on Social Network Analysis, Management and Security (SNAMS\u201921) (2021)","DOI":"10.1109\/SNAMS53716.2021.9732127"},{"key":"1118_CR16","doi-asserted-by":"crossref","unstructured":"Cordasco, G., Gargano, L., Rescigno, A. A.: Parameterized complexity of immunization in the threshold model. In Proc. of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM\u201922) (2022)","DOI":"10.1007\/978-3-030-96731-4_23"},{"key":"1118_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"1118_CR18","volume-title":"Parameterized Complexity","author":"RG Downey","year":"2012","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (2012)"},{"key":"1118_CR19","doi-asserted-by":"publisher","unstructured":"Dvor\u00e1k, P., Knop, D., Toufar, T.: Target set selection in dense graph classes. In: Proc. of 29th International Symposium on Algorithms and Computation (ISAAC\u201918) (2018) https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.18","DOI":"10.4230\/LIPIcs.ISAAC.2018.18"},{"key":"1118_CR20","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.tcs.2018.11.018","volume":"772","author":"S Ehard","year":"2019","unstructured":"Ehard, S., Rautenbach, D.: Vaccinate your trees! Theoret. Comput. Sci. 772, 46\u201357 (2019)","journal-title":"Theoret. Comput. Sci."},{"issue":"180","key":"1118_CR21","first-page":"184","volume":"429","author":"S Eubank","year":"2004","unstructured":"Eubank, S., Guclu, H., Kumar, V.S.A., Marathe, M.V., Srinivasan, A., Toroczkai, Z., Wang, N.: Modelling disease outbreaks in realistic urban social networks. Nature 429(180), 184 (2004)","journal-title":"Nature"},{"key":"1118_CR22","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1016\/S0166-218X(02)00394-3","volume":"127","author":"U Feige","year":"2003","unstructured":"Feige, U., Krauthgamer, R., Nissim, K.: On cutting a few vertices from a graph. Discret. Appl. Math. 127, 643\u2013649 (2003)","journal-title":"Discret. Appl. Math."},{"key":"1118_CR23","first-page":"57","volume":"43","author":"S Finbow","year":"2009","unstructured":"Finbow, S., MacGillivray, G.: The firefighter problem: a survey of results, directions and questions. Austral. J. Combinat. 43, 57\u201377 (2009)","journal-title":"Austral. J. Combinat."},{"key":"1118_CR24","unstructured":"Feige, U., Kogan, S.: Target set selection for conservative population. CoRR abs\/1909.03422 (2019)"},{"key":"1118_CR25","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Golovach, P.A., Korhonen, J.H.: On the parameterized complexity of cutting a few vertices from a graph. In: Proc. of International Symposium on Mathematical Foundations of Computer Science (MFCS\u201913) (2013)","DOI":"10.1007\/978-3-642-40313-2_38"},{"key":"1118_CR26","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.tcs.2014.11.029","volume":"566","author":"L Gargano","year":"2015","unstructured":"Gargano, L., Rescigno, A.A.: Complexity of conflict-free colorings of graphs. Theoret. Comput. Sci. 566, 39\u201349 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"1118_CR27","unstructured":"Gavenciak, T., Knop, D., Kouteck\u00fd, M.: Integer programming in parameterized complexity: three miniatures. In: Proc. of Intern. Symp. on Parameterized and Exact Computation, (IPEC\u201918) (2018)"},{"issue":"6","key":"1118_CR28","doi-asserted-by":"publisher","first-page":"1420","DOI":"10.1086\/226707","volume":"83","author":"M Granovetter","year":"1978","unstructured":"Granovetter, M.: Threshold models of collective behaviors. Am. J. Sociol. 83(6), 1420\u20131443 (1978)","journal-title":"Am. J. Sociol."},{"key":"1118_CR29","doi-asserted-by":"crossref","unstructured":"Hayrapetyan, A., Kempe, D., Pal, M., Svitkina Z.: Unbalanced graph cuts. In: Proc. European Symposium on Algorithms (ESA 2005), LNCS 3669, pp. 191\u2013202 (2005)","DOI":"10.1007\/11561071_19"},{"key":"1118_CR30","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/j.tcs.2019.09.025","volume":"796","author":"T Hanaka","year":"2019","unstructured":"Hanaka, T., Bodlaender, H.L., van der Zanden, T.C., Ono, H.: On the maximum weight minimal separator. Theoret. Comput. Sci. 796, 294\u2013308 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"1118_CR31","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proc. of the 9th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 137\u2013146 (2003)","DOI":"10.1145\/956750.956769"},{"key":"1118_CR32","unstructured":"Khalil, E.B., Dilkina, B., Song, L.: CuttingEdge: Influence Minimization in Networks. Methods, Models, and Applications at NIPS. In: Workshop on Frontiers of Network Analysis (2013)"},{"key":"1118_CR33","doi-asserted-by":"crossref","unstructured":"Kimura, M., Saito, K., Motoda, H.: Blocking links to minimize contamination spread in a social network. ACM Trans. Knowl. Discovery Data 3(2) (2009)","DOI":"10.1145\/1514888.1514892"},{"key":"1118_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth Computations and Approximations. Springer, Berlin (1994). https:\/\/doi.org\/10.1007\/BFb0045375"},{"key":"1118_CR35","unstructured":"Knop, D., Kouteck\u00fd, M., Masar\u00edk, T., Toufar, T.; Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity. Log. Methods Comput. Sci. 15(4) (2019)"},{"key":"1118_CR36","doi-asserted-by":"crossref","unstructured":"Komusiewicz, C., Sorge, M.: Finding dense subgraphs of sparse graphs. In: Parameterized and Exact Computation, LNCS 7535 (2012)","DOI":"10.1007\/978-3-642-33293-7_23"},{"key":"1118_CR37","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00453-011-9554-x","volume":"64","author":"M Lampis","year":"2012","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64, 19\u201337 (2012)","journal-title":"Algorithmica"},{"key":"1118_CR38","doi-asserted-by":"crossref","unstructured":"Meier, D., Oswald, Y.A., Schmid, S., Wattenhofer, R.: On the windfall of friendship: inoculation strategies on social networks. In: Proc of EC\u201908, pp 294\u2013301 (2008)","DOI":"10.1145\/1386790.1386836"},{"key":"1118_CR39","doi-asserted-by":"publisher","DOI":"10.1017\/9781108653947","volume-title":"A First Course in Network Science","author":"F Menczer","year":"2020","unstructured":"Menczer, F., Fortunato, S., Davis, C.A.: A First Course in Network Science, 1st edn. Cambridge University Press, Cambridge (2020)","edition":"1"},{"key":"1118_CR40","doi-asserted-by":"crossref","unstructured":"Newman, M.E.J., Forrest, S., Balthrop, J.: Email networks and the spread of computer viruses. Phys. Rev. E 66 (2002)","DOI":"10.1103\/PhysRevE.66.035101"},{"key":"1118_CR41","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)"},{"issue":"3","key":"1118_CR42","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01118-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01118-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01118-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T19:02:59Z","timestamp":1698778979000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01118-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,7]]},"references-count":42,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["1118"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01118-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,7]]},"assertion":[{"value":"10 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}