Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.63
URN: urn:nbn:de:0030-drops-74288
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7428/
Eickmeyer, Kord ; Giannopoulou, Archontia C. ; Kreutzer, Stephan ; Kwon, O-joung ; Pilipczuk, Michal ; Rabinovich, Roman ; Siebertz, Sebastian
Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{eickmeyer_et_al:LIPIcs:2017:7428,
author = {Kord Eickmeyer and Archontia C. Giannopoulou and Stephan Kreutzer and O-joung Kwon and Michal Pilipczuk and Roman Rabinovich and Sebastian Siebertz},
title = {{Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {63:1--63:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7428},
URN = {urn:nbn:de:0030-drops-74288},
doi = {10.4230/LIPIcs.ICALP.2017.63},
annote = {Keywords: Graph Structure Theory, Nowhere Dense Graphs, Parameterized Complexity, Kernelization, Dominating Set}
}
| Keywords: | Graph Structure Theory, Nowhere Dense Graphs, Parameterized Complexity, Kernelization, Dominating Set | |
| Seminar: | 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 07.07.2017 |
