For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 The Complexity of Induced Tree Reconfiguration ProblemsKunihiro WASA  Katsuhisa YAMANAKA  Hiroki ARIMURA  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.464-469Publication 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.