Reconfiguration of Steiner Trees in an Unweighted Graph
Haruka Mizuta, Takehiro Ito, Xiao Zhou · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2017
We study a reconfiguration problem for Steiner trees in an unweighted graph, which determines whether there exists a sequence of Steiner trees that transforms a given Steiner tree into another one by exchanging a single edge at a time. In this paper, we show that the problem is PSPACE-complete even for split graphs, while solvable in linear time for interval graphs and for cographs.