{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T04:04:10Z","timestamp":1747541050424,"version":"3.40.5"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031929311","type":"print"},{"value":"9783031929328","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-92932-8_10","type":"book-chapter","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:18Z","timestamp":1747468038000},"page":"136-152","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Computational Complexity of\u00a0Graph Reconstruction"],"prefix":"10.1007","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Morgan","family":"Chopin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Camille","family":"Richer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,18]]},"reference":[{"issue":"3","key":"10_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-Z","volume":"73","author":"KA Abrahamson","year":"1995","unstructured":"Abrahamson, K.A., Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogues. Ann. Pure Appl. Logic 73(3), 235\u2013276 (1995)","journal-title":"Ann. Pure Appl. Logic"},{"key":"10_CR2","doi-asserted-by":"publisher","unstructured":"Abrahao, B.D., Chierichetti, F., Kleinberg, R., Panconesi, A.: Trace complexity of network inference. In: The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, pp. 491\u2013499. ACM (2013). https:\/\/doi.org\/10.1145\/2487575.2487664","DOI":"10.1145\/2487575.2487664"},{"issue":"2","key":"10_CR3","doi-asserted-by":"publisher","first-page":"135","DOI":"10.3233\/COM-140030","volume":"3","author":"C Bazgan","year":"2014","unstructured":"Bazgan, C., Chopin, M., Nichterlein, A., Sikora, F.: Parameterized inapproximability of target set selection and generalizations. Computability 3(2), 135\u2013145 (2014). https:\/\/doi.org\/10.3233\/COM-140030","journal-title":"Computability"},{"issue":"12","key":"10_CR4","doi-asserted-by":"publisher","first-page":"2168","DOI":"10.1109\/JSAC.2006.884015","volume":"24","author":"Z Beerliova","year":"2006","unstructured":"Beerliova, Z., et al.: Network discovery and verification. IEEE J. Sel. Areas Commun. 24(12), 2168\u20132181 (2006)","journal-title":"IEEE J. Sel. Areas Commun."},{"issue":"1","key":"10_CR5","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. Disc. Optim. 8(1), 87\u201396 (2011). https:\/\/doi.org\/10.1016\/j.disopt.2010.09.007","journal-title":"Disc. Optim."},{"issue":"3","key":"10_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. Disc. Math. 23(3), 1400\u20131415 (2009)","journal-title":"SIAM J. Disc. Math."},{"issue":"1","key":"10_CR7","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s00224-013-9499-3","volume":"55","author":"M Chopin","year":"2013","unstructured":"Chopin, M., Nichterlein, A., Niedermeier, R., Weller, M.: Constant thresholds can make target set selection tractable. Theory Comput. Syst. 55(1), 61\u201383 (2013). https:\/\/doi.org\/10.1007\/s00224-013-9499-3","journal-title":"Theory Comput. Syst."},{"key":"10_CR8","unstructured":"Daneshmand, H., Gomez-Rodriguez, M., Song, L., Sch\u00f6lkopf, B.: Estimating diffusion network structures: recovery conditions, sample complexity & soft-thresholding algorithm. In: Proceedings of the 31th International Conference on Machine Learning, ICML 2014. JMLR Workshop and Conference Proceedings, vol.\u00a032, pp. 793\u2013801. JMLR.org (2014). http:\/\/proceedings.mlr.press\/v32\/daneshmand14.html"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Heidelberg (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"1","key":"10_CR10","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1137\/20m1337624","volume":"36","author":"P Dvor\u00e1k","year":"2022","unstructured":"Dvor\u00e1k, P., Knop, D., Toufar, T.: Target set selection in dense graph classes. SIAM J. Disc. Math. 36(1), 536\u2013572 (2022). https:\/\/doi.org\/10.1137\/20m1337624","journal-title":"SIAM J. Disc. Math."},{"key":"10_CR11","doi-asserted-by":"publisher","unstructured":"Easley, D.A., Kleinberg, J.M.: Networks, Crowds, and Markets - Reasoning About a Highly Connected World. Cambridge University Press,Cambridge (2010). https:\/\/doi.org\/10.1017\/CBO9780511761942. http:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item2705443\/?site_locale=en_GB","DOI":"10.1017\/CBO9780511761942"},{"key":"10_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"4","key":"10_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2086737.2086741","volume":"5","author":"M Gomez-Rodriguez","year":"2012","unstructured":"Gomez-Rodriguez, M., Leskovec, J., Krause, A.: Inferring networks of diffusion and influence. ACM Trans. Knowl. Disc. Data (TKDD) 5(4), 1\u201337 (2012)","journal-title":"ACM Trans. Knowl. Disc. Data (TKDD)"},{"key":"10_CR14","unstructured":"Hoffmann, J., Basu, S., Goel, S., Caramanis, C.: Learning mixtures of graphs from epidemic cascades. In: III, H.D., Singh, A. (eds.) Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol.\u00a0119, pp. 4342\u20134352. PMLR (2020). https:\/\/proceedings.mlr.press\/v119\/hoffmann20a.html"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Kannan, S., Mathieu, C., Zhou, H.: Graph reconstruction and verification. ACM Trans. Algor. 14(4) (2018)","DOI":"10.1145\/3199606"},{"key":"10_CR16","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). https:\/\/doi.org\/10.4086\/toc.2015.v011a004","journal-title":"Theory Comput."},{"issue":"4","key":"10_CR17","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"10_CR18","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1145\/2318857.2254783","volume":"40","author":"P Netrapalli","year":"2012","unstructured":"Netrapalli, P., Sanghavi, S.: Learning the graph of epidemic cascades. SIGMETRICS Perform. Eval. Rev. 40(1), 211\u2013222 (2012). https:\/\/doi.org\/10.1145\/2318857.2254783","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"10_CR19","doi-asserted-by":"publisher","unstructured":"Newman, M.: Networks: An Introduction. Oxford University Press, Oxford (2010). https:\/\/doi.org\/10.1093\/ACPROF:OSO\/9780199206650.001.0001","DOI":"10.1093\/ACPROF:OSO\/9780199206650.001.0001"},{"issue":"2","key":"10_CR20","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(2), 233\u2013256 (2013). https:\/\/doi.org\/10.1007\/s13278-012-0067-7","journal-title":"Soc. Netw. Anal. Min."},{"key":"10_CR21","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0304-3975(01)00055-X","volume":"282","author":"D Peleg","year":"2002","unstructured":"Peleg, D.: Local majorities, coalitions and monopolies in graphs: a review. Theor. Comput. Sci. 282, 231\u2013257 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR22","unstructured":"Pouget-Abadie, J., Horel, T.: Inferring graphs from cascades: a sparse recovery framework. In: Bach, F.R., Blei, D.M. (eds.) Proceedings of the 32nd International Conference on Machine Learning, ICML 2015. JMLR Workshop and Conference Proceedings, vol.\u00a037, pp. 977\u2013986. JMLR.org (2015). http:\/\/proceedings.mlr.press\/v37\/pouget-abadie15.html"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-92932-8_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:21Z","timestamp":1747468041000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-92932-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031929311","9783031929328"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-92932-8_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"18 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","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":"10 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/easyconferences.eu\/ciac2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}