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.
展开▼
机译：我们证明，只要G是无处密集图类C的图，并且A是G的顶点的子集，则实现为A与G的顶点的r邻居的交集的A的子集的数量为大多数f（r，eps）| A | ^（1 + eps），其中r是任何正整数，eps是任何正实数，并且f是仅取决于类C的函数。这表示无处密集邻域复杂度方面的图类，它回答了[Reidl等人，CoRR，2016]提出的问题。作为上述结果的算法应用，我们表明，对于每个固定整数r，参数化的Distance-r支配集问题都允许在任何稠密图类上使用几乎线性的核。这证明了[Drange et al。，STACS 2016]提出的猜想，并且表明在子图封闭图类上，距离-r支配集的参数化可牵引性的极限正好位于无处密集和某处密集之间的边界上。
展开▼
