How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?

DOI10.4230/LIPICS.IPEC.2017.10MaRDI QIDQ5111869zbMATH OpenOpenAlexFDO

Authors Marin Bougeret, Ignasi Sau

Publication date 27 May 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/8556/pdf/LIPIcs-IPEC-2017-10.pdf/

zbMATH Keywords

treewidthsparse graphsparameterized complexitystructural parameterspolynomial kernelstreedepth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Kernelization using structural parameters on sparse graph classes
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Tight kernel bounds for problems on graphs with small degeneracy
• Polynomial kernels for vertex cover parameterized by small degree modulators

Cites work

• (Meta) Kernelization
• A faster parameterized algorithm for treedepth
• Bidimensionality and kernels
• Crown structures for vertex cover kernelization
• Explicit linear kernels via dynamic programming
• Incompressibility through Colors and IDs
• Infeasibility of instance compression and succinct PCPs for NP
• Kernelization using structural parameters on sparse graph classes
• Kernels for structural parameterizations of vertex cover -- case of small degree modulators
• On problems without polynomial kernels
• On the hardness of losing width
• Parameterized and Exact Computation
• Reflections on multivariate algorithmics and problem parameterization
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• Sparsity. Graphs, structures, and algorithms
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
• Vertex cover structural parameterization revisited

Cited in

(7)

• Hitting minors on bounded treewidth graphs. III. Lower bounds
• Optimal data reduction for graph coloring using low-degree polynomials
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Kernelization using structural parameters on sparse graph classes
• Grid recognition: classical and parameterized computational perspectives
• Twin-width and polynomial kernels

This page was built for publication: How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?

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