{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:42:53Z","timestamp":1787323373172,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In the vertex cover problem we are given a graph $G=(V,E)$ and an integer $k$ and have to determine whether there is a set $X\\subseteq V$ of size at most $k$ such that each edge in $E$ has at least one endpoint in $X$. The problem can be easily solved in time $\\mathcal{O}^*(2^k)$, making it fixed-parameter tractable (FPT) with respect to $k$. While the fastest known algorithm takes only time $\\mathcal{O}^*(1.2738^k)$, much stronger improvements have been obtained by studying parameters that are smaller than $k$. Apart from treewidth-related results, the arguably best algorithm for vertex cover runs in time $\\mathcal{O}^*(2.3146^p)$, where $p=k-LP(G)$ is only the excess of the solution size $k$ over the best fractional vertex cover [Lokshtanov et al. ACM Trans. Algorithms, 11 (2014), pp. 15:1--15:31]. Since $p\\leq k$ but $k$ cannot be bounded in terms of $p$ alone, this strictly increases the range of tractable instances. Recently, [Garg and Philip, Proceedings of the Symposium on Discrete Algorithms, 2016, pp. 1152--1166] greatly contributed to understanding the parameterized complexity of the vertex cover problem. They prove that $2LP(G)-MM(G)$ is a lower bound for the vertex cover size of $G$, where $MM(G)$ is the size of a largest matching of $G$, and proceed to study parameter $\\ell=k-(2LP(G)-MM(G))$. They give an algorithm of running time $\\mathcal{O}^*(3^\\ell)$, proving that vertex cover is FPT in $\\ell$. It can be easily observed that $\\ell\\leq p$ whereas $p$ cannot be bounded in terms of $\\ell$ alone. We complement the work of Garg and Philip by proving that vertex cover admits a randomized polynomial kernelization in terms of $\\ell$, i.e., an efficient preprocessing to size polynomial in $\\ell$. This improves over parameter $p=k-LP(G)$ for which this was previously known [Kratsch and Wahlstr\u00f6m, Proceedings of the IEEE Symposium on Foundations of Computer Science, 2012, pp. 450--459].<\/jats:p>","DOI":"10.1137\/16m1104585","type":"journal-article","created":{"date-parts":[[2018,7,26]],"date-time":"2018-07-26T13:47:50Z","timestamp":1532612870000},"page":"1806-1839","source":"Crossref","is-referenced-by-count":9,"title":["A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter"],"prefix":"10.1137","volume":"32","author":[{"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,7,26]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.12.3.253"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.026"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015,https:\/\/doi.org\/10.1007\/978-3-319-21275-3.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9480-1"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462899"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer-Verlag, London, 2013,https:\/\/doi.org\/10.1007\/978-1-4471-5559-1.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb11","first-page":"142","author":"Fomin F. V.","year":"2014","journal-title":"SIAM"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch80"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"atypb14","unstructured":"B. M. P. Jansen,\n                      The Power of Data Reduction: Kernels for Fundamental Graph Problems\n                      , PhD thesis, Utrecht University, utrecht, the Netherlands, 2013."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9393-4"},{"key":"atypb16","unstructured":"S. Kratsch,\n                      Recent developments in kernelization: A survey\n                      , Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 113 (2014),http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/285."},{"key":"atypb17","unstructured":"S. Kratsch and M. Wahlstro\u0308m,\n                      Representative Sets and Irrelevant Vertices: New Tools for Kernelization\n                      , preprint, arXiv:1111.2195 [CS. DS], 2011,http:\/\/arxiv.org\/abs\/1111.2195."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"S. Kratsch and M. Wahlstro\u0308m,\n                      Representative sets and irrelevant vertices: New tools for kernelization\n                      , in Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012, pp. 450-459,https:\/\/doi.org\/10.1109\/FOCS.2012.46.","DOI":"10.1109\/FOCS.2012.46"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"atypb20","first-page":"45","author":"Lova\u0301sz L.","year":"1977","journal-title":"London"},{"key":"atypb21","unstructured":"L. Lova\u0301sz and M. D. Plummer,\n                      Matching Theory\n                      , North-Holland, Amsterdam, 1986."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0996"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.027"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9412-2"},{"key":"atypb25","first-page":"338","author":"Narayanaswamy N. S.","year":"2012","journal-title":"STACS."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"atypb27","unstructured":"J. G. Oxley,\n                      Matroid Theory\n                      , Oxford University Press, Oxford, 1992."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(68)90163-7"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"V. Raman, M. S. Ramanujan, and S. Saurabh,\n                      Paths, flowers and Vertex Cover\n                      , in Proceedings of the 19th Annual European Symposium on Algorithms, 2011, pp. 382-393,https:\/\/doi.org\/10.1007\/978-3-642-23719-5_33.","DOI":"10.1007\/978-3-642-23719-5_33"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1104585","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:58:44Z","timestamp":1787320724000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1104585"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1104585"],"URL":"https:\/\/doi.org\/10.1137\/16m1104585","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}