Rank vertex cover as a natural problem for algebraic compression

DOI10.1137/17M1154370zbMATH Open1419.05203arXiv1705.02822OpenAlexW2963443205MaRDI QIDQ5232153FDOQ5232153

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)

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

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

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)

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. With applications in computer science
• 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 \textsc{Vertex Cover}: 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)