How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
From MaRDI portal
Publication:2324243
Abstract: In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsk{`y} et al. [ESA 2013] proved that every graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a -treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most , where is a fixed integer. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs. In this article we answer this question by finding two very natural such problems: we prove that Vertex Cover admits a polynomial kernel on general graphs for any integer , and that Dominating Set does not for any integer even on degenerate graphs, unless . For the positive result, we build on the techniques of Jansen and Bodlaender [STACS 2011], and for the negative result we use a polynomial parameter transformation for and an OR-cross-composition for . As existing results imply that Dominating Set admits a polynomial kernel on degenerate graphs for , our result provides a dichotomy about the existence of polynomial kernels for Dominating Set on degenerate graphs with this parameter.
Recommendations
- 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
- Kernelization using structural parameters on sparse graph classes
- Polynomial kernels for 3-leaf power graph modification problems
- Polynomial kernels for 3-leaf power graph modification problems
- A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- Approximate tree kernels
Cites work
- (Meta) Kernelization
- A faster parameterized algorithm for treedepth
- Bidimensionality and kernels
- Crown structures for vertex cover kernelization
- Dynamic programming for graphs on surfaces
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Explicit linear kernels via dynamic programming
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Kernelization Lower Bounds by Cross-Composition
- Kernelization lower bounds through colors and IDs
- Kernelization using structural parameters on sparse graph classes
- Kernels for structural parameterizations of vertex cover -- case of small degree modulators
- Meta-kernelization using Well-structured Modulators
- Meta-kernelization with structural parameters
- On problems without polynomial kernels
- On the hardness of losing width
- Parameterized algorithms
- Parametrized complexity theory.
- Planar Formulae and Their Uses
- Reflections on multivariate algorithmics and problem parameterization
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- 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
(21)- On the approximate compressibility of connected vertex cover
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- On the hardness of losing width
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Parameterized complexity of computing maximum minimal blocking and hitting sets
- Kernelization using structural parameters on sparse graph classes
- Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
- Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Smaller parameters for vertex cover kernelization
- Kernelization for feedback vertex set via elimination distance to a forest
- On the Parameterized Complexity of Clique Elimination Distance
- Kernelization for feedback vertex set via elimination distance to a forest
- Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel
- Kernelization dichotomies for hitting subgraphs under structural parameterizations
- Difference determines the degree: structural kernelizations of component order connectivity
- Kernelizing temporal exploration problems
- Component order connectivity admits no polynomial kernel parameterized by the distance to subdivided comb graphs
- Boundaried kernelization
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 Q2324243)
