Reconfiguration on nowhere dense graph classes

摘要: Let $\mathcal{Q}$ be a vertex subset problem on graphs. In reconfiguration variant of we are given graph $G$ and two feasible solutions $S_s, S_t\subseteq V(G)$ with $|S_s|=|S_t|=k$. The is to determine whether there exists sequence $S_1,\ldots,S_n$ solutions, where $S_1=S_s$, $S_n=S_t$, $|S_i|\leq k\pm 1$, each $S_{i+1}$ results from $S_i$, $1\leq i 0$ even obtain kernel almost linear size $\mathcal{O}(k^{1+\epsilon})$. We then prove that if class $\mathcal{C}$ somewhere dense closed under taking subgraphs, for some value $r\geq 1$ the variants above problems $\mathsf{W}[1]$-hard (and in particular cannot expect existence kernelization algorithms). Hence our show limit tractability distance-$r$ independent set dominating subgraph classes lies exactly boundary between nowhere denseness denseness.