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
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: |
|
2017 |
2017
