Reconfiguration on nowhere dense graph classes (Q1658772)

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