Rank vertex cover as a natural problem for algebraic compression
Journal article, Peer reviewed
MetadataShow full item record
Original versionSIAM Journal on Discrete Mathematics. 2019, 33 (3), 1277-1296. 10.1137/17M1154370
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$.