{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,15]],"date-time":"2026-02-15T03:27:44Z","timestamp":1771126064101,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2018,3,26]],"date-time":"2018-03-26T00:00:00Z","timestamp":1522022400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00224-018-9858-1","type":"journal-article","created":{"date-parts":[[2018,3,26]],"date-time":"2018-03-26T00:41:15Z","timestamp":1522024875000},"page":"1910-1951","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Polynomial Kernels for Vertex Cover Parameterized by Small Degree Modulators"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2677-4648","authenticated-orcid":false,"given":"Diptapriyo","family":"Majumdar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,26]]},"reference":[{"issue":"7","key":"9858_CR1","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci. 76(7), 524\u2013531 (2010)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9858_CR2","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Bart, M.P.: Jansen, and Stefan Kratsch. Kernelization Lower Bounds by Cross-Composition. SIAM J. Discret. Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discret. Math."},{"key":"9858_CR3","unstructured":"Bougeret, M., Sau, I.: How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? Proceedings of IPEC 2017, arXiv: 1609.08095 (2017)"},{"issue":"3","key":"9858_CR4","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discret. Appl. Math. 127(3), 415\u2013429 (2003)","journal-title":"Discret. Appl. Math."},{"issue":"40-42","key":"9858_CR5","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Ge, X.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40-42), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9858_CR6","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1016\/j.jcss.2013.10.002","volume":"80","author":"R Crowston","year":"2014","unstructured":"Crowston, R., Fellows, M.R., Gutin, G., Jones, M., Kim, E.J., Rosamond, F., Ruzsa, I.Z.: St\u00e9phan Thomass\u00e9, and Anders Yeo. Satisfying more than half of a system of linear equations over GF(2): A multivariate approach. J. Comput. Syst. Sci. 80(4), 687\u2013696 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"9858_CR7","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)"},{"issue":"1","key":"9858_CR8","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00224-013-9480-1","volume":"54","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: On the hardness of losing width. Theory Comput. Syst. 54(1), 73\u201382 (2014)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"9858_CR9","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses. J. ACM 61(4), 23:1\u201323:27 (2014)","journal-title":"J. ACM"},{"key":"9858_CR10","volume-title":"Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, Berlin (2012)"},{"key":"9858_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity Texts in Computer Science. Springer, Berlin (2013)"},{"key":"9858_CR12","doi-asserted-by":"crossref","unstructured":"Etscheid, M., Mnich, M.: Linear Kernels and Linear-Time Algorithms for Finding Large Cuts. Algorithmica (2017)","DOI":"10.1007\/s00453-017-0388-z"},{"issue":"3","key":"9858_CR13","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"MR Fellows","year":"2013","unstructured":"Fellows, M.R., Jansen, B.M.P., Rosamond, F.A.: Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3), 541\u2013566 (2013)","journal-title":"Eur. J. Comb."},{"issue":"4","key":"9858_CR14","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1007\/s00224-009-9167-9","volume":"45","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F.A., Saket, S.: The complexity ecology of parameters: an illustration using bounded max leaf number. Theory Comput. Syst. 45(4), 822\u2013848 (2009)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9858_CR15","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1137\/140997889","volume":"30","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Philip, G., Saket, S.: Hitting forbidden minors: approximation and kernelization. SIAM J. Discret. Math. 30(1), 383\u2013410 (2016)","journal-title":"SIAM J. Discret. Math."},{"key":"9858_CR16","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Str\u00f8mme, T.J.F.: Vertex Cover Structural Parameterization Revisited. CoRR, arXiv: 1508.00395 (2016)","DOI":"10.1007\/978-3-662-53536-3_15"},{"key":"9858_CR17","doi-asserted-by":"crossref","unstructured":"Fomin, Fedor V., Str\u00f8mme, T. J. F.: Vertex Cover Structural Parameterization Revisited. In: Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Istanbul, Revised Selected Papers, pp. 171\u2013182 (2016)","DOI":"10.1007\/978-3-662-53536-3_15"},{"issue":"1","key":"9858_CR18","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/BF02591727","volume":"29","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Nemhauser, G.L.: A polynomial algorithm for the max-cut problem on graphs without long odd cycles. Math. Programm. 29(1), 28\u201340 (1984)","journal-title":"Math. Programm."},{"issue":"2","key":"9858_CR19","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/j.jcss.2010.06.001","volume":"77","author":"G Gutin","year":"2011","unstructured":"Gutin, G., Kim, E.J., Szeider, S., Anders, Y.: A probabilistic approach to problems parameterized above or below tight bounds. J. Comput. Syst. Sci. 77(2), 422\u2013429 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9858_CR20","doi-asserted-by":"crossref","unstructured":"Gutin, G., Yeo, A.: Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey. In: The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, volume 7370 of Lecture Notes in Computer Science, pp. 257\u2013286. Springer (2012)","DOI":"10.1007\/978-3-642-30891-8_14"},{"key":"9858_CR21","unstructured":"Hols, E.C., Kratsch, S.: Smaller parameters for vertex cover kernelization. Proceedings of IPEC 2017, arXiv: 1711.04604 (2017)"},{"issue":"2","key":"9858_CR22","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF01589347","volume":"20","author":"WL Hsu","year":"1981","unstructured":"Hsu, W.L., Ikura, Y., Nemhauser, G.L.: A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles. Math. Programm. 20 (2), 225\u2013232 (1981)","journal-title":"Math. Programm."},{"issue":"2","key":"9858_CR23","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00224-012-9393-4","volume":"53","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P., Bodlaender, H.L.: Vertex cover kernelization revisited - upper and lower bounds for a refined parameter. Theory Comput. Syst. 53(2), 263\u2013299 (2013)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9858_CR24","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-016-0189-9","volume":"79","author":"BMP Jansen","year":"2017","unstructured":"Jansen, B.M.P., Pieterse, A.: Sparsification upper and lower bounds for graph problems and not-all-equal SAT. Algorithmica 79(1), 3\u201328 (2017)","journal-title":"Algorithmica"},{"key":"9858_CR25","doi-asserted-by":"crossref","unstructured":"Kim, E.J., Williams, R.: Improved parameterized algorithms for above average constraint satisfaction. In: Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbru\u0307cken, Revised Selected Papers, pp. 118\u2013131 (2011)","DOI":"10.1007\/978-3-642-28050-4_10"},{"key":"9858_CR26","unstructured":"Kratsch, Stefan: A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. In: 24th Annual European Symposium on Algorithms, ESA 2016, Aarhus, Denmark, pp, 59:1\u201359:17 (2016)"},{"key":"9858_CR27","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstro\u0307m, M.: Representative Sets and Irrelevant Vertices: New Tools for Kernelization. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, pp. 450\u2013459 (2012)","DOI":"10.1109\/FOCS.2012.46"},{"issue":"2","key":"9858_CR28","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/2566616","volume":"11","author":"D Lokshtanov","year":"2014","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithm. 11(2), 15:1\u201315:31 (2014)","journal-title":"ACM Trans. Algorithm."},{"key":"9858_CR29","unstructured":"Majumdar, D., Raman, V., Saurabh, S.: Kernels for Structural Parameterization of Vertex Cover: case of small degree modulators. In: 10th International Symposium on Parameterized and Exact Computation (IPEC), volume LIPICS: Leibniz International Proceedings in Informatics (43), pp. 331\u2013342 (2015)"},{"key":"9858_CR30","doi-asserted-by":"crossref","unstructured":"Nemhauser, G.L., Trotter, Jr., L.E.: Vertex Packings: Structural properties and Algorithms. Math. Program. 8(1), 232\u2013248 (1975)","DOI":"10.1007\/BF01580444"},{"key":"9858_CR31","doi-asserted-by":"crossref","unstructured":"Panolan, F., Rai, A.: On the Kernelization Complexity of Problems on Graphs without Long Odd Cycles. In: COCOON 2012, volume 7434 of LNCS, pp. 445\u2013457. Springer (2012)","DOI":"10.1007\/978-3-642-32241-9_38"},{"key":"9858_CR32","volume-title":"Systematic Kernelization in FPT Algorithm Design","author":"E Prieto","year":"2005","unstructured":"Prieto, E.: Systematic Kernelization in FPT Algorithm Design. PhD thesis, The University of Newcastle, Australia (2005)"},{"key":"9858_CR33","unstructured":"Sipser, M.: Introduction to the Theory of Computation PWS. Publishing Company (1997)"},{"key":"9858_CR34","volume-title":"Kernelization of Vertex Cover by Structural Parameters","author":"TJF Str\u00f8mme","year":"2015","unstructured":"Str\u00f8mme, T.J. F.: Kernelization of Vertex Cover by Structural Parameters. Master\u2019s thesis, University of Bergen, Norway (2015)"},{"key":"9858_CR35","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A 4k2 kernel for feedback vertex set. ACM Trans. Algorithm. 6(2) (2010)","DOI":"10.1145\/1721837.1721848"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9858-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9858-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9858-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,13]],"date-time":"2019-10-13T08:15:38Z","timestamp":1570954538000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9858-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,26]]},"references-count":35,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["9858"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9858-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,26]]},"assertion":[{"value":"26 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}