摘要：Let G be a graph and Tâ,,Tâ,, be two spanning trees of G. We say that Tâ, can be transformed into Tâ,, via an edge flip if there exist two edges e â^^ Tâ, and f in Tâ,, such that Tâ,, = (Tâ,⧵e) â^ª f. Since spanning trees form a matroid, one can indeed transform a spanning tree into any other via a sequence of edge flips, as observed in [Takehiro Ito et al., 2011]. We investigate the problem of determining, given two spanning trees Tâ,,Tâ,, with an additional property Î , if there exists an edge flip transformation from Tâ, to Tâ,, keeping property Î all along. First we show that determining if there exists a transformation from Tâ, to Tâ,, such that all the trees of the sequence have at most k (for any fixed k ⥠3) leaves is PSPACE-complete. We then prove that determining if there exists a transformation from Tâ, to Tâ,, such that all the trees of the sequence have at least k leaves (where k is part of the input) is PSPACE-complete even restricted to split, bipartite or planar graphs. We complete this result by showing that the problem becomes polynomial for cographs, interval graphs and when k = n-2.
