Lossy kernels for connected distance-$r$ domination on nowhere dense graph classes

摘要: For $\alpha\colon\mathbb{N}\rightarrow\mathbb{R}$, an $\alpha$-approximate bi-kernel is a polynomial-time algorithm that takes as input instance $(I, k)$ of problem $Q$ and outputs $(I',k')$ $Q'$ size bounded by function $k$ such that, for every $c\geq 1$, $c$-approximate solution the new can be turned into $c\cdot\alpha(k)$-approximate original in polynomial time. This framework \emph{lossy kernelization} was recently introduced Lokshtanov et al. We prove nowhere dense class graphs, $\alpha>1$ $r\in\mathbb{N}$ there exists $p$ (whose degree depends only on $r$ while its coefficients depend $\alpha$) connected distance-$r$ dominating set with parameter admits $p(k)$. Furthermore, we show this result cannot extended to more general classes graphs which are closed under taking subgraphs showing if $C$ somewhere subgraphs, then some value exist (connected) any $\alpha\colon\mathbb{N}\rightarrow\mathbb{R}$ (assuming Gap Exponential Time Hypothesis).