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

DOI10.1007/s00453-018-0468-8zbMath1430.68126arXiv1609.08095OpenAlexW2963685860MaRDI QIDQ2324243

Ignasi Sau, Marin Bougeret

Publication date: 10 September 2019

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

treewidthparameterized complexitysparse graphsstructural 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)

Related Items (12)

Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Parameterized complexity of computing maximum minimal blocking and hitting sets ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ On the approximate compressibility of connected vertex cover ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Smaller Parameters for Vertex Cover Kernelization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kernelization using structural parameters on sparse graph classes
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• Meta-kernelization with structural parameters
• On problems without polynomial kernels
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• On the hardness of losing width
• Crown structures for vertex cover kernelization
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Vertex Cover Structural Parameterization Revisited
• Explicit Linear Kernels via Dynamic Programming
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• Planar Formulae and Their Uses
• Kernelization Lower Bounds Through Colors and IDs
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Kernelization Lower Bounds by Cross-Composition
• A Faster Parameterized Algorithm for Treedepth
• (Meta) Kernelization
• Meta-kernelization using Well-structured Modulators
• Bidimensionality and Geometric Graphs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Dynamic programming for graphs on surfaces
• Parameterized Algorithms

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