Reconfiguration on sparse graphs

A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k, whether it is possible to transform one into the other by a sequence of vertex additions/deletions such that each intermediate set remains a feasible solution of size bounded by k. We study reconfiguration variants of two classical vertex-subset problems, namely Independent Set and Dominating Set. We denote the former by and the latter by . Both and are PSPACE-complete on graphs of bounded bandwidth and W[1]-hard parameterized by k on general graphs. We show that is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere dense. For , we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques.