{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T14:19:15Z","timestamp":1772893155632,"version":"3.50.1"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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&lt;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\\geq 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 $\\epsilon&gt;0$ we even obtain a kernel of almost linear size $\\mathcal{O}(k^{1+\\epsilon})$.  We then prove that if a class $\\mathcal{C}$ is somewhere dense and closed under taking subgraphs, then for some value of $r\\geq 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 subgraph closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.<\/jats:p>","DOI":"10.37236\/7458","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T10:16:16Z","timestamp":1578651376000},"source":"Crossref","is-referenced-by-count":6,"title":["Reconfiguration on Nowhere Dense Graph Classes"],"prefix":"10.37236","volume":"25","author":[{"given":"Sebastian","family":"Siebertz","sequence":"first","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2018,8,10]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v25i3p24\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v25i3p24\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T23:29:45Z","timestamp":1579217385000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v25i3p24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,10]]},"references-count":0,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2018,7,12]]}},"URL":"https:\/\/doi.org\/10.37236\/7458","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,10]]},"article-number":"P3.24"}}