# Reconfiguration over tree decompositions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2014.

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

- [Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures](https://mlsanity.com/paper/2412.08556/) (2024)

## Abstract (arXiv)

A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. The reconfiguration version of a vertex-subset problem Q asks whether it is possible to transform one feasible solution for Q into another in at most ℓ steps, where each step is a vertex addition or deletion, and each intermediate set is also a feasible solution for Q of size bounded by k. Motivated by recent results establishing W[1]-hardness of the reconfiguration versions of most vertex-subset problems parameterized by ℓ, we investigate the complexity of such problems restricted to graphs of bounded treewidth. We show that the reconfiguration versions of most vertex-subset problems remain PSPACE-complete on graphs of treewidth at most t but are fixed-parameter tractable parameterized by ℓ + t for all vertex-subset problems definable in monadic second-order logic (MSOL). To prove the latter result, we introduce a technique which allows us to circumvent cardinality constraints and define reconfiguration problems in MSOL.