2014/05/10 by Mouawad, Amer E., Nishimura, Naomi, Raman, Venkatesh +1 · 2 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1405.2447
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.