Let $G$ be an undirected graph. We say that $G$ contains a ladder of length $k$ if the $2 \times (k+1)$ grid graph is an induced subgraph of $G$ that is only connected to the rest of $G$ via its four cornerpoints. We prove that if all the ladders contained in $G$ are reduced to length 4, the treewidth remains unchanged (and that this bound is tight). Our result indicates that, when computing the treewidth of a graph, long ladders can simply be reduced, and that minimal forbidden minors for bounded treewidth graphs cannot contain long ladders. Our result also settles an open problem from algorithmic phylogenetics: the common chain reduction rule, used to simplify the comparison of two evolutionary trees, is treewidth-preserving in the display graph of the two trees.
翻译:让$G$变成一个非方向图。 我们说$G$包含一个长度为$k美元的梯子。 如果 2 美元时间( k+1) 的网格图是一个只通过其四个角点连接到其余的$G$的诱导子图, 它只能通过四个角点连接到其余的$G$。 我们证明,如果$G$中包含的所有梯子都缩到4长, 树枝保持不变( 并且这个绳子很紧 ) 。 我们的结果表明, 当计算一个图的树枝时, 长梯子可以简单地减少, 并且被捆绑的树枝图中最禁止的未成年人不能包含长梯子。 我们的结果也解决了算法上的植物遗传学上的一个公开问题: 用于简化两种进化树比较的普通链条规则, 在两棵树的显示图中保存树枝线。