dc.contributor.author Meesum, Syed Mohammad dc.contributor.author Panolan, Fahad dc.contributor.author Saurabh, Saket dc.contributor.author Zehavi, Meirav dc.date.accessioned 2021-01-12T14:01:12Z dc.date.available 2021-01-12T14:01:12Z dc.date.created 2019-11-25T14:19:10Z dc.date.issued 2019 dc.Published SIAM Journal on Discrete Mathematics. 2019, 33 (3), 1277-1296. en_US dc.identifier.issn 0895-4801 dc.identifier.uri https://hdl.handle.net/11250/2722590 dc.description.abstract 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öm 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$. en_US dc.language.iso eng en_US dc.publisher SIAM en_US dc.title Rank vertex cover as a natural problem for algebraic compression en_US dc.type Journal article en_US dc.type Peer reviewed en_US dc.description.version publishedVersion en_US dc.rights.holder Copyright 2019 Society for Industrial and Applied Mathematics en_US cristin.ispublished true cristin.fulltext original cristin.qualitycode 1 dc.identifier.doi 10.1137/17M1154370 dc.identifier.cristin 1751937 dc.source.journal SIAM Journal on Discrete Mathematics en_US dc.source.40 33 en_US dc.source.14 3 en_US dc.source.pagenumber 1277-1296 en_US
﻿