Vertex cover kernelization revisited: upper and lower bounds for a refined parameter

DOI10.4230/LIPICS.STACS.2011.177MaRDI QIDQ3113682zbMATH OpenFDO

Authors Bart M. P. Jansen, Hans L. Bodlaender

Publication date 23 January 2012

Full work available at URL https://arxiv.org/abs/1012.4701, http://subs.emis.de/LIPIcs/frontdoor_8632.html

zbMATH Keywords

kernelizationlower boundsparameterized complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Kernels for structural parameterizations of vertex cover -- case of small degree modulators
• Polynomial kernels for vertex cover parameterized by small degree modulators
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• A Cubic Kernel for Feedback Vertex Set

Cited in

(23)

• Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
• Polynomial kernels for vertex cover parameterized by small degree modulators
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• On the hardness of losing width
• On polynomial kernels for structural parameterizations of odd cycle transversal
• On the hardness of losing width
• Kernelization -- preprocessing with a guarantee
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Two-layer planarization parameterized by feedback edge set
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Confronting intractability via parameters
• Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Smaller parameters for vertex cover kernelization
• Parameterized and Exact Computation
• Kernels for structural parameterizations of vertex cover -- case of small degree modulators
• Parameterized complexity for iterated type partitions and modular-width
• What Is Known About Vertex Cover Kernelization?
• Search-space reduction via essential vertices
• Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel
• Component order connectivity admits no polynomial kernel parameterized by the distance to subdivided comb graphs

This page was built for publication: Vertex cover kernelization revisited: upper and lower bounds for a refined parameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3113682)