{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:08:40Z","timestamp":1757621320480,"version":"3.44.0"},"publisher-location":"Singapore","reference-count":31,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819502172"},{"type":"electronic","value":"9789819502189"}],"license":[{"start":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T00:00:00Z","timestamp":1754179200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T00:00:00Z","timestamp":1754179200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-0218-9_18","type":"book-chapter","created":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T21:09:32Z","timestamp":1754168972000},"page":"239-252","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity of\u00a0Influence Maximization"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-5996-7206","authenticated-orcid":false,"given":"Panfeng","family":"Liu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4098-844X","authenticated-orcid":false,"given":"Biaoshuai","family":"Tao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,3]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.jda.2014.05.001","volume":"27","author":"C Bazgan","year":"2014","unstructured":"Bazgan, C., Chopin, M., Nichterlein, A., Sikora, F.: Parameterized approximability of maximizing the spread of influence in networks. J. Discrete Algorithms 27, 54\u201365 (2014)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"18_CR2","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)","journal-title":"Discret. Optim."},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Borgs, C., Brautbar, M., Chayes, J., Lucier, B.: Maximizing social influence in nearly optimal time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 946\u2013957. SIAM (2014)","DOI":"10.1137\/1.9781611973402.70"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Brown, J.J., Reingen, P.H.: Social ties and word-of-mouth referral behavior. J. Consum. Res. 14(3), 350\u2013362 (1987)","DOI":"10.1086\/209118"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 177\u2013186 (2008)","DOI":"10.1145\/1374376.1374404"},{"issue":"3","key":"18_CR6","doi-asserted-by":"publisher","first-page":"1400","DOI":"10.1137\/08073617X","volume":"23","author":"N Chen","year":"2009","unstructured":"Chen, N.: On the approximability of influence in social networks. SIAM J. Discret. Math. 23(3), 1400\u20131415 (2009)","journal-title":"SIAM J. Discret. Math."},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1029\u20131038 (2010)","DOI":"10.1145\/1835804.1835934"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Chen, W., Yuan, Y., Zhang, L.: Scalable influence maximization in social networks under the linear threshold model. In: 2010 IEEE International Conference on Data Mining, pp. 88\u201397. IEEE (2010)","DOI":"10.1109\/ICDM.2010.118"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s00224-013-9499-3","volume":"55","author":"M Chopin","year":"2014","unstructured":"Chopin, M., Nichterlein, A., Niedermeier, R., Weller, M.: Constant thresholds can make target set selection tractable. Theory Comput. Syst. 55, 61\u201383 (2014)","journal-title":"Theory Comput. Syst."},{"key":"18_CR10","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: Combinatorial Optimization and Applications: 9th International Conference, 2015, Houston, TX, USA, pp. 193\u2013208. Springer (2015)","DOI":"10.1007\/978-3-319-26626-8_15"},{"issue":"1","key":"18_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s13278-016-0408-z","volume":"6","author":"G Cordasco","year":"2016","unstructured":"Cordasco, G., Gargano, L., Rescigno, A.A.: On finding small sets that influence large networks. Soc. Netw. Anal. Min. 6(1), 1\u201320 (2016). https:\/\/doi.org\/10.1007\/s13278-016-0408-z","journal-title":"Soc. Netw. Anal. Min."},{"key":"18_CR12","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":"18_CR13","doi-asserted-by":"crossref","unstructured":"Cygan, M., et al.: Parameterized Algorithms, vol.\u00a05. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Domingos, P., Richardson, M.: Mining the network value of customers. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2001, pp. 57\u201366. ACM, New York (2001)","DOI":"10.1145\/502512.502525"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R., et\u00a0al.: Fundamentals of Parameterized Complexity, vol.\u00a04. Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (2012)","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"6","key":"18_CR17","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 behavior. Am. J. Sociol. 83(6), 1420\u20131443 (1978)","journal-title":"Am. J. Sociol."},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.1007\/11523468_91","volume-title":"Automata, Languages and Programming","author":"D Kempe","year":"2005","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Influential nodes in a diffusion model for social networks. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1127\u20131138. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11523468_91"},{"key":"18_CR19","doi-asserted-by":"publisher","first-page":"105","DOI":"10.4086\/toc.2015.v011a004","volume":"11","author":"D Kempe","year":"2015","unstructured":"Kempe, D., Kleinberg, J.M., Tardos, \u00c9.: Maximizing the spread of influence through a social network. Theory Comput. 11, 105\u2013147 (2015)","journal-title":"Theory Comput."},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Khanna, S., Lucier, B.: Influence maximization in undirected networks. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1482\u20131496. SIAM (2014)","DOI":"10.1137\/1.9781611973402.109"},{"key":"18_CR21","doi-asserted-by":"crossref","unstructured":"Lerman, K., Ghosh, R.: Information contagion: an empirical study of the spread of news on Digg and Twitter social networks. In: Proceedings of the International AAAI Conference on Web and Social Media, vol. 4, no. 1, pp. 90\u201397 (2010)","DOI":"10.1609\/icwsm.v4i1.14021"},{"issue":"6","key":"18_CR22","doi-asserted-by":"publisher","first-page":"2176","DOI":"10.1137\/080714452","volume":"39","author":"E Mossel","year":"2010","unstructured":"Mossel, E., Roch, S.: Submodularity of influence in social networks: from local to global. SIAM J. Comput. 39(6), 2176\u20132188 (2010)","journal-title":"SIAM J. Comput."},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s13278-012-0067-7","volume":"3","author":"A Nichterlein","year":"2013","unstructured":"Nichterlein, A., Niedermeier, R., Uhlmann, J., Weller, M.: On tractable cases of target set selection. Soc. Netw. Anal. Min. 3, 233\u2013256 (2013)","journal-title":"Soc. Netw. Anal. Min."},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms, vol.\u00a031. OUP Oxford (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.003.0004"},{"issue":"6","key":"18_CR25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.63.066117","volume":"63","author":"R Pastor-Satorras","year":"2001","unstructured":"Pastor-Satorras, R., Vespignani, A.: Epidemic dynamics and endemic states in complex networks. Phys. Rev. E 63(6), 066117 (2001)","journal-title":"Phys. Rev. E"},{"key":"18_CR26","doi-asserted-by":"crossref","unstructured":"Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing. In: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 61\u201370 (2002)","DOI":"10.1145\/775047.775057"},{"key":"18_CR27","doi-asserted-by":"crossref","unstructured":"Rigobon, R.: Contagion: how to measure it? In: Preventing Currency Crises in Emerging Markets, pp. 269\u2013334. NBER Chapters, National Bureau of Economic Research, Inc (2002)","DOI":"10.7208\/chicago\/9780226185057.003.0007"},{"issue":"3","key":"18_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3313904","volume":"11","author":"G Schoenebeck","year":"2019","unstructured":"Schoenebeck, G., Tao, B.: Beyond worst-case (in) approximability of nonsubmodular influence maximization. ACM Trans. Comput. Theory (TOCT) 11(3), 1\u201356 (2019)","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G., Tao, B.: Influence maximization on undirected graphs: toward closing the $$(1-1\/e)$$ gap. ACM Trans. Econ. Comput. (TEAC) 8(4), 1\u201336 (2020)","DOI":"10.1145\/3417748"},{"key":"18_CR30","unstructured":"Schoenebeck, G., Tao, B., Yu, F.Y.: Limitations of greed: influence maximization in undirected networks re-visited. In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1224\u20131232 (2020)"},{"key":"18_CR31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2022.104919","volume":"285","author":"G Schoenebeck","year":"2022","unstructured":"Schoenebeck, G., Tao, B., Yu, F.Y.: Think globally, act locally: on the optimal seeding for nonsubmodular influence maximization. Inf. Comput. 285, 104919 (2022)","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-0218-9_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T12:41:50Z","timestamp":1757335310000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-0218-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,3]]},"ISBN":["9789819502172","9789819502189"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-0218-9_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,8,3]]},"assertion":[{"value":"3 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/cocoon2025\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}