# Reconfiguration on sparse graphs

arXiv: https://arxiv.org/abs/1502.04803 · HTML: https://mlsanity.com/paper/1502.04803/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2015.

## Built on by (most cited first, 1 of 1)

- [Reconfiguring Shortest Paths in Graphs](https://mlsanity.com/paper/2112.07499/) (2021)

## Abstract (arXiv)

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 S and T of size k, whether it is possible to transform S into T by a sequence of vertex additions and deletions such that each intermediate set is also 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 ISR and the latter by DSR. Both ISR and DSR are PSPACE-complete on graphs of bounded bandwidth and W[1]-hard parameterized by k on general graphs. We show that ISR is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere-dense. As a corollary, we answer positively an open question concerning the parameterized complexity of the problem on graphs of bounded treewidth. Moreover, our techniques generalize recent results showing that ISR is fixed-parameter tractable on planar graphs and graphs of bounded degree. For DSR, we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques, a class of graphs which includes graphs of bounded degeneracy and nowhere-dense graphs.