The Complexity of Induced Tree Reconfiguration Problems

Kunihiro WASA  Katsuhisa YAMANAKA  Hiroki ARIMURA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.464-469
Publication Date: 2019/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018FCP0010
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Category: 
Keyword: 
reconfiguration problem,  induced trees,  PSPACE-complete,  W[1]-hard,  FPT,  

Full Text: PDF(393.6KB)
>>Buy this Article


Summary: 
Given two feasible solutions A and B, a reconfiguration problem asks whether there exists a reconfiguration sequence (A0=A, A1,...,A=B) such that (i) A0,...,A are feasible solutions and (ii) we can obtain Ai from Ai-1 under the prescribed rule (the reconfiguration rule) for each i ∈ {1,...,ℓ}. In this paper, we address the reconfiguration problem for induced trees, where an induced tree is a connected and acyclic induced subgraph of an input graph. We consider the following two rules as the prescribed rules: Token Jumping: removing u from an induced tree and adding v to the tree, and Token Sliding: removing u from an induced tree and adding v adjacent to u to the tree, where u and v are vertices of an input graph. As the main results, we show that (I) the reconfiguration problemis PSPACE-complete even if the input graph is of bounded maximum degree, (II) the reconfiguration problem is W[1]-hard when parameterized by both the size of induced trees and the length of the reconfiguration sequence, and (III) there exists an FPT algorithm when the problem is parameterized by both the size of induced trees and the maximum degree of an input graph under Token Jumping and Token Sliding.