Neighborhood complexity and kernelization for nowhere dense classes of graphs

DOI10.4230/LIPICS.ICALP.2017.63MaRDI QIDQ5111394zbMATH OpenFDO

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

Publication date 27 May 2020

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)

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.

Recommendations

• Kernelization and approximation of distance-r independent sets on nowhere dense graphs
• scientific article; zbMATH DE number 409491
• 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

Cited in

(38)

• Coloring and covering nowhere dense graphs
• Domination problems in nowhere-dense classes of graphs
• On the parameterized complexity of reconfiguration of connected dominating sets
• Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
• Data reduction for directed feedback vertex set on graphs without long induced cycles. Three rules to rule them all
• Turbocharging heuristics for weak coloring numbers
• Improved bounds for weak coloring numbers
• Lossy kernels for connected dominating set on sparse graphs
• Reconfiguration on nowhere dense graph classes
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• Lossy kernels for connected dominating set on sparse graphs
• Polynomial kernels and wideness properties of nowhere dense graph classes
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs
• Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
• Erdös-Hajnal properties for powers of sparse graphs
• Progressive algorithms for domination and independence
• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
• Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size
• A survey on the parameterized complexity of reconfiguration problems
• First-order transductions of graphs (invited talk)
• Domination above \(r\)-independence: does sparseness help?
• Distributed domination on sparse graph classes
• Cop-width, flip-width and strong colouring numbers
• Algorithmic properties of sparse digraphs
• Polynomial kernels and wideness properties of nowhere dense graph classes
• Bounding generalized coloring numbers of planar graphs using coin models
• Neighbourhood complexity of graphs of bounded twin-width
• On quasi-planar graphs: clique-width and logical description
• Parameterized aspects of strong subgraph closure
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
• Bounds on half graph orders in powers of sparse graphs
• Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
• Computing complexity measures of degenerate graphs
• Bidimensionality and kernels
• scientific article; zbMATH DE number 7764115 (Why is no real title available?)
• On the generalised colouring numbers of graphs that exclude a fixed minor
• Constant round distributed domination on graph classes with bounded expansion

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)