The Complexity of Induced Tree Reconfiguration Problems
Access this Article
Author(s)
Abstract
<p>Given two feasible solutions <i>A</i> and <i>B</i>, a <i>reconfiguration problem</i> asks whether there exists a <i>reconfiguration sequence</i> (<i>A</i><sub>0</sub>=<i>A</i>, <i>A</i><sub>1</sub>,...,<i>A</i><sub>ℓ</sub>=<i>B</i>) such that (i) <i>A</i><sub>0</sub>,...,<i>A</i><sub>ℓ</sub> are feasible solutions and (ii) we can obtain <i>A<sub>i</sub></i> from <i>A</i><sub><i>i</i>1</sub> under the prescribed rule (the <i>reconfiguration rule</i>) for each <i>i</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 <i>u</i> from an induced tree and adding <i>v</i> to the tree, and Token Sliding: removing <i>u</i> from an induced tree and adding <i>v</i> adjacent to <i>u</i> to the tree, where <i>u</i> and <i>v</i> 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.</p>
Journal

 IEICE Transactions on Information and Systems

IEICE Transactions on Information and Systems E102.D(3), 464469, 2019
The Institute of Electronics, Information and Communication Engineers