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
- (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
- 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?)
- 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
(45)- Characterising bounded expansion by neighbourhood complexity
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Twin-width and polynomial kernels
- Local planar domination revisited
- Lower bounds for protrusion replacement by counting equivalence classes
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- On structural parameterizations of the bounded-degree vertex deletion problem
- Turing kernelization for finding long paths in graph classes excluding a topological minor
- 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
- Towards a polynomial kernel for directed feedback vertex set
- Kernelization using structural parameters on sparse graph classes
- Minimum fill-in of sparse graphs: kernelization and approximation
- Finite integer index of pathwidth and treewidth
- Propagation kernels: efficient graph kernels from propagated information
- Lossy kernels for connected dominating set on sparse graphs
- On structural parameterizations of the bounded-degree vertex deletion problem
- Low rank estimation of smooth kernels on graphs
- Approximation and kernelization for chordal vertex deletion
- Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
- A Retrospective on (Meta) Kernelization
- scientific article; zbMATH DE number 7559402 (Why is no real title available?)
- Elimination Distance to Bounded Degree on Planar Graphs
- Domination above \(r\)-independence: does sparseness help?
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Towards a polynomial kernel for directed feedback vertex set
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Turing kernelization for finding long paths in graphs excluding a topological minor
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- Lossy kernels for connected dominating set on sparse graphs
- scientific article; zbMATH DE number 6784970 (Why is no real title available?)
- Graph Kernels: State-of-the-Art and Future Challenges
- On the lossy kernelization for connected treedepth deletion set
- On the Parameterized Complexity of Clique Elimination Distance
- scientific article; zbMATH DE number 7764115 (Why is no real title available?)
- Deep kernel supervised hashing for node classification in structural networks
- Elimination distance to bounded degree on planar graphs preprint
- Distributed domination on sparse graph classes
- Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
- Cop-width, flip-width and strong colouring numbers
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- First-order transductions of graphs (invited talk)
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- On the parameterized complexity of reconfiguration of connected dominating sets
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)
