Polynomial kernels and wideness properties of nowhere dense graph classes

DOI10.1145/3274652zbMATH Open1454.05064arXiv1608.05637OpenAlexW3160089363WikidataQ128934441 ScholiaQ128934441MaRDI QIDQ4629992FDOQ4629992

Authors: Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz 

Publication date: 28 March 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Abstract: Nowhere dense classes of graphs are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a characterisation of these classes in terms of uniform quasi-wideness, a concept originating in finite model theory, has proved to be particularly useful. Uniform quasi-wideness is used in many fpt-algorithms on nowhere dense classes. However, the existing constructions showing the equivalence of nowhere denseness and uniform quasi-wideness imply a non-elementary blow up in the parameter dependence of the fpt-algorithms, making them infeasible in practice. As a first main result of this paper, we use tools from logic, in particular from a subfield of model theory known as stability theory, to establish polynomial bounds for the equivalence of nowhere denseness and uniform quasi-wideness. A powerful method in parameterized complexity theory is to compute a problem kernel in a pre-computation step, that is, to reduce the input instance in polynomial time to a sub-instance of size bounded in the parameter only (independently of the input graph size). Our new tools allow us to obtain for every fixed value of $r$ a polynomial kernel for the distance-$r$ dominating set problem on nowhere dense classes of graphs. This result is particularly interesting, as it implies that for every class $mathcalC$ of graphs which is closed under subgraphs, the distance-$r$ dominating set problem admits a kernel on $mathcalC$ for every value of $r$ if, and only if, it admits a polynomial kernel for every value of $r$ (under the standard assumption of parameterized complexity theory that $mathrmFPTeqW[2]$).

Full work available at URL: https://arxiv.org/abs/1608.05637

Recommendations

• Polynomial kernels and wideness properties of nowhere dense graph classes
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• Domination problems in nowhere-dense classes of graphs
• Kernelization and Sparseness: the case of Dominating Set
• Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs

zbMATH Keywords

stability theorynowhere densenessgraph structure theoryuniform quasi-wideness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Classification theory, stability, and related concepts in model theory (03C45) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75) Parameterized complexity, tractability and kernelization (68Q27)

Cited In (8)

• Domination problems in nowhere-dense classes of graphs
• Title not available (Why is that?)
• Polynomial kernels and wideness properties of nowhere dense graph classes
• Distributed domination on sparse graph classes
• Harmless sets in sparse classes
• Directed nowhere dense classes of graphs
• Bounds on half graph orders in powers of sparse graphs
• Neighborhood complexity and kernelization for nowhere dense classes of graphs

This page was built for publication: Polynomial kernels and wideness properties of nowhere dense graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629992)