{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:33Z","timestamp":1759638213160,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:00:00Z","timestamp":1641600000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:00:00Z","timestamp":1641600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s00453-021-00897-6","type":"journal-article","created":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:03:13Z","timestamp":1641600193000},"page":"405-435","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Parameterized Complexity of Maximum Degree Contraction Problem"],"prefix":"10.1007","volume":"84","author":[{"given":"Saket","family":"Saurabh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prafullkumar","family":"Tale","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,8]]},"reference":[{"issue":"3","key":"897_CR1","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s00224-018-9892-z","volume":"63","author":"A Agarwal","year":"2019","unstructured":"Agarwal, A., Saurabh, S., Tale, P.: On the parameterized complexity of contraction to generalization of trees. Theory Comput. Syst. 63(3), 587\u2013614 (2019)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"897_CR2","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1137\/19M1259638","volume":"34","author":"A Agrawal","year":"2020","unstructured":"Agrawal, A., Fomin, F.V., Lokshtanov, D., Saurabh, S., Tale, P.: Path contraction faster than $$2^{n}$$. SIAM J. Discrete Math. 34(2), 1302\u20131325 (2020)","journal-title":"SIAM J. Discrete Math."},{"key":"897_CR3","doi-asserted-by":"crossref","unstructured":"Agrawal, A., Kanesh, L., Saurabh, S., Tale, P.: Paths to trees and cacti. In: International Conference on Algorithms and Complexity, pp. 31\u201342. Springer (2017)","DOI":"10.1007\/978-3-319-57586-5_4"},{"issue":"3","key":"897_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3319909","volume":"11","author":"A Agrawal","year":"2019","unstructured":"Agrawal, A., Lokshtanov, D., Saurabh, S., Zehavi, M.: Split contraction: the untold story. ACM Transactions Comput. Theory (TOCT) 11(3), 1\u201322 (2019)","journal-title":"ACM Transactions Comput. Theory (TOCT)"},{"issue":"4","key":"897_CR5","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM (JACM) 42(4), 844\u2013856 (1995)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"897_CR6","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(83)90012-0","volume":"26","author":"T Asano","year":"1983","unstructured":"Asano, T., Hirata, T.: Edge-contraction problems. J. Computer Syst. Sci. 26(2), 197\u2013208 (1983)","journal-title":"J. Computer Syst. Sci."},{"issue":"3","key":"897_CR7","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":"7","key":"897_CR8","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/s00236-014-0204-z","volume":"51","author":"R Belmonte","year":"2014","unstructured":"Belmonte, R., Golovach, P.A., Hof, P., Paulusma, D.: Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica 51(7), 473\u2013497 (2014)","journal-title":"Acta Informatica"},{"issue":"1\u20132","key":"897_CR9","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":"2","key":"897_CR10","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. Information Comput. 167(2), 86\u2013119 (2001)","journal-title":"Information Comput."},{"issue":"1","key":"897_CR11","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1002\/jgt.3190110111","volume":"11","author":"AE Brouwer","year":"1987","unstructured":"Brouwer, A.E., Veldman, H.J.: Contractibility and NP-completeness. J. Graph Theory 11(1), 71\u201379 (1987)","journal-title":"J. Graph Theory"},{"key":"897_CR12","doi-asserted-by":"crossref","unstructured":"Cai, L., Guo, C.: Contracting few edges to remove forbidden induced subgraphs. In: International symposium on parameterized and exact computation, pp. 97\u2013109. Springer (2013)","DOI":"10.1007\/978-3-319-03898-8_10"},{"key":"897_CR13","doi-asserted-by":"crossref","unstructured":"Chen, Z.Z., Fellows, M., Fu, B., Jiang, H., Liu, Y., Wang, L., Zhu, B.: A linear kernel for co-path\/cycle packing. In: International Conference on Algorithmic Applications in Management, pp. 90\u2013102. Springer (2010)","DOI":"10.1007\/978-3-642-14355-7_10"},{"key":"897_CR14","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, New York (2015)"},{"key":"897_CR15","doi-asserted-by":"crossref","unstructured":"Dessmark, A., Jansen, K., Lingas, A.: The maximum k-dependent and f-dependent set problem. In: International Symposium on Algorithms and Computation, pp. 88\u201397. Springer (1993)","DOI":"10.1007\/3-540-57568-5_238"},{"key":"897_CR16","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th Edition, Graduate texts in mathematics, vol. 173. Springer (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"897_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized complexity. Springer, Verlag (2013)"},{"issue":"6","key":"897_CR18","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. Computer Syst. Sci. 77(6), 1141\u20131158 (2011)","journal-title":"J. Computer Syst. Sci."},{"key":"897_CR19","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer (2006)"},{"key":"897_CR20","unstructured":"Fomin, F.V., Lokshtanov, D., Mihajlin, I., Saurabh, S., Zehavi, M.: Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 49:1\u201349:18. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"897_CR21","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)"},{"key":"897_CR22","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). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"897_CR23","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.tcs.2012.12.041","volume":"476","author":"PA Golovach","year":"2013","unstructured":"Golovach, P.A., van\u2019t Hof, P., Paulusma, D.: Obtaining planarity by contracting few edges. Theor. Computer Sci. 476, 38\u201346 (2013)","journal-title":"Theor. Computer Sci."},{"key":"897_CR24","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2013.02.030","volume":"481","author":"PA Golovach","year":"2013","unstructured":"Golovach, P.A., Kaminski, M., Paulusma, D., Thilikos, D.M.: Increasing the minimum degree of a graph by contractions. Theor. Computer Sci. 481, 74\u201384 (2013)","journal-title":"Theor. Computer Sci."},{"issue":"22\u201324","key":"897_CR25","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1016\/j.ipl.2013.09.004","volume":"113","author":"S Guillemot","year":"2013","unstructured":"Guillemot, S., Marx, D.: A faster FPT algorithm for bipartite contraction. Information Process. Lett. 113(22\u201324), 906\u2013912 (2013)","journal-title":"Information Process. Lett."},{"key":"897_CR26","doi-asserted-by":"publisher","unstructured":"Gunda, S., Jain, P., Lokshtanov, D., Saurabh, S., Tale, P.: On the parameterized approximability of contraction to classes of chordal graphs. In: J.\u00a0Byrka, R.\u00a0Meka (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2020, August 17-19, 2020, Virtual Conference, LIPIcs, vol. 176, pp. 51:1\u201351:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2020.51","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2020.51"},{"issue":"4","key":"897_CR27","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/3470869","volume":"13","author":"S Gunda","year":"2021","unstructured":"Gunda, S., Jain, P., Lokshtanov, D., Saurabh, S., Tale, P.: On the parameterized approximability of contraction to classes of chordal graphs. ACM Trans. Comput. Theory 13(4), 27\u201340 (2021). https:\/\/doi.org\/10.1145\/3470869","journal-title":"ACM Trans. Comput. Theory"},{"issue":"4","key":"897_CR28","doi-asserted-by":"publisher","first-page":"2143","DOI":"10.1137\/130907392","volume":"27","author":"P Heggernes","year":"2013","unstructured":"Heggernes, P., Hof, P.V., Lokshtanov, D., Paul, C.: Obtaining a bipartite graph by contracting few edges. SIAM J. Discrete Math. 27(4), 2143\u20132156 (2013)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"897_CR29","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s00453-012-9670-2","volume":"68","author":"P Heggernes","year":"2014","unstructured":"Heggernes, P., Van\u2019t Hof, P., L\u00e9v\u00eaque, B., Lokshtanov, D., Paul, C.: Contracting graphs to paths and trees. Algorithmica 68(1), 109\u2013132 (2014)","journal-title":"Algorithmica"},{"issue":"38\u201340","key":"897_CR30","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. Theor. Computer Sci. 410(38\u201340), 3640\u20133654 (2009)","journal-title":"Theor. Computer Sci."},{"key":"897_CR31","unstructured":"Krithika, R., Misra, P., Rai, A., Tale, P.: Lossy kernels for graph contraction problems. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"key":"897_CR32","doi-asserted-by":"crossref","unstructured":"Krithika, R., Misra, P., Tale, P.: An FPT algorithm for contraction to cactus. In: International Computing and Combinatorics Conference, pp. 341\u2013352. Springer (2018)","DOI":"10.1007\/978-3-319-94776-1_29"},{"issue":"3","key":"897_CR33","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/16M1104834","volume":"47","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. SIAM J. Comput. 47(3), 675\u2013702 (2018)","journal-title":"SIAM J. Comput."},{"key":"897_CR34","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: On the hardness of eliminating small induced subgraphs by contracting edges. In: International Symposium on Parameterized and Exact Computation, pp. 243\u2013254. Springer (2013)","DOI":"10.1007\/978-3-319-03898-8_21"},{"key":"897_CR35","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Panolan, F., Ramanujan, M.S., Saurabh, S.: Lossy kernelization. In: H.\u00a0Hatami, P.\u00a0McKenzie, V.\u00a0King (eds.) Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pp. 224\u2013237. ACM (2017). https:\/\/doi.org\/10.1145\/3055399.3055456","DOI":"10.1145\/3055399.3055456"},{"key":"897_CR36","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.jctb.2014.09.002","volume":"111","author":"B Martin","year":"2015","unstructured":"Martin, B., Paulusma, D.: The computational complexity of disconnected cut and 2k2-partition. J. comb. Theory Series B 111, 17\u201337 (2015)","journal-title":"J. comb. Theory Series B"},{"key":"897_CR37","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"issue":"1\u20133","key":"897_CR38","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."},{"key":"897_CR39","unstructured":"Saurabh, S., Souza, U.d.S., Tale, P.: On the parameterized complexity of grid contraction. In: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"897_CR40","unstructured":"Saurabh, S., Souza, U.d.S., Tale, P.: On the parameterized complexity of grid contraction. arXiv preprint arXiv:2008.07967 (2020)"},{"issue":"2","key":"897_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1721837.1721848","volume":"6","author":"S Thomass\u00e9","year":"2010","unstructured":"Thomass\u00e9, S.: A $$4k^2$$ kernel for feedback vertex set. ACM Transactions Algorithms (TALG) 6(2), 1\u20138 (2010)","journal-title":"ACM Transactions Algorithms (TALG)"},{"issue":"2","key":"897_CR42","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0166-218X(81)90039-1","volume":"3","author":"T Watanabe","year":"1981","unstructured":"Watanabe, T., Ae, T., Nakamura, A.: On the removal of forbidden graphs by edge-deletion or by edge-contraction. Discrete Appl. Math. 3(2), 151\u2013153 (1981)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"897_CR43","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0166-218X(83)90101-4","volume":"6","author":"T Watanabe","year":"1983","unstructured":"Watanabe, T., Ae, T., Nakamura, A.: On the np-hardness of edge-deletion and-contraction problems. Discrete Appl. Math. 6(1), 63\u201378 (1983)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00897-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00897-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00897-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T07:05:05Z","timestamp":1644908705000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00897-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,8]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["897"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00897-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,8]]},"assertion":[{"value":"12 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}