2026-07-20T07:32:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7428 2024-03-06T10:40:24Z ddc:004 open_access

Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs Eickmeyer, Kord Giannopoulou, Archontia C. Kreutzer, Stephan Kwon, O-joung Pilipczuk, Michal Rabinovich, Roman Siebertz, Sebastian Graph Structure Theory Nowhere Dense Graphs Parameterized Complexity Kernelization Dominating Set We prove that whenever G is a graph from a nowhere dense graph class C, 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,eps)|A|^(1+eps), where r is any positive integer, eps is any positive real, and f is a function that depends only on the class C. This yields a characterization of nowhere dense classes of graphs in terms of neighborhood complexity, which answers a question posed by [Reidl et al., CoRR, 2016]. As an algorithmic application of the above result, we show that for every fixed integer 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., STACS 2016], 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kord Eickmeyer and Archontia C. Giannopoulou and Stephan Kreutzer and O-joung Kwon and Michal Pilipczuk and Roman Rabinovich and Sebastian Siebertz 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.63 urn:nbn:de:0030-drops-74288 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.63 eng https://creativecommons.org/licenses/by/3.0/legalcode