License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7428/
Go to the corresponding LIPIcs Volume Portal

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:
LIPIcs-ICALP-2017-63.pdf (0.6 MB)

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
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI