论文标题
与许多或几片叶子的跨越树的重新配置
Reconfiguration of Spanning Trees with Many or Few Leaves
论文作者
论文摘要
令$ g $为图形，$ t_1，t_2 $是$ g $的两跨树。我们说，如果在t_1 $中存在两个边缘$ e \，则可以通过边缘翻转将$ t_1 $转换为$ t_2 $，而$ t_2 $中的$ f $，这样$ t_2 =（t_1 \ setMinus e）\ cup f $。由于跨越树形成了成曲线，因此确实可以通过一系列边缘翻转将生成树转化为其他树，如Ito等人所观察到的那样。 我们研究了确定的问题，如果存在额外的属性$π$，如果存在边缘翻转转换，从$ t_1 $到$ t_2 $保持属性$π$。 首先，我们证明确定是否存在从$ t_1 $到$ t_2 $的转换，使得该序列的所有树最多都有$ k $（对于任何固定的$ k \ ge 3 $）叶子是pspace-complete。 然后，我们证明确定是否存在从$ t_1 $到$ t_2 $的转换，使得序列的所有树都至少具有$ k $叶子（其中$ k $是输入的一部分），甚至限制在pspace-complete中，甚至限制在拆分，两部分或平面图中。我们通过证明问题成为cographs，间隔图以及$ k = n-2 $的多项式来完成此结果。
Let $G$ be a graph and $T_1,T_2$ be two spanning trees of $G$. We say that $T_1$ can be transformed into $T_2$ via an edge flip if there exist two edges $e \in T_1$ and $f$ in $T_2$ such that $T_2= (T_1 \setminus e) \cup 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 $T_1,T_2$ with an additional property $Π$, if there exists an edge flip transformation from $T_1$ to $T_2$ keeping property $Π$ all along. First we show that determining if there exists a transformation from $T_1$ to $T_2$ such that all the trees of the sequence have at most $k$ (for any fixed $k \ge 3$) leaves is PSPACE-complete. We then prove that determining if there exists a transformation from $T_1$ to $T_2$ 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$.
