{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:32:52Z","timestamp":1787322772924,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["267959"],"award-info":[{"award-number":["267959"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a long-standing, notorious open problem in parameterized complexity. Some years ago, the breakthrough work by Kratsch and Wahlstr\u00f6m on representative sets finally answered this question in the affirmative [FOCS 2012]. In this paper, we present an alternative, algebraic compression of the Vertex Cover Above LP problem into the Rank Vertex Cover problem. Here, the input consists of a graph $G$, a parameter $k$, and a bijection between $V(G)$ and the set of columns of a representation of a matroid $M$, and the objective is to find a vertex cover whose rank is upper bounded by $k$.<\/jats:p>","DOI":"10.1137\/17m1154370","type":"journal-article","created":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T14:06:27Z","timestamp":1563890787000},"page":"1277-1296","source":"Crossref","is-referenced-by-count":1,"title":["Rank Vertex Cover as a Natural Problem for Algebraic Compression"],"prefix":"10.1137","volume":"33","author":[{"given":"Syed M.","family":"Meesum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,7,23]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"M. Agrawal, N. Kayal, and N. Saxena,\n                      Primes is in P\n                      , Ann. Math. (2004), pp. 781-793.","DOI":"10.4007\/annals.2004.160.781"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00213-5"},{"key":"atypb3","first-page":"565","volume":"22","author":"Bareiss E. H.","year":"1968","journal-title":"Math. Comp."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/0222038"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.10.003"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/050646354"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.026"},{"key":"atypb9","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, Berlin, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462899"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer, Cham, Switzerland, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"R. G. Downey, M. R. Fellows, and U. Stege,\n                      Parameterized complexity: A framework for systematically confronting computational intractability\n                      , in Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, Vol. 49, 1999, pp. 49-99.","DOI":"10.1090\/dimacs\/049\/04"},{"key":"atypb14","first-page":"1152","author":"Garg S.","year":"2016","journal-title":"Philadelphia"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"G. Gordon and J. McNulty,\n                      Matroids: A Geometric Introduction\n                      , Cambridge University Press, Cambridge, 2012,https:\/\/doi.org\/10.1017\/CBO9781139049443.","DOI":"10.1017\/CBO9781139049443"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9262-y"},{"key":"atypb17","unstructured":"R. Hill,\n                      A First Course in Coding Theory\n                      , Oxford Applied Linguistics, Clarendon Press, Oxford, 1986,https:\/\/books.google.co.in\/books?id=UTxjBX9lKoMC."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"S. Jukna,\n                      Extremal combinatorics: With applications in computer science\n                      , Texts Theoret. Comput. Sci. EATCS Ser., Springer, Berlin, 2011,https:\/\/books.google.co.in\/books?id=NV3Y8vjWo8kC.","DOI":"10.1007\/978-3-642-17364-6_1"},{"key":"atypb20","first-page":"1","author":"Kratsch S.","year":"2016","journal-title":"Denmark"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"S. Kratsch and M. Wahlstr\u00f6m,\n                      Representative sets and irrelevant vertices: New tools for kernelization\n                      , in IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS-12), T. Roughgarden ed., IEEE Computer Society, Los Alamitos, CA, 2012, pp. 450-459.","DOI":"10.1109\/FOCS.2012.46"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.09.003"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"atypb24","unstructured":"L. Lov\u00e1sz,\n                      Flats in matroids and geometric graphs\n                      , Combinatorial Surveys, (1977), pp. 45-86."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9412-2"},{"key":"atypb26","first-page":"338","author":"Narayanaswamy N.","year":"2012","journal-title":"LIPIcs"},{"key":"atypb27","first-page":"561","author":"Niedermeier R.","year":"1999","journal-title":"Berlin"},{"key":"atypb28","unstructured":"J. G. Oxley,\n                      Matroid Theory\n                      , Oxford Graduate Texts in Mathematics, Oxford University Press, New York, 2006."},{"key":"atypb29","first-page":"382","author":"Raman V.","year":"2011","journal-title":"Berlin"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"},{"key":"atypb31","unstructured":"F. N. Abu-Khzam, M. A. Langston, and W. H. Suters,\n                      Fast, effective vertex cover kernelization: a tale of two algorithms\n                      , 3rd ACS\/IEEE International Conference on Computer Systems and Applications, 2005, IEEE, Piscataway, NJ, 2005."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1154370","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:25:29Z","timestamp":1787318729000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1154370"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1154370"],"URL":"https:\/\/doi.org\/10.1137\/17m1154370","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}