Kernelization using structural parameters on sparse graph classes
From MaRDI portal
Abstract: Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, meta-theorems for linear kernels exist on graphs of bounded genus, -minor-free graphs, and -topological-minor-free graphs. To the best of our knowledge, no meta-theorems for polynomial kernels are known for any larger sparse graph classes; e.g., for classes of bounded expansion or for nowhere dense ones. In this paper we prove such meta-theorems for the two latter cases. More specifically, we show that graph problems that have finite integer index (FII) have linear kernels on graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For nowhere dense graph classes, our result yields almost-linear kernels. While our parameter may seem rather strong, we argue that a linear kernelization result on graphs of bounded expansion with a weaker parameter (than treedepth modulator) would fail to include some of the problems covered by our framework. Moreover, we only require the problems to have FII on graphs of constant treedepth. This allows us to prove linear kernels for problems such as Longest Path/Cycle, Exact -Path, Treewidth, and Pathwidth, which do not have FII on general graphs (and the first two not even on bounded treewidth graphs).
Recommendations
- Kernelization using structural parameters on sparse graph classes
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Meta-kernelization using Well-structured Modulators
- Meta-kernelization using well-structured modulators
Cites work
- scientific article; zbMATH DE number 176762 (Why is no real title available?)
- scientific article; zbMATH DE number 1323192 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- (Meta) Kernelization
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Bidimensionality and kernels
- Characterisations and examples of graph classes with bounded expansion
- Cluster vertex deletion: a parameterization between vertex cover and clique-width
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- First order properties on nowhere dense structures
- Grad and classes with bounded expansion. I: Decompositions
- Graph Layout Problems Parameterized by Vertex Cover
- Graph theory
- Hitting forbidden minors: approximation and kernelization
- Incompressibility through Colors and IDs
- Kernel bounds for path and cycle problems
- Kernelization and Sparseness: the case of Dominating Set
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Linear time low tree-width partitions and algorithmic consequences
- On cutwidth parameterized by vertex cover
- On nowhere dense graphs
- On problems without polynomial kernels
- On the excluded minors for the matroids of branch-width \(k\)
- On the hardness of losing width
- On the maximum number of cliques in a graph
- Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
- Parametrized complexity theory.
- Polynomial-time data reduction for dominating set
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Sparsity. Graphs, structures, and algorithms
- The branchwidth of graphs and their cycle matroids
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
Cited in
(42)- Polynomial kernels for hitting forbidden minors under structural parameterizations
- On the parameterized complexity of reconfiguration of connected dominating sets
- A Retrospective on (Meta) Kernelization
- Towards a polynomial kernel for directed feedback vertex set
- Towards a polynomial kernel for directed feedback vertex set
- Lossy kernels for connected dominating set on sparse graphs
- Finite integer index of pathwidth and treewidth
- Elimination Distance to Bounded Degree on Planar Graphs
- Characterising bounded expansion by neighbourhood complexity
- scientific article; zbMATH DE number 7559402 (Why is no real title available?)
- Approximation and kernelization for chordal vertex deletion
- On the lossy kernelization for connected treedepth deletion set
- Lossy kernels for connected dominating set on sparse graphs
- Propagation kernels: efficient graph kernels from propagated information
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- scientific article; zbMATH DE number 6784970 (Why is no real title available?)
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- Kernelization using structural parameters on sparse graph classes
- Elimination distance to bounded degree on planar graphs preprint
- On the Parameterized Complexity of Clique Elimination Distance
- On structural parameterizations of the bounded-degree vertex deletion problem
- Graph Kernels: State-of-the-Art and Future Challenges
- Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
- Minimum fill-in of sparse graphs: kernelization and approximation
- Domination above \(r\)-independence: does sparseness help?
- Distributed domination on sparse graph classes
- Cop-width, flip-width and strong colouring numbers
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Turing kernelization for finding long paths in graph classes excluding a topological minor
- Low rank estimation of smooth kernels on graphs
- Alternative parameterizations of \textsc{Metric Dimension}
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Meta-kernelization using well-structured modulators
- Lower bounds for protrusion replacement by counting equivalence classes
- Deep kernel supervised hashing for node classification in structural networks
- Turing kernelization for finding long paths in graphs excluding a topological minor
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- On structural parameterizations of the bounded-degree vertex deletion problem
- scientific article; zbMATH DE number 7764115 (Why is no real title available?)
- Twin-width and polynomial kernels
- Local planar domination revisited
This page was built for publication: Kernelization using structural parameters on sparse graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q340583)
