Neighborhood complexity and kernelization for nowhere dense classes of graphs

DOI10.4230/LIPICS.ICALP.2017.63zbMATH Open1441.68176arXiv1612.08197MaRDI QIDQ5111394FDOQ5111394

Roman Rabinovich, Kord Eickmeyer, Michał Pilipczuk, Sebastian Siebertz, Stephan Kreutzer, Archontia C. Giannopoulou, O-joung Kwon

Publication date: 27 May 2020

Abstract: We prove that whenever $G$ is a graph from a nowhere dense graph class $mathcalC$, and $A$ is a subset of vertices of $G$, then the number of subsets of $A$ that are realized as intersections of $A$ with $r$-neighborhoods of vertices of $G$ is at most $f(r,epsilon)cdot|A{|}^{1+epsilon}$, where $r$ is any positive integer, $epsilon$ is any positive real, and $f$ is a function that depends only on the class $mathcalC$. This yields a characterization of nowhere dense classes of graphs in terms of neighborhood complexity, which answers a question posed by Reidl et al. As an algorithmic application of the above result, we show that for every fixed $r$, the parameterized Distance-$r$ Dominating Set problem admits an almost linear kernel on any nowhere dense graph class. This proves a conjecture posed by Drange et al., and shows that the limit of parameterized tractability of Distance-$r$ Dominating Set on subgraph-closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.

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

zbMATH Keywords

dominating setparameterized complexitykernelizationnowhere dense graphsgraph structure theory

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75) Parameterized complexity, tractability and kernelization (68Q27)

Cited In (25)

• Erdös--Hajnal Properties for Powers of Sparse Graphs
• On the parameterized complexity of reconfiguration of connected dominating sets
• Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
• Title not available (Why is that?)
• Improved bounds for weak coloring numbers
• Title not available (Why is that?)
• Reconfiguration on nowhere dense graph classes
• Bidimensionality and Kernels
• Title not available (Why is that?)
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
• Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• Distributed domination on sparse graph classes
• Coloring and Covering Nowhere Dense Graphs
• Bounding generalized coloring numbers of planar graphs using coin models
• Neighbourhood complexity of graphs of bounded twin-width
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• On quasi-planar graphs: clique-width and logical description
• Bounds on half graph orders in powers of sparse graphs
• Title not available (Why is that?)
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
• Title not available (Why is that?)
• On the generalised colouring numbers of graphs that exclude a fixed minor
• Constant round distributed domination on graph classes with bounded expansion

   Recommendations

• Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes 👍 👎
• Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes 👍 👎
• On nowhere dense graphs 👍 👎
• Nowhere dense graph classes and dimension 👍 👎
• The neighborhood complex of a random graph 👍 👎
• Graph classes with structured neighborhoods and algorithmic applications 👍 👎
• Graph classes with structured neighborhoods and algorithmic applications 👍 👎
• The neighborhood complexes of almost \(s\)-stable Kneser graphs 👍 👎

This page was built for publication: Neighborhood complexity and kernelization for nowhere dense classes of graphs

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