Rank vertex cover as a natural problem for algebraic compression
Journal article, Peer reviewed
Published version
Åpne
Permanent lenke
https://hdl.handle.net/11250/2722590Utgivelsesdato
2019Metadata
Vis full innførselSamlinger
- Department of Informatics [981]
- Registrations from Cristin [10402]
Originalversjon
10.1137/17M1154370Sammendrag
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$.