{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:51:00Z","timestamp":1780822260001,"version":"3.54.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,8,19]],"date-time":"2020-08-19T00:00:00Z","timestamp":1597795200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,19]],"date-time":"2020-08-19T00:00:00Z","timestamp":1597795200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"FWF","award":["P31336"],"award-info":[{"award-number":["P31336"]}]},{"DOI":"10.13039\/501100000858","name":"University of Sheffield","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000858","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below a given degree bound. Our focus lies on parameters that measure the structural properties of the input instance. We first show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treedepth, and even the size of a minimum vertex deletion set into graphs of pathwidth and treedepth at most three. We thereby resolve an open question stated in Betzler, Bredereck, Niedermeier and Uhlmann\u00a0(2012) concerning the complexity of BDD parameterized by the feedback vertex set number. On the positive side, we obtain fixed-parameter algorithms for the problem with respect to the decompositional parameter treecut width and a novel problem-specific parameter called the core fracture number.<\/jats:p>","DOI":"10.1007\/s00453-020-00758-8","type":"journal-article","created":{"date-parts":[[2020,8,19]],"date-time":"2020-08-19T07:06:23Z","timestamp":1597820783000},"page":"297-336","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem"],"prefix":"10.1007","volume":"83","author":[{"given":"Robert","family":"Ganian","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Klute","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1935-651X","authenticated-orcid":false,"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,8,19]]},"reference":[{"key":"758_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05412-3","volume-title":"Proofs from the Book","author":"M Aigner","year":"2004","unstructured":"Aigner, M., Ziegler, G.M.: Proofs from the Book, 3rd edn. Springer, Berlin (2004)","edition":"3"},{"issue":"7","key":"758_CR2","doi-asserted-by":"publisher","first-page":"1311","DOI":"10.1016\/j.jcss.2015.04.002","volume":"81","author":"C B\u00e4ckstr\u00f6m","year":"2015","unstructured":"B\u00e4ckstr\u00f6m, C., Jonsson, P., Ordyniak, S., Szeider, S.: A complete parameterized complexity analysis of bounded planning. J. Comput. Syst. Sci. 81(7), 1311\u20131332 (2015)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"758_CR3","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1287\/opre.1100.0851","volume":"59","author":"B Balasundaram","year":"2011","unstructured":"Balasundaram, B., Butenko, S., Hicks, I.V.: Clique relaxations in social network analysis: the maximum k-plex problem. Oper. Res. 59(1), 133\u2013142 (2011)","journal-title":"Oper. Res."},{"issue":"3","key":"758_CR4","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s11590-009-0146-5","volume":"4","author":"B Balasundaram","year":"2010","unstructured":"Balasundaram, B., Chandramouli, S.S., Trukhanov, S.: Approximation algorithms for finding and partitioning unit-disk graphs into co-$$k$$-plexes. Optim. Lett. 4(3), 311\u2013320 (2010)","journal-title":"Optim. Lett."},{"issue":"3","key":"758_CR5","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/s00453-012-9695-6","volume":"68","author":"N Betzler","year":"2014","unstructured":"Betzler, N., Bodlaender, H.L., Bredereck, R., Niedermeier, R., Uhlmann, J.: On making a distinguished vertex of minimum degree by vertex deletion. Algorithmica 68(3), 715\u2013738 (2014)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"758_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.dam.2011.08.013","volume":"160","author":"N Betzler","year":"2012","unstructured":"Betzler, N., Bredereck, R., Niedermeier, R., Uhlmann, J.: On bounded-degree vertex deletion parameterized by treewidth. Discrete Appl. Math. 160(1\u20132), 53\u201360 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"52","key":"758_CR7","doi-asserted-by":"publisher","first-page":"5425","DOI":"10.1016\/j.tcs.2009.05.029","volume":"410","author":"N Betzler","year":"2009","unstructured":"Betzler, N., Uhlmann, J.: Parameterized complexity of candidate control in elections and related digraph problems. Theor. Comput. Sci. 410(52), 5425\u20135442 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"758_CR8","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J Discrete Math."},{"issue":"2","key":"758_CR9","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1006\/inco.2000.2958","volume":"167","author":"HL Bodlaender","year":"2001","unstructured":"Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Reduction algorithms for graphs of small treewidth. Inf. Comput. 167(2), 86\u2013119 (2001)","journal-title":"Inf. Comput."},{"key":"758_CR10","doi-asserted-by":"crossref","unstructured":"Chen, Z.Z., Fellows, M.R., Fu, B., Jiang, H., Liu, Y., Wang, L., Zhu, B.: A linear kernel for co-path\/cycle packing. In Proceedings of the AAIM 2010, volume 6124 of LNCS, pp. 90\u2013102. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-14355-7_10"},{"issue":"1","key":"758_CR11","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic secondorder logic of graphs. i. recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"758_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)"},{"key":"758_CR13","doi-asserted-by":"crossref","unstructured":"Dessmark, A., Jansen, K., Lingas, A.: The maximum $$k$$-dependent and $$f$$-dependent set problem. In: Proceedings of the ISAAC 1993, volume 762 of LNCS, pp. 88\u201398. Springer, Berlin (1993)","DOI":"10.1007\/3-540-57568-5_238"},{"key":"758_CR14","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, volume 173 of Graduate Texts in Mathematics. 2nd edition, Springer, New York (2000)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"758_CR15","doi-asserted-by":"crossref","unstructured":"Downey, R. G., Fellows, M. R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"758_CR16","unstructured":"Eduard E., Robert G., Stefan S.: Meta-kernelization using well-structured modulators. In Thore H., Iyad\u00a0A. Kanj, (eds.), Proceedings of the IPEC 2015, volume\u00a043 of LIPIcs, pp. 114\u2013126. Leibniz-Zentrum f\u00fcr Informatik, (2015)"},{"key":"758_CR17","doi-asserted-by":"crossref","unstructured":"Eiben, E., Ganian, R., Szeider, S.: Solving problems on graphs of high rank-width. In Proceedings of the WADS 2015, volume 9214 of LNCS, pp. 314\u2013326. Springer, Berlin (2015)","DOI":"10.1007\/978-3-319-21840-3_26"},{"issue":"4","key":"758_CR18","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1112\/jlms\/s1-16.4.212","volume":"1","author":"P Erd\u0151s","year":"1941","unstructured":"Erd\u0151s, P., Tur\u00e1n, P.: On a problem of Sidon in additive number theory, and on some related problems. J. Lond. Math. Soc. 1(4), 212\u2013215 (1941)","journal-title":"J. Lond. Math. Soc."},{"issue":"6","key":"758_CR19","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1016\/j.jcss.2010.12.001","volume":"77","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Guo, J., Moser, H., Niedermeier, R.: A generalization of Nemhauser and Trotter\u2019s local optimization theorem. J. Comput. Syst. Sci. 77(6), 1141\u20131158 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"758_CR20","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.\u00a0A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In ISAAC, Lecture Notes in Computer Science, pp. 294\u2013305. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-92182-0_28"},{"issue":"1","key":"758_CR21","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49\u201365 (1987)","journal-title":"Combinatorica"},{"issue":"1","key":"758_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(03)00274-1","volume":"155","author":"A Fr\u00e9ville","year":"2004","unstructured":"Fr\u00e9ville, A.: The multidimensional 0\u20131 knapsack problem: an overview. Eur. J. Oper. Res. 155(1), 1\u201321 (2004)","journal-title":"Eur. J. Oper. Res."},{"key":"758_CR23","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.jcss.2016.09.002","volume":"84","author":"J Gajarsk\u00fd","year":"2017","unstructured":"Gajarsk\u00fd, J., Hlinen\u00fd, P., Obdrz\u00e1lek, J., Ordyniak, S., Reidl, F., Rossmanith, P., Villaamil, F.S., Sikdar, S.: Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci. 84, 219\u2013242 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"758_CR24","doi-asserted-by":"crossref","unstructured":"Ganian, Robert, Kim, Eun\u00a0Jung, Szeider, Stefan: Algorithmic applications of tree-cut width. In Giuseppe\u00a0F. Italiano, G. P., Donald S. (eds.). Proceedings of the MFCS 2015, volume 9235 of LNCS, pp. 348\u2013360. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-48054-0_29"},{"key":"758_CR25","unstructured":"Ganian, R., Klute, F., Ordyniak, S.: On structural parameterizations of the bounded-degree vertex deletion problem. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume\u00a096 of LIPIcs, pages 33:1\u201333:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, (2018)"},{"key":"758_CR26","doi-asserted-by":"crossref","unstructured":"Ganian, R., Lodha, N., Ordyniak, S., Szeider, S.: Sat-encodings for treecut width and treedepth. In Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, USA, January 7-8, 2019, pp. 117\u2013129, (2019)","DOI":"10.1137\/1.9781611975499.10"},{"key":"758_CR27","doi-asserted-by":"crossref","unstructured":"Ganian, R., Ordyniak, S.: The power of cut-based parameters for computing edge disjoint paths. In Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de N\u00faria, Spain, June 19\u201321, 2019, Revised Papers, pp. 190\u2013204, (2019)","DOI":"10.1007\/978-3-030-30786-8_15"},{"issue":"2","key":"758_CR28","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/j.jcss.2015.08.003","volume":"82","author":"R Ganian","year":"2016","unstructured":"Ganian, R., Slivovsky, F., Szeider, S.: Meta-kernelization with structural parameters. J. Comput. Syst. Sci. 82(2), 333\u2013346 (2016)","journal-title":"J. Comput. Syst. Sci."},{"key":"758_CR29","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.jcss.2016.10.007","volume":"85","author":"S Gaspers","year":"2017","unstructured":"Gaspers, S., Misra, N., Ordyniak, S., Szeider, S., Zivny, S.: Backdoors into heterogeneous classes of SAT and CSP. J. Comput. Syst. Sci. 85, 38\u201356 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"758_CR30","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":"3","key":"758_CR31","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."},{"issue":"1","key":"758_CR32","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/s00453-016-0245-5","volume":"80","author":"EJ Kim","year":"2018","unstructured":"Kim, E.J., Oum, S., Paul, C., Sau, I., Thilikos, D.M.: An FPT 2-approximation for tree-cut decomposition. Algorithmica 80(1), 116\u2013135 (2018)","journal-title":"Algorithmica"},{"key":"758_CR33","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth: Computations and Approximations. LNCS, vol. 842. Springer, Berlin (1994)","DOI":"10.1007\/BFb0045375"},{"issue":"38\u201340","key":"758_CR34","doi-asserted-by":"publisher","first-page":"3640","DOI":"10.1016\/j.tcs.2009.04.021","volume":"410","author":"C Komusiewicz","year":"2009","unstructured":"Komusiewicz, C., H\u00fcffner, F., Moser, H., Niedermeier, R.: Isolation concepts for efficiently enumerating dense subgraphs. Theoret. Comput. Sci. 410(38\u201340), 3640\u20133654 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"758_CR35","doi-asserted-by":"crossref","unstructured":"Kronegger, M., Ordyniak, S., Pfandler, A.: Variable-deletion backdoors to planning. In Proceedings of the AAAI 2015, pp. 2300\u20132307. AAAI Press, (2014)","DOI":"10.1609\/aaai.v29i1.9662"},{"issue":"4","key":"758_CR36","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":"758_CR37","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1137\/130924056","volume":"28","author":"D Marx","year":"2014","unstructured":"Marx, D., Wollan, P.: Immersions in highly edge connected graphs. SIAM J. Discrete Math. 28(1), 503\u2013520 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"758_CR38","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10878-010-9338-2","volume":"23","author":"B McClosky","year":"2012","unstructured":"McClosky, B., Hicks, I.V.: Combinatorial algorithms for the maximum $$k$$-plex problem. J. Comb. Optim. 23(1), 29\u201349 (2012)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"758_CR39","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s10878-011-9391-5","volume":"24","author":"H Moser","year":"2012","unstructured":"Moser, H., Niedermeier, R., Sorge, M.: Exact combinatorial algorithms and experiments for finding maximum $$k$$-plexes. J. Comb. Optim. 24(3), 347\u2013373 (2012)","journal-title":"J. Comb. Optim."},{"key":"758_CR40","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., de\u00a0Mendez, P.\u00a0O.: Sparsity-graphs, Structures, and Algorithms, volume\u00a028 of Algorithms and combinatorics. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"key":"758_CR41","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter. Algorithms Oxford Lecture Series in Mathematics and its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter. Algorithms Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2006)"},{"issue":"1\u20133","key":"758_CR42","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/j.dam.2005.02.029","volume":"152","author":"N Nishimura","year":"2005","unstructured":"Nishimura, N., Ragde, P., Thilikos, D.M.: Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover. Discrete Appl. Math. 152(1\u20133), 229\u2013245 (2005)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"758_CR43","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"758_CR44","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1080\/0022250X.1978.9989883","volume":"6","author":"SB Seidman","year":"1978","unstructured":"Seidman, S.B., Foster, B.L.: A graph-theoretic generalization of the clique concept. J. Math. Sociol. 6(1), 139\u2013154 (1978)","journal-title":"J. Math. Sociol."},{"key":"758_CR45","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.jctb.2014.07.003","volume":"110","author":"P Wollan","year":"2015","unstructured":"Wollan, P.: The structure of graphs not admitting a fixed immersion. J. Comb. Theory Ser. B 110, 47\u201366 (2015)","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00758-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00758-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00758-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T17:24:12Z","timestamp":1667928252000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00758-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,19]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["758"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00758-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,19]]},"assertion":[{"value":"8 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}