{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T22:03:34Z","timestamp":1769983414291,"version":"3.49.0"},"publisher-location":"Cham","reference-count":71,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319983547","type":"print"},{"value":"9783319983554","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98355-4_19","type":"book-chapter","created":{"date-parts":[[2018,8,8]],"date-time":"2018-08-08T10:34:57Z","timestamp":1533724497000},"page":"330-356","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["What Is Known About Vertex Cover Kernelization?"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[]},{"given":"Lars","family":"Jaffke","sequence":"additional","affiliation":[]},{"given":"Aliz Izabella","family":"Kir\u00e1ly","sequence":"additional","affiliation":[]},{"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"key":"19_CR1","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: Arge, L., Italiano, G.F., Sedgewick, R. (eds.) Proceedings 6th Workshop on Algorithm Engineering and Experiments and 1st Workshop on Analytic Algorithms and Combinatorics (ALENEX\/ANALC), pp. 62\u201369. SIAM (2004)"},{"key":"19_CR2","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57285-7","volume-title":"Conflict Resolution in Decision Making","year":"2017","unstructured":"Aydo\u011fan, R., Baarslag, T., Gerding, E., Jonker, C.M., Julian, V., Sanchez-Anguix, V. (eds.): COREDEMA 2016. LNCS (LNAI), vol. 10238. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57285-7"},{"issue":"3","key":"19_CR3","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(97)00213-5","volume":"65","author":"R Balasubramanian","year":"1998","unstructured":"Balasubramanian, R., Fellows, M.R., Raman, V.: An improved fixed-parameter algorithm for vertex cover. Inf. Process. Lett. 65(3), 163\u2013168 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"8","key":"19_CR4","doi-asserted-by":"publisher","first-page":"e12262","DOI":"10.1371\/journal.pone.0012262","volume":"5","author":"R Berretta","year":"2010","unstructured":"Berretta, R., Moscato, P.: Cancer biomarker discovery: the entropic hallmark. PLoS ONE 5(8), e12262 (2010)","journal-title":"PLoS ONE"},{"issue":"1","key":"19_CR5","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."},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-540-70575-8_46","volume-title":"Automata, Languages and Programming","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 563\u2013574. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_46"},{"key":"19_CR7","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H Bodlender","year":"2009","unstructured":"Bodlender, H., Downey, R., Fellows, M., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75, 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"19_CR8","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"JF Buss","year":"1993","unstructured":"Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM J. Comput. 22(3), 560\u2013572 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"19_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2005.05.026","volume":"173","author":"S Butenko","year":"2006","unstructured":"Butenko, S., Wilhelm, W.E.: Clique-detection models in computational biochemistry and genomics. Eur. J. Oper. Res. 173(1), 1\u201317 (2006)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"19_CR10","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0168-0072(95)00020-8","volume":"84","author":"L Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability. Ann. Pure Appl. Log. 84(1), 119\u2013138 (1997)","journal-title":"Ann. Pure Appl. Log."},{"issue":"2","key":"19_CR11","doi-asserted-by":"publisher","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)","journal-title":"J. Algorithms"},{"issue":"40\u201342","key":"19_CR12","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., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010). Previously appeared in MFCS 2006 as \u2018Improved parameterized upper bounds for vertex cover\u2019","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"19_CR13","doi-asserted-by":"publisher","first-page":"e1000135","DOI":"10.1371\/journal.pcbi.1000135","volume":"4","author":"TMK Cheng","year":"2008","unstructured":"Cheng, T.M.K., Yu-En, L., Vendruscolo, M., Blundell, T.L., et al.: Prediction by graph theoretic measures of structural effects in proteins arising from non-synonymous single nucleotide polymorphisms. PLoS Comput. Biol. 4(7), e1000135 (2008)","journal-title":"PLoS Comput. Biol."},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-540-30559-0_22","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B Chor","year":"2004","unstructured":"Chor, B., Fellows, M., Juedes, D.: Linear kernels in linear time, or how to save k colors in O(n2) steps. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 257\u2013269. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30559-0_22"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Cong, J., Smith, M.L.: A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design. In: Proceedings 30th International Design Automation Conference, pp. 755\u2013760. ACM (1993)","DOI":"10.1145\/157485.165119"},{"key":"19_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms, 1st edn. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","edition":"1"},{"key":"19_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-540-28639-4_24","volume-title":"Parameterized and Exact Computation","author":"F Dehne","year":"2004","unstructured":"Dehne, F., Fellows, M., Rosamond, F., Shaw, P.: Greedy localization, iterative compression, and modeled crown reductions: new FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In: Downey, R., Fellows, M., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 271\u2013280. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-28639-4_24"},{"issue":"4","key":"19_CR18","doi-asserted-by":"publisher","first-page":"23","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 (JACM) 61(4), 23 (2014). Previously appeared in STOC 2010","journal-title":"J. ACM (JACM)"},{"key":"19_CR19","series-title":"Progress in Computer Science and Applied Logic","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized computational feasibility. In: Clote, P., Remmel, J.B. (eds.) Feasible Mathematics II. PCS, pp. 219\u2013244. Springer, Boston (1995). https:\/\/doi.org\/10.1007\/978-1-4612-2566-9_7"},{"key":"19_CR20","series-title":"Texts in Computer Science","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. TCS. Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R., Stege, U.: Parameterized complexity: a framework for systematically confronting computational intractability. In: Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, vol. 49, pp. 49\u201399 (1999)","DOI":"10.1090\/dimacs\/049\/04"},{"key":"19_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/9780470125847.ch1","volume":"7","author":"GM Downs","year":"1996","unstructured":"Downs, G.M., Willett, P.: Similarity searching in databases of chemical structures. Rev. Comput. Chem. 7, 1\u201366 (1996)","journal-title":"Rev. Comput. Chem."},{"key":"19_CR23","first-page":"1","volume":"80","author":"J Enright","year":"2017","unstructured":"Enright, J., Meeks, K.: Deleting edges to restrict the size of an epidemic: a new application for treewidth. Algorithmica 80, 1\u201333 (2017). Previously appeared in COCOA 2015","journal-title":"Algorithmica"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Fellows, M.R.: Parameterized complexity: new developments and research frontiers. In: Downey, R.G., Hirschfeldt, D.R. (eds.) Aspects of Complexity: Minicourses in Algorithmics, Complexity and Computational Algebra. De Gruyter Series in Logic and Its Applications, vol. 4, pp. 51\u201372. De Gruyter, Kaikoura (2000)","DOI":"10.1515\/9783110889178.51"},{"key":"19_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/3-540-45678-3_26","volume-title":"Algorithms and Computation","author":"MR Fellows","year":"2001","unstructured":"Fellows, M.R.: Parameterized complexity: the main ideas and some research frontiers. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol. 2223, pp. 291\u2013307. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45678-3_26"},{"key":"19_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-39890-5_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"MR Fellows","year":"2003","unstructured":"Fellows, M.R.: Blow-ups, win\/win\u2019s, and crown rules: some new directions in FPT. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 1\u201312. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-39890-5_1"},{"key":"19_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/11847250_25","volume-title":"Parameterized and Exact Computation","author":"MR Fellows","year":"2006","unstructured":"Fellows, M.R.: The lost continent of polynomial time: preprocessing and kernelization. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 276\u2013277. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11847250_25"},{"issue":"4","key":"19_CR28","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1109\/TST.2014.6867514","volume":"19","author":"MR Fellows","year":"2014","unstructured":"Fellows, M.R.: Some open problems in parameterized complexity related to the work of Jianer Chen. Tsinghua Sci. Technol. 19(4), 325\u2013328 (2014)","journal-title":"Tsinghua Sci. Technol."},{"issue":"3","key":"19_CR29","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."},{"key":"19_CR30","unstructured":"Fellows, M.R., Stege, U.: An improved fixed-parameter tractable algorithm for vertex cover (1999)"},{"issue":"16","key":"19_CR31","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.ipl.2010.05.029","volume":"110","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Gaspers, S., Golovach, P.A., Kratsch, D., Saurabh, S.: Parameterized algorithm for eternal vertex cover. Inf. Process. Lett. 110(16), 702\u2013706 (2010)","journal-title":"Inf. Process. Lett."},{"key":"19_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-662-53536-3_15","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Str\u00f8mme, T.J.F.: Vertex cover structural parameterization revisited. In: Heggernes, P. (ed.) WG 2016. LNCS, vol. 9941, pp. 171\u2013182. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53536-3_15"},{"key":"19_CR33","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Proceedings Fortieth Annual ACM Symposium on Theory of Computing (STOC), pp. 133\u2013142. ACM (2008)","DOI":"10.1145\/1374376.1374398"},{"key":"19_CR34","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"issue":"9","key":"19_CR35","doi-asserted-by":"publisher","first-page":"5750","DOI":"10.1109\/TIT.2014.2339840","volume":"60","author":"L-A Gottlieb","year":"2014","unstructured":"Gottlieb, L.-A., Kontorovich, A., Krauthgamer, R.: Efficient classification for metric data. IEEE Trans. Inf. Theory 60(9), 5750\u20135759 (2014)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"19_CR36","doi-asserted-by":"publisher","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. ACM SIGACT News 38(1), 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"issue":"3","key":"19_CR37","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s00224-007-1309-3","volume":"41","author":"J Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory Comput. Syst. 41(3), 501\u2013520 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"19_CR38","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","volume":"10","author":"P Hall","year":"1935","unstructured":"Hall, P.: On representatives of subsets. J. Lond. Math. Soc. 10(1), 26\u201330 (1935)","journal-title":"J. Lond. Math. Soc."},{"key":"19_CR39","doi-asserted-by":"crossref","unstructured":"Hamzaoglu, I., Patel, J.H.: Test set compaction algorithms for combinational circuits. In: Proceedings IEEE\/ACM International Conference on Computer-Aided Design, pp. 283\u2013289. ACM (1998)","DOI":"10.1145\/288548.288615"},{"key":"19_CR40","unstructured":"Hols, E.-M.C., Kratsch, S.: Smaller parameters for vertex cover kernelization. arXiv preprint arXiv:1711.04604 (2017)"},{"issue":"4","key":"19_CR41","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"19_CR42","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-sat. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"19_CR43","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."},{"key":"19_CR44","unstructured":"Jansen, B.M.P.: The power of data reduction. Kernels for fundamental graph problems. Ph.D. thesis, Utrecht University, The Netherlands (2013)"},{"issue":"2","key":"19_CR45","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. Theory Comput. Syst. 53(2), 263\u2013299 (2013)","journal-title":"Theory Comput. Syst."},{"key":"19_CR46","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. IRSS, pp. 85\u2013103. Springer, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"19_CR47","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jcss.2010.06.009","volume":"77","author":"RM Karp","year":"2011","unstructured":"Karp, R.M.: Heuristic algorithms in computational molecular biology. J. Comput. Syst. Sci. 77(1), 122\u2013128 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"19_CR48","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1089\/cmb.1996.3.289","volume":"3","author":"I Koch","year":"1996","unstructured":"Koch, I., Lengauer, T., Wanke, E.: An algorithm for finding maximal common subtopologies in a set of protein structures. J. Comput. Biol. 3(2), 289\u2013306 (1996)","journal-title":"J. Comput. Biol."},{"issue":"4","key":"19_CR49","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D K\u00f6nig","year":"1916","unstructured":"K\u00f6nig, D.: \u00dcber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77(4), 453\u2013465 (1916)","journal-title":"Math. Ann."},{"key":"19_CR50","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Representative sets and irrelevant vertices: new tools for kernelization. In: Proceedings 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 450\u2013459. IEEE (2012)","DOI":"10.1109\/FOCS.2012.46"},{"issue":"23","key":"19_CR51","doi-asserted-by":"publisher","first-page":"1089","DOI":"10.1016\/j.ipl.2011.09.003","volume":"111","author":"M Lampis","year":"2011","unstructured":"Lampis, M.: A kernel of order $$2k - c\\log k$$ for vertex cover. Inf. Process. Lett. 111(23), 1089\u20131091 (2011)","journal-title":"Inf. Process. Lett."},{"key":"19_CR52","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-6291-9","volume-title":"An Introduction to Chemoinformatics","author":"AR Leach","year":"2007","unstructured":"Leach, A.R., Gillet, V.J.: An Introduction to Chemoinformatics. Springer, Dordrecht (2007)"},{"issue":"105","key":"19_CR53","first-page":"41","volume":"3","author":"D Lokshtanov","year":"2013","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 3(105), 41\u201371 (2013)","journal-title":"Bull. EATCS"},{"key":"19_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-642-30891-8_10","volume-title":"The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday","author":"D Lokshtanov","year":"2012","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization \u2013 preprocessing with a guarantee. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. LNCS, vol. 7370, pp. 129\u2013161. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-30891-8_10"},{"key":"19_CR55","unstructured":"Majumdar, D., Raman, V., Saurabh, S.: Kernels for structural parameterizations of vertex cover-case of small degree modulators. In: Proceedings 10th International Symposium on Parameterized and Exact Computation (IPEC). Leibniz International Proceedings in Informatics (LIPIcs), vol. 43, pp. 331\u2013342. Schloss Dagstuhl Publishing (2015)"},{"issue":"1","key":"19_CR56","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.disopt.2010.10.001","volume":"8","author":"N Misra","year":"2011","unstructured":"Misra, N., Raman, V., Saurabh, S.: Lower bounds on kernelization. Discrete Optim. 8(1), 110\u2013128 (2011)","journal-title":"Discrete Optim."},{"key":"19_CR57","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: Proceedings 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 248\u2013255. IEEE (2004)","DOI":"10.1109\/FOCS.2004.40"},{"key":"19_CR58","unstructured":"Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: LP can be a cure for parameterized problems. In: D\u00fcrr, C., Wilke, T. (eds.) Proceedings 29th Symposium on Theoretical Aspects of Computer Science (STACS). Leibniz International Proceedings in Informatics (LIPIcs), vol. 14, pp. 338\u2013349. Schloss Dagstuhl Publishing (2012)"},{"issue":"1","key":"19_CR59","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/BF01580222","volume":"6","author":"GL Nemhauser","year":"1974","unstructured":"Nemhauser, G.L., Trotter, L.E.: Properties of vertex packing and independence system polyhedra. Math. Program. 6(1), 48\u201361 (1974)","journal-title":"Math. Program."},{"key":"19_CR60","series-title":"Oxford Lecture Series in Mathematics and its Applications","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2002","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2002)"},{"key":"19_CR61","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1998)"},{"issue":"10","key":"19_CR62","doi-asserted-by":"publisher","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-c$$ for vertex cover. Discrete Math. 311(10), 892\u2013895 (2011)","journal-title":"Discrete Math."},{"key":"19_CR63","unstructured":"Stege, U.: Resolving conflicts in problems from computational biology. Ph.D. thesis, ETH Zuerich (2000)"},{"issue":"3","key":"19_CR64","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1287\/opre.1040.0189","volume":"53","author":"DM Strickland","year":"2005","unstructured":"Strickland, D.M., Barnes, E., Sokol, J.S.: Optimal protein structure alignment using maximum cliques. Oper. Res. 53(3), 389\u2013402 (2005)","journal-title":"Oper. Res."},{"key":"19_CR65","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2003","unstructured":"Vazirani, V.V.: Approximation Algorithms, 1st edn. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-662-04565-7","edition":"1"},{"key":"19_CR66","unstructured":"Weihe, K.: Covering trains by stations or the power of data reduction. In: Proceedings 1st Conference on Algorithms and Experiments (ALEX 1998), Trento, Italy, pp. 1\u20138 (1998)"},{"key":"19_CR67","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44691-5_1","volume-title":"Algorithm Engineering","author":"K Weihe","year":"2001","unstructured":"Weihe, K.: On the differences between \u201cpractical\u201d and \u201capplied\u201d. In: N\u00e4her, S., Wagner, D. (eds.) WAE 2000. LNCS, vol. 1982, pp. 1\u201310. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44691-5_1"},{"key":"19_CR68","unstructured":"Weller, M.: Aspects of preprocessing applied to combinatorial graph problems. Ph.D. thesis, TU Berlin (2013)"},{"issue":"6","key":"19_CR69","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1021\/ci9800211","volume":"38","author":"P Willett","year":"1998","unstructured":"Willett, P., Barnard, J.M., Downs, G.M.: Chemical similarity searching. J. Chem. Inf. Comput. Sci. 38(6), 983\u2013996 (1998)","journal-title":"J. Chem. Inf. Comput. Sci."},{"issue":"3","key":"19_CR70","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"CK Yap","year":"1983","unstructured":"Yap, C.K.: Some consequences of non-uniform conditions on uniform classes. Theoret. Comput. Sci. 26(3), 287\u2013300 (1983)","journal-title":"Theoret. Comput. Sci."},{"issue":"16","key":"19_CR71","doi-asserted-by":"publisher","first-page":"5934","DOI":"10.1073\/pnas.0306752101","volume":"101","author":"E Yeger-Lotem","year":"2004","unstructured":"Yeger-Lotem, E., et al.: Network motifs in integrated cellular networks of transcription-regulation and protein-protein interaction. Proc. Nat. Acad. Sci. U.S.A. 101(16), 5934\u20135939 (2004)","journal-title":"Proc. Nat. Acad. Sci. U.S.A."}],"container-title":["Lecture Notes in Computer Science","Adventures Between Lower Bounds and Higher Altitudes"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98355-4_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T07:38:22Z","timestamp":1751787502000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-98355-4_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319983547","9783319983554"],"references-count":71,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98355-4_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"9 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}