{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:32:56Z","timestamp":1767339176513},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,8]]},"DOI":"10.1007\/s00224-012-9393-4","type":"journal-article","created":{"date-parts":[[2012,3,7]],"date-time":"2012-03-07T01:51:10Z","timestamp":1331085070000},"page":"263-299","source":"Crossref","is-referenced-by-count":35,"title":["Vertex Cover Kernelization Revisited"],"prefix":"10.1007","volume":"53","author":[{"given":"Bart M. P.","family":"Jansen","sequence":"first","affiliation":[]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,3,8]]},"reference":[{"key":"9393_CR1","first-page":"62","volume-title":"Proc. 6th ALENEX\/ANALC","author":"F.N. Abu-Khzam","year":"2004","unstructured":"Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem: theory and experiments. In: Proc. 6th ALENEX\/ANALC, pp. 62\u201369 (2004)"},{"issue":"3","key":"9393_CR2","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s00224-007-1328-0","volume":"41","author":"F.N. Abu-Khzam","year":"2007","unstructured":"Abu-Khzam, F.N., Fellows, M.R., Langston, M.A., Suters, W.H.: Crown structures for vertex cover kernelization. Theory Comput. Syst. 41(3), 411\u2013430 (2007). doi: 10.1007\/s00224-007-1328-0","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"9393_CR3","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V. Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. 12(3), 289\u2013297 (1999). doi: 10.1137\/S0895480196305124","journal-title":"SIAM J. Discrete Math."},{"issue":"8","key":"9393_CR4","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009). doi: 10.1016\/j.jcss.2009.04.001","journal-title":"J. Comput. Syst. Sci."},{"key":"9393_CR5","first-page":"165","volume-title":"Proc. 28th STACS","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: a new technique for kernelization lower bounds. In: Proc. 28th STACS, pp. 165\u2013176 (2011). doi: 10.4230\/LIPIcs.STACS.2011.165"},{"key":"9393_CR6","first-page":"437","volume-title":"Proc. 38th ICALP","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Preprocessing for treewidth: a combinatorial analysis through kernelization. In: Proc. 38th ICALP, pp. 437\u2013448 (2011). doi: 10.1007\/978-3-642-22006-7_37"},{"issue":"3","key":"9393_CR7","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J.F. Buss","year":"1993","unstructured":"Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM J. Comput. 22(3), 560\u2013572 (1993). doi: 10.1137\/0222038","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9393_CR8","doi-asserted-by":"crossref","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. Discrete Appl. Math. 127(3), 415\u2013429 (2003). doi: 10.1016\/S0166-218X(02)00242-1","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9393_CR9","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41(2), 280\u2013301 (2001). doi: 10.1006\/jagm.2001.1186","journal-title":"J. Algorithms"},{"issue":"40\u201342","key":"9393_CR10","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J. Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010). doi: 10.1016\/j.tcs.2010.06.026","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9393_CR11","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/j.dam.2007.03.026","volume":"156","author":"M. Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Crown reductions for the minimum weighted vertex cover problem. Discrete Appl. Math. 156(3), 292\u2013312 (2008). doi: 10.1016\/j.dam.2007.03.026","journal-title":"Discrete Appl. Math."},{"key":"9393_CR12","first-page":"257","volume-title":"Proc. 30th WG","author":"B. Chor","year":"2004","unstructured":"Chor, B., Fellows, M., Juedes, D.W.: Linear kernels in linear time, or how to save k colors in O(n 2) steps. In: Proc. 30th WG, pp. 257\u2013269 (2004). doi: 10.1007\/978-3-540-30559-0_22"},{"key":"9393_CR13","volume-title":"Proc. 6th IPEC","author":"M. Cygan","year":"2012","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: On the hardness of losing width. In: Proc. 6th IPEC (2012) (To appear)"},{"key":"9393_CR14","first-page":"147","volume-title":"Proc. 36th WG","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Kernelization hardness of connectivity problems in 2-degenerate graphs. In: Proc. 36th WG, pp. 147\u2013158 (2010). doi: 10.1007\/978-3-642-16926-7_15"},{"key":"9393_CR15","first-page":"251","volume-title":"Proc. 42nd STOC","author":"H. Dell","year":"2010","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Proc. 42nd STOC, pp. 251\u2013260 (2010). doi: 10.1145\/1806689.1806725"},{"key":"9393_CR16","first-page":"231","volume-title":"Proc. 5th WEA","author":"J. D\u00edaz","year":"2006","unstructured":"D\u00edaz, J., Petit, J., Thilikos, D.M.: Kernels for the vertex cover problem on the preferred attachment model. In: Proc. 5th WEA, pp. 231\u2013240 (2006). doi: 10.1007\/11764298_21"},{"key":"9393_CR17","first-page":"378","volume-title":"Proc. 36th ICALP","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Proc. 36th ICALP, pp. 378\u2013389 (2009). doi: 10.1007\/978-3-642-02927-1_32"},{"key":"9393_CR18","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"9393_CR19","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R., Langston, M.A. (eds.): Comput. J.: Special Issue on Parameterized Complexity, 51 (2008)","DOI":"10.1093\/comjnl\/bxm111"},{"key":"9393_CR20","first-page":"49","volume-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"R.G. Downey","year":"1997","unstructured":"Downey, R.G., Fellows, M.R., Stege, U.: Parameterized complexity: a framework for systematically confronting computational intractability. In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 49\u201399 (1997)"},{"key":"9393_CR21","first-page":"1","volume-title":"Proc. 1st ACiD","author":"V. Estivill-Castro","year":"2005","unstructured":"Estivill-Castro, V., Fellows, M., Langston, M., Rosamond, F.: FPT is P-time extremal structure I. In: Proc. 1st ACiD, pp. 1\u201341 (2005)"},{"key":"9393_CR22","first-page":"2","volume-title":"Proc. 20th IWOCA","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R.: Towards fully multivariate algorithmics: some new results and directions in parameter ecology. In: Proc. 20th IWOCA, pp. 2\u201310 (2009). doi: 10.1007\/978-3-642-10217-2_2"},{"issue":"4","key":"9393_CR23","doi-asserted-by":"crossref","first-page":"822","DOI":"10.1007\/s00224-009-9167-9","volume":"45","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F.A., Saurabh, S.: The complexity ecology of parameters: an illustration using bounded max leaf number. Theory Comput. Syst. 45(4), 822\u2013848 (2009). doi: 10.1007\/s00224-009-9167-9","journal-title":"Theory Comput. Syst."},{"key":"9393_CR24","first-page":"294","volume-title":"Proc. 19th ISAAC","author":"M.R. Fellows","year":"2008","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Proc. 19th ISAAC, pp. 294\u2013305 (2008). doi: 10.1007\/978-3-540-92182-0_28"},{"issue":"1","key":"9393_CR25","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L. Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011). doi: 10.1016\/j.jcss.2010.06.007","journal-title":"J. Comput. Syst. Sci."},{"key":"9393_CR26","volume-title":"Computers and Intractability, a Guide to the Theory of NP-Completeness","author":"M.R. 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)"},{"key":"9393_CR27","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1002\/jgt.3190130604","volume":"13","author":"J.R. Griggs","year":"1989","unstructured":"Griggs, J.R., Kleitman, D., Shastri, A.: Spanning trees with many leaves in cubic graphs. J. Graph Theory 13, 669\u2013695 (1989). doi: 10.1002\/jgt.3190130604","journal-title":"J. Graph Theory"},{"issue":"1","key":"9393_CR28","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31\u201345 (2007). doi: 10.1145\/1233481.1233493","journal-title":"SIGACT News"},{"issue":"2","key":"9393_CR29","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1007\/s00224-010-9262-y","volume":"48","author":"G. Gutin","year":"2011","unstructured":"Gutin, G., Kim, E.J., Lampis, M., Mitsou, V.: Vertex cover problem parameterized above and below tight bounds. Theory Comput. Syst. 48(2), 402\u2013410 (2011). doi: 10.1007\/s00224-010-9262-y","journal-title":"Theory Comput. Syst."},{"key":"9393_CR30","first-page":"177","volume-title":"Proc. 28th STACS","author":"B.M.P. Jansen","year":"2011","unstructured":"Jansen, B.M.P., Bodlaender, H.L.: Vertex cover kernelization revisited: upper and lower bounds for a refined parameter. In: Proc. 28th STACS, pp. 177\u2013188 (2011). doi: 10.4230\/LIPIcs.STACS.2011.177"},{"key":"9393_CR31","volume-title":"Proc. 6th IPEC","author":"B.M.P. Jansen","year":"2012","unstructured":"Jansen, B.M.P., Kratsch, S.: On polynomial kernels for structural parameterizations of odd cycle transversal. In: Proc. 6th IPEC (2012) (To appear)"},{"issue":"3","key":"9393_CR32","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S. Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2212\u03f5. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008). doi: 10.1016\/j.jcss.2007.06.019","journal-title":"J. Comput. Syst. Sci."},{"key":"9393_CR33","first-page":"81","volume-title":"Proc. 12th SWAT","author":"S. Kratsch","year":"2010","unstructured":"Kratsch, S., Schweitzer, P.: Isomorphism for graphs of bounded feedback vertex set number. In: Proc. 12th SWAT, pp. 81\u201392 (2010). doi: 10.1007\/978-3-642-13731-0_9"},{"issue":"4","key":"9393_CR34","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1007\/s00453-010-9412-2","volume":"61","author":"S. Mishra","year":"2011","unstructured":"Mishra, S., Raman, V., Saurabh, S., Sikdar, S., Subramanian, C.: The complexity of K\u00f6nig subgraph problems and above-guarantee vertex cover. Algorithmica 61(4), 857\u2013881 (2011). doi: 10.1007\/s00453-010-9412-2","journal-title":"Algorithmica"},{"key":"9393_CR35","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G. Nemhauser","year":"1975","unstructured":"Nemhauser, G., Trotter, L.: Vertex packings: structural properties and algorithms. Math. Program. 8, 232\u2013248 (1975). doi: 10.1007\/BF01580444","journal-title":"Math. Program."},{"key":"9393_CR36","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"9393_CR37","first-page":"17","volume-title":"Proc. 27th STACS","author":"R. Niedermeier","year":"2010","unstructured":"Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: Proc. 27th STACS, pp. 17\u201332 (2010). doi: 10.4230\/LIPIcs.STACS.2010.2495"},{"issue":"2","key":"9393_CR38","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0196-6774(03)00005-1","volume":"47","author":"R. Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for weighted vertex cover. J. Algorithms 47(2), 63\u201377 (2003). doi: 10.1016\/S0196-6774(03)00005-1","journal-title":"J. Algorithms"},{"key":"9393_CR39","first-page":"382","volume-title":"Proc. 19th ESA","author":"V. Raman","year":"2011","unstructured":"Raman, V., Ramanujan, M.S., Saurabh, S.: Paths, flowers and vertex cover. In: Proc. 19th ESA, pp. 382\u2013393 (2011). doi: 10.1007\/978-3-642-23719-5_33"},{"issue":"8","key":"9393_CR40","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I. Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-sat is fixed-parameter tractable. J. Comput. Syst. Sci. 75(8), 435\u2013450 (2009). doi: 10.1016\/j.jcss.2009.04.002","journal-title":"J. Comput. Syst. Sci."},{"key":"9393_CR41","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Springer, Berlin (2003)"},{"issue":"10\u201311","key":"9393_CR42","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1016\/j.disc.2011.02.014","volume":"311","author":"A. Soleimanfallah","year":"2011","unstructured":"Soleimanfallah, A., Yeo, A.: A kernel of order 2k\u2212c for vertex cover. Discrete Math. 311(10\u201311), 892\u2013895 (2011). doi: 10.1016\/j.disc.2011.02.014","journal-title":"Discrete Math."},{"key":"9393_CR43","first-page":"431","volume-title":"Proc. 7th TAMC","author":"J. Uhlmann","year":"2010","unstructured":"Uhlmann, J., Weller, M.: Two-layer planarization parameterized by feedback edge set. In: Proc. 7th TAMC, pp. 431\u2013442 (2010). doi: 10.1007\/978-3-642-13562-0_39"},{"key":"9393_CR44","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C.K. Yap","year":"1983","unstructured":"Yap, C.K.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287\u2013300 (1983). doi: 10.1016\/0304-3975(83)90020-8","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9393_CR45","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1002\/jgt.3190150208","volume":"15","author":"J. Zito","year":"1991","unstructured":"Zito, J.: The structure and maximum number of maximum independent sets in trees. J. Graph Theory 15(2), 207\u2013221 (1991). doi: 10.1007\/s00224-012-9393-4","journal-title":"J. Graph Theory"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9393-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,25]],"date-time":"2019-06-25T01:23:31Z","timestamp":1561425811000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9393-4"}},"subtitle":["Upper and Lower Bounds for a Refined Parameter"],"short-title":[],"issued":{"date-parts":[[2012,3,8]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["9393"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9393-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,8]]}}}