Tight kernel bounds for problems on graphs with small degeneracy

DOI10.1145/3108239MaRDI QIDQ4554933zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Fabrizio Grandoni, Danny Hermelin

Publication date 12 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

degenerate graphskernelizationkernelization lower boundsparameterized complexitysparse graphsweak compositions

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In this paper we consider kernelization for problems on d-degenerate graphs, i.e. graphs such that any subgraph contains a vertex of degree at most $d$. This graph class generalizes many classes of graphs for which effective kernelization is known to exist, e.g. planar graphs, H-minor free graphs, and H-topological-minor free graphs. We show that for several natural problems on d-degenerate graphs the best known kernelization upper bounds are essentially tight.

Recommendations

• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size

Cited in

(19)

• Twin-width and polynomial kernels
• Tight Approximations of Degeneracy in Large Graphs
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Polynomial kernels for hard problems on disk graphs
• Hans Bodlaender and the Theory of Kernelization Lower Bounds
• Exploiting c-closure in kernelization algorithms for graph problems
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Exploiting c-Closure in Kernelization Algorithms for Graph Problems
• Essentially tight kernels for (weakly) closed graphs
• Computing dense and sparse subgraphs of weakly closed graphs
• Essentially tight kernels for (weakly) closed graphs
• Twin-width and polynomial kernels
• Stability in graphs with matroid constraints
• Parameterized covering in semi-ladder-free hypergraphs
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• Cuts in graphs with matroid constraints

This page was built for publication: Tight kernel bounds for problems on graphs with small degeneracy

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