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