Kernelization using structural parameters on sparse graph classes
From MaRDI portal
Publication:340583
DOI10.1016/J.JCSS.2016.09.002zbMATH Open1353.68127arXiv1302.6863OpenAlexW2098564749MaRDI QIDQ340583FDOQ340583
Authors: Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar 
Publication date: 14 November 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
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).
Full work available at URL: https://arxiv.org/abs/1302.6863
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Graph theory
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- On problems without polynomial kernels
- Grad and classes with bounded expansion. I: Decompositions
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Hitting forbidden minors: approximation and kernelization
- Incompressibility through Colors and IDs
- Characterisations and examples of graph classes with bounded expansion
- Title not available (Why is that?)
- (Meta) Kernelization
- Bidimensionality and kernels
- Sparsity. Graphs, structures, and algorithms
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Cluster vertex deletion: a parameterization between vertex cover and clique-width
- Polynomial-time data reduction for dominating set
- Graph Layout Problems Parameterized by Vertex Cover
- Title not available (Why is that?)
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- On the maximum number of cliques in a graph
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- On the excluded minors for the matroids of branch-width \(k\)
- On nowhere dense graphs
- On the hardness of losing width
- The branchwidth of graphs and their cycle matroids
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Kernel bounds for path and cycle problems
- Linear time low tree-width partitions and algorithmic consequences
- Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Title not available (Why is that?)
- Kernelization and Sparseness: the case of Dominating Set
- On cutwidth parameterized by vertex cover
- First order properties on nowhere dense structures
Cited In (42)
- A Retrospective on (Meta) Kernelization
- On the parameterized complexity of reconfiguration of connected dominating sets
- 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
- Title not available (Why is that?)
- Approximation and kernelization for chordal vertex deletion
- On the lossy kernelization for connected treedepth deletion set
- Title not available (Why is that?)
- Lossy kernels for connected dominating set on sparse graphs
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Elimination distance to bounded degree on planar graphs preprint
- Propagation kernels: efficient graph kernels from propagated information
- On the Parameterized Complexity of Clique Elimination Distance
- Kernelization using structural parameters on sparse graph classes
- 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
- Distributed domination on sparse graph classes
- Domination above \(r\)-independence: does sparseness help?
- 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
- On the number of labeled graphs of bounded treewidth
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Low rank estimation of smooth kernels on graphs
- Alternative parameterizations of \textsc{Metric Dimension}
- 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
- On structural parameterizations of the bounded-degree vertex deletion problem
- Title not available (Why is that?)
- Twin-width and polynomial kernels
- Local planar domination revisited
- Reconfiguration on 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)
