2020/06/25 by Nicolas Bousquet, Bousquet, Nicolas, Takehiro Ito +11 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.2006.14309
32 pages, 8 figures
arxiv created 2020/06/25 · arxiv updated 2020/06/26
Let G be a graph and T1,T2 be two spanning trees of G. We say that T1 can be transformed into T2 via an edge flip if there exist two edges e ∈ T1 and f in T2 such that T2= (T1 ∖ 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 by Ito et al. We investigate the problem of determining, given two spanning trees T1,T2 with an additional property Π, if there exists an edge flip transformation from T1 to T2 keeping property Π all along. First we show that determining if there exists a transformation from T1 to T2 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 T1 to T2 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.