Kernelization using structural parameters on sparse graph classes

DOI10.1016/J.JCSS.2016.09.002zbMATH Open1353.68127arXiv1302.6863OpenAlexW2098564749MaRDI QIDQ340583FDOQ340583

Jakub Gajarský, Sebastian Ordyniak, Somnath Sikdar, Petr Hliněný, Fernando Sánchez Villaamil, Jan Obdržálek, Felix Reidl, Peter Rossmanith

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, $H$-minor-free graphs, and $H$-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 $s,t$-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

zbMATH Keywords

parameterized complexitytree-depthkernelizationfinite integer indexnowhere dense graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Incompressibility through Colors and IDs
• Characterisations and examples of graph classes with bounded expansion
• Title not available (Why is that?)
• (Meta) Kernelization
• Bidimensionality and Geometric Graphs
• 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 Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• 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 (40)

• A Retrospective on (Meta) Kernelization
• On the parameterized complexity of reconfiguration of connected dominating sets
• Title not available (Why is that?)
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs
• Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
• Towards a polynomial kernel for directed feedback vertex set
• Elimination Distance to Bounded Degree on Planar Graphs
• Characterising bounded expansion by neighbourhood complexity
• Title not available (Why is that?)
• On the lossy kernelization for connected treedepth deletion set
• Title not available (Why is that?)
• 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
• Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
• Graph Kernels: State-of-the-Art and Future Challenges
• Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• Minimum fill-in of sparse graphs: kernelization and approximation
• Distributed domination on sparse graph classes
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Title not available (Why is that?)
• Turing kernelization for finding long paths in graph classes excluding a topological minor
• On the number of labeled graphs of bounded treewidth
• Low rank estimation of smooth kernels on graphs
• Alternative parameterizations of \textsc{Metric Dimension}
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
• 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
• Approximation and Kernelization for Chordal Vertex Deletion
• On structural parameterizations of the bounded-degree vertex deletion problem
• Title not available (Why is that?)
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
• 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)