
For FullText 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 Problems
Kunihiro WASA Katsuhisa YAMANAKA Hiroki ARIMURA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E102D
No.3
pp.464469 Publication Date: 2019/03/01 Publicized: 2018/10/30 Online ISSN: 17451361
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, PSPACEcomplete, W[1]hard, FPT,
Full Text: PDF>>
Summary:
Given two feasible solutions A and B, a reconfiguration problem asks whether there exists a reconfiguration sequence (A_{0}=A, A_{1},...,A_{ℓ}=B) such that (i) A_{0},...,A_{ℓ} are feasible solutions and (ii) we can obtain A_{i} from A_{i1} 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 PSPACEcomplete 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.

