تقرير
Snakes and Ladders: a Treewidth Story
| العنوان: | Snakes and Ladders: a Treewidth Story |
|---|---|
| المؤلفون: | Chaplick, Steven, Kelk, Steven, Meuwese, Ruben, Mihalak, Matus, Stamoulis, Georgios |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics Quantitative Biology |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Data Structures and Algorithms, Quantitative Biology - Populations and Evolution |
| الوصف: | 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. Comment: Compared to the earlier arXiv/WG version we have added analytical (as opposed to empirical) tightness bounds, and an extended discussion. See also Authors note 2 at the end of the introduction about earlier work in this area by Marchand et al |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2302.10662 |
| رقم الأكسشن: | edsarx.2302.10662 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |