The Complexity of Induced Tree Reconfiguration Problems

Access this Article

Author(s)

    • YAMANAKA Katsuhisa
    • Department of Systems Innovation Engineering, Faculty of Science and Engineering, Iwate University
    • ARIMURA Hiroki
    • Graduate School of Information Science and Technology, Hokkaido University

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 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.</p>

Journal

  • IEICE Transactions on Information and Systems

    IEICE Transactions on Information and Systems E102.D(3), 464-469, 2019

    The Institute of Electronics, Information and Communication Engineers

Codes

Page Top