Snakes and Ladders: a Treewidth Story
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929227652136960 |
|---|---|
| author | Chaplick, Steven Kelk, Steven Meuwese, Ruben Mihalak, Matus Stamoulis, Georgios |
| author_facet | Chaplick, Steven Kelk, Steven Meuwese, Ruben Mihalak, Matus Stamoulis, Georgios |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_10662 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Snakes and Ladders: a Treewidth Story Chaplick, Steven Kelk, Steven Meuwese, Ruben Mihalak, Matus Stamoulis, Georgios Combinatorics Data Structures and Algorithms 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. |
| title | Snakes and Ladders: a Treewidth Story |
| topic | Combinatorics Data Structures and Algorithms Populations and Evolution |
| url | https://arxiv.org/abs/2302.10662 |