Kernels for structural parameterizations of vertex cover -- case of small degree modulators

DOI10.4230/LIPICS.IPEC.2015.331MaRDI QIDQ5363786zbMATH OpenFDO

Authors Diptapriyo Majumdar, Venkatesh Raman, Saket Saurabh

Publication date 29 September 2017

zbMATH Keywords

parameterized complexityvertex coverkernelizationstructural parameterizationexpansion lemma

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Polynomial kernels for vertex cover parameterized by small degree modulators
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Smaller parameters for vertex cover kernelization
• Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
• Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel

Cited in

(16)

• Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
• Vertex cover structural parameterization revisited
• Constrained bipartite vertex cover: the easy kernel is essentially tight
• 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?
• Polynomial kernels for vertex cover parameterized by small degree modulators
• On the kernelization of split graph problems
• A new framework for kernelization lower bounds: the case of maximum minimal vertex cover
• What Is Known About Vertex Cover Kernelization?
• A kernel of order \(2k - c\) for Vertex Cover
• A refined branching algorithm for the maximum satisfiability problem
• Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
• Smaller parameters for vertex cover kernelization
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Elimination distances, blocking sets, and kernels for Vertex Cover
• Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization

This page was built for publication: Kernels for structural parameterizations of vertex cover -- case of small degree modulators

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