Kernelization and Sparseness: the case of Dominating Set

摘要: We prove that for every positive integer $r$ and graph class $\mathcal G$ of bounded expansion, the $r$-Dominating Set problem admits a linear kernel on graphs from G$. Moreover, when is only assumed to be nowhere dense, then we give an almost classic Dominating problem, i.e., case $r=1$. These results generalize line previous research finding kernels Set. However, approach taken in this work, which based theory sparse graphs, radically different conceptually much simpler than approaches. We complement our findings by showing closely related Connected existence such kernelization algorithms unlikely, even though known admit $H$-topological-minor-free graphs. Also, any somewhere dense G$, there some W[$2$]-hard Thus, fall short proving sharp dichotomy parameterized complexity subgraph-monotone classes: conjecture border tractability lies exactly between classes.