Rank vertex cover as a natural problem for algebraic compression

DOI10.1137/17M1154370MaRDI QIDQ5232153zbMATH OpenOpenAlexFDO

Authors 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)

Full work available at URL https://arxiv.org/abs/1705.02822

zbMATH Keywords

vertex coverkernelizationodd cycle transversalalgebraic compression

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• A randomized polynomial kernelization for vertex cover with a smaller parameter
• LP can be a cure for parameterized problems
• Faster parameterized algorithms using linear programming
• Vertex cover problem parameterized above and below tight bounds

Cites work

• scientific article; zbMATH DE number 3561367 (Why is no real title available?)
• scientific article; zbMATH DE number 1304341 (Why is no real title available?)
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• scientific article; zbMATH DE number 3999824 (Why is no real title available?)
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• A kernel of order \(2k-c\log k\) for vertex cover
• Almost 2-SAT is fixed-parameter tractable
• An improved fixed-parameter algorithm for vertex cover
• Extremal combinatorics. With applications in computer science
• Faster parameterized algorithms using linear programming
• Fundamentals of parameterized complexity
• Improved upper bounds for vertex cover
• LP can be a cure for parameterized problems
• Matroids. A geometric introduction
• Nondeterminism within $P^ * $
• PRIMES is in P
• Parameterized algorithms
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Paths, flowers and vertex cover
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• Refined memorization for vertex cover
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
• The complexity of König subgraph problems and above-guarantee vertex cover
• Vertex cover problem parameterized above and below tight bounds
• Vertex cover: Further observations and further improvements
• Which problems have strongly exponential complexity?

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)