{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T16:25:24Z","timestamp":1761582324696,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,1,9]],"date-time":"2024-01-09T00:00:00Z","timestamp":1704758400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,9]],"date-time":"2024-01-09T00:00:00Z","timestamp":1704758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100004541","name":"Ministry of Education, India","doi-asserted-by":"publisher","award":["Prime Minister\u2019s Research Fellowship Scheme (No. MRF-192002-211)"],"award-info":[{"award-number":["Prime Minister\u2019s Research Fellowship Scheme (No. MRF-192002-211)"]}],"id":[{"id":"10.13039\/501100004541","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,5]]},"DOI":"10.1007\/s00453-023-01199-9","type":"journal-article","created":{"date-parts":[[2024,1,9]],"date-time":"2024-01-09T06:02:33Z","timestamp":1704780153000},"page":"1475-1511","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Structural Parameterizations of the Harmless Set Problem"],"prefix":"10.1007","volume":"86","author":[{"given":"Ajinkya","family":"Gaikwad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Soumen","family":"Maity","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,9]]},"reference":[{"issue":"3","key":"1199_CR1","doi-asserted-by":"publisher","first-page":"1382","DOI":"10.1137\/06066672X","volume":"23","author":"A Aazami","year":"2009","unstructured":"Aazami, A., Stilp, K.: Approximation algorithms and hardness for domination with propagation. SIAM J. Discrete Math. 23(3), 1382\u20131399 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"1199_CR2","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/0166-218X(92)90122-Q","volume":"37\u201338","author":"K Bagga","year":"1992","unstructured":"Bagga, K., Beineke, L., Goddard, W., Lipman, M., Pippert, R.: A survey of integrity. Discrete Appl. Math. 37\u201338, 13\u201328 (1992)","journal-title":"Discrete Appl. Math."},{"issue":"38","key":"1199_CR3","first-page":"13","volume":"1","author":"CA Barefoot","year":"1987","unstructured":"Barefoot, C.A., Entringer, R., Swart, H.C.: Vulnerability in graphs\u2014a comparative survey. J. Combin. Math. Combin. Comput. 1(38), 13\u201322 (1987)","journal-title":"J. Combin. Math. Combin. Comput."},{"issue":"C","key":"1199_CR4","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.disopt.2014.09.004","volume":"14","author":"C Bazgan","year":"2014","unstructured":"Bazgan, C., Chopin, M.: The complexity of finding harmless individuals in social networks. Discrete Optim. 14(C), 170\u2013182 (2014)","journal-title":"Discrete Optim."},{"key":"1199_CR5","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1007\/978-3-642-38768-5_48","volume-title":"Computing and Combinatorics","author":"C Bazgan","year":"2013","unstructured":"Bazgan, C., Chopin, M., Nichterlein, A., Sikora, F.: Parameterized approximability of maximizing the spread of influence in networks. In: Du, D.-Z., Zhang, G. (eds.) Computing and Combinatorics, pp. 543\u2013554. Springer, Berlin (2013)"},{"issue":"1","key":"1199_CR6","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. Discrete Optim. 8(1), 87\u201396 (2011). (Parameterized Complexity of Discrete Optimization)","journal-title":"Discrete Optim."},{"issue":"29","key":"1199_CR7","doi-asserted-by":"publisher","first-page":"3693","DOI":"10.1016\/j.tcs.2011.03.029","volume":"412","author":"CC Centeno","year":"2011","unstructured":"Centeno, C.C., Dourado, M.C., Penso, L.D., Rautenbach, D., Szwarcfiter, J.L.: Irreversible conversion of graphs. Theoret. Comput. Sci. 412(29), 3693\u20133700 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"1199_CR8","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. Discrete Math. 23(3), 1400\u20131415 (2009)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"1199_CR9","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1007\/s10878-012-9518-3","volume":"25","author":"C-Y Chiang","year":"2013","unstructured":"Chiang, C.-Y., Huang, L.-H., Li, B.-J., Wu, J., Yeh, H.-G.: Some results on the target set selection problem. J. Combin. Optim. 25(4), 702\u2013715 (2013)","journal-title":"J. Combin. Optim."},{"issue":"1","key":"1199_CR10","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(1), 61\u201383 (2014)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"1199_CR11","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"1199_CR12","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)"},{"doi-asserted-by":"crossref","unstructured":"Doucha, M., Kratochv\u00edl, J.: Cluster vertex deletion: a parameterization between vertex cover and clique-width. In: Proceedings of the 37th International Conference on Mathematical Foundations of Computer Science, MFCS\u201912, pp. 348\u2013359. Springer, Berlin (2012)","key":"1199_CR13","DOI":"10.1007\/978-3-642-32589-2_32"},{"key":"1199_CR14","volume-title":"Parameterized Complexity","author":"RG Downey","year":"2012","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (2012)"},{"doi-asserted-by":"crossref","unstructured":"Drange, P.G., Dregi, M., van\u00a0\u2019t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. Algorithmica 76(4), 1181\u20131202 (2016)","key":"1199_CR15","DOI":"10.1007\/s00453-016-0127-x"},{"key":"1199_CR16","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-031-06678-8_22","volume-title":"Combinatorial Algorithms","author":"PG Drange","year":"2022","unstructured":"Drange, P.G., Muzi, I., Reidl, F.: Harmless sets in sparse classes. In: Bazgan, C., Fernau, H. (eds.) Combinatorial Algorithms, pp. 299\u2013312. Springer, Cham (2022)"},{"issue":"7","key":"1199_CR17","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1016\/j.dam.2008.09.012","volume":"157","author":"PA Dreyer","year":"2009","unstructured":"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(7), 1615\u20131627 (2009)","journal-title":"Discrete Appl. Math."},{"key":"1199_CR18","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-92182-0_28","volume-title":"Algorithms and Computation","author":"MR Fellows","year":"2008","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) Algorithms and Computation, pp. 294\u2013305. Springer, Berlin (2008)"},{"key":"1199_CR19","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-030-96731-4_19","volume-title":"WALCOM: Algorithms and Computation","author":"A Gaikwad","year":"2022","unstructured":"Gaikwad, A., Maity, S.: On the harmless set problem parameterized by treewidth. In: Mutzel, P., Rahman, M.S., Slamin (eds.) WALCOM: Algorithms and Computation, pp. 227\u2013238. Springer, Cham (2022)"},{"doi-asserted-by":"crossref","unstructured":"Ganian, R.: Improving vertex cover as a graph parameter. Discrete Math. Theor. Comput. Sci. 17(2) (2015)","key":"1199_CR20","DOI":"10.46298\/dmtcs.2136"},{"doi-asserted-by":"crossref","unstructured":"Ganian, R., Klute, F., Ordyniak, S.: On structural parameterizations of the bounded-degree vertex deletion problem. Algorithmica (2020)","key":"1199_CR21","DOI":"10.1007\/s00453-020-00758-8"},{"key":"1199_CR22","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-030-75242-2_19","volume-title":"Algorithms and Complexity","author":"T Gima","year":"2021","unstructured":"Gima, T., Hanaka, T., Kiyomi, M., Kobayashi, Y., Otachi, Y.: Exploring the gap between treedepth and vertex cover through vertex integrity. In: Calamoneri, T., Cor\u00f2, F. (eds.) Algorithms and Complexity, pp. 271\u2013285. Springer, Cham (2021)"},{"issue":"4","key":"1199_CR23","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"12","key":"1199_CR24","doi-asserted-by":"publisher","first-page":"2747","DOI":"10.1016\/j.dam.2008.08.022","volume":"157","author":"M Kami\u0144ski","year":"2009","unstructured":"Kami\u0144ski, M., Lozin, V.V., Milani\u010d, M.: Recent developments on graphs of bounded clique-width. Discrete Appl. Math. 157(12), 2747\u20132761 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"1199_CR25","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD \u201903, pp. 137\u2013146. Association for Computing Machinery, New York (2003)","key":"1199_CR26","DOI":"10.1145\/956755.956769"},{"key":"1199_CR27","volume-title":"Treewidth, Computations and Approximations. Lecture Notes in Computer Science","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994)"},{"key":"1199_CR28","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"},{"issue":"4","key":"1199_CR29","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1199_CR30","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201(1), 189\u2013241 (1999)","journal-title":"Discrete Math."},{"key":"1199_CR31","volume-title":"Sparsity: Graphs, Structures, and Algorithms","author":"J Nesetril","year":"2014","unstructured":"Nesetril, J., de Mendez, P.O.: Sparsity: Graphs, Structures, and Algorithms. Springer, Cham (2014)"},{"issue":"2","key":"1199_CR32","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)","journal-title":"Soc. Netw. Anal. Min."},{"issue":"2","key":"1199_CR33","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(2), 231\u2013257 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"1199_CR34","doi-asserted-by":"publisher","first-page":"683","DOI":"10.7155\/jgaa.00244","volume":"15","author":"T Reddy","year":"2011","unstructured":"Reddy, T., Rangan, C.: Variants of spreading messages. J. Graph Algorithms Appl. 15(5), 683\u2013699 (2011)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"1199_CR35","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.: Graph minors. III. Planar tree-width. J. Combin. Theory Ser. B 36(1), 49\u201364 (1984)","journal-title":"J. Combin. Theory Ser. B"},{"unstructured":"Szeider, S.: Not so easy problems for tree decomposable graphs. CoRR. arXiv:1107.1177 (2011)","key":"1199_CR36"},{"doi-asserted-by":"crossref","unstructured":"Tedder, M., Corneil, D., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Automata, Languages and Programming, pp. 634\u2013645. Springer, Berlin (2008)","key":"1199_CR37","DOI":"10.1007\/978-3-540-70575-8_52"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01199-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01199-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01199-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,21]],"date-time":"2024-04-21T03:02:43Z","timestamp":1713668563000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01199-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,9]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1199"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01199-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,1,9]]},"assertion":[{"value":"16 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 January 2024","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 declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The authors declare that the manuscript complies to the Ethical Rules applicable for this journal.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}]}}