Header menu link for other important links
X
Rank vertex cover as a natural problem for algebraic compression
S.M. Meesum, , S. Saurabh, M. Zehavi
Published in Society for Industrial and Applied Mathematics Publications
2019
Volume: 33
   
Issue: 3
Pages: 1277 - 1296
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. © 2019 Society for Industrial and Applied Mathematics
About the journal
JournalSIAM Journal on Discrete Mathematics
PublisherSociety for Industrial and Applied Mathematics Publications
ISSN08954801