Rank Vertex Cover as a Natural Problem for Algebraic Compression
From MaRDI portal
Publication:5232153
DOI10.1137/17M1154370zbMATH Open1419.05203arXiv1705.02822OpenAlexW2963443205MaRDI QIDQ5232153FDOQ5232153
Fahad Panolan, Saket Saurabh, Meirav Zehavi, S. M. Meesum
Publication date: 29 August 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Abstract: The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem has been a longstanding, notorious open problem in Parameterized Complexity. Five years ago, the breakthrough work by Kratsch and Wahlstrom on representative sets has 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 matriod M, and the objective is to find a vertex cover whose rank is upper bounded by k.
Full work available at URL: https://arxiv.org/abs/1705.02822
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Fundamentals of parameterized complexity
- Almost 2-SAT is fixed-parameter tractable
- Which problems have strongly exponential complexity?
- On Multiway Cut Parameterized above Lower Bounds
- LP can be a cure for parameterized problems
- Title not available (Why is that?)
- Parameterized Algorithms
- The complexity of König subgraph problems and above-guarantee vertex cover
- PRIMES is in P
- Title not available (Why is that?)
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Improved upper bounds for vertex cover
- Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
- An improved fixed-parameter algorithm for vertex cover
- Nondeterminism within $P^ * $
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Extremal Combinatorics
- Vertex cover: Further observations and further improvements
- Faster Parameterized Algorithms Using Linear Programming
- A kernel of order \(2k-c\log k\) for vertex cover
- Paths, Flowers and Vertex Cover
- Title not available (Why is that?)
- A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
- Vertex cover problem parameterized above and below tight bounds
- Refined memorization for vertex cover
- Matroids. A geometric introduction
- Title not available (Why is that?)
- Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
This page was built for publication: Rank Vertex Cover as a Natural Problem for Algebraic Compression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232153)
