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

DOI10.4230/LIPICS.IPEC.2015.331zbMATH Open1378.68089MaRDI QIDQ5363786FDOQ5363786

Authors: Diptapriyo Majumdar, Venkatesh Raman, Saket Saurabh 

Publication date: 29 September 2017

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

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)

Cited In (16)

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

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)