The Behavior of Tree-Width and Path-Width under Graph Operations and Graph Transformations
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917692724740096 |
|---|---|
| author | Gurski, Frank Weishaupt, Robin |
| author_facet | Gurski, Frank Weishaupt, Robin |
| contents | Tree-width and path-width are well-known graph parameters. Many NP-hard graph problems allow polynomial-time solutions, when restricted to graphs of bounded tree-width or bounded path-width. In this work, we study the behavior of tree-width and path-width under various unary and binary graph transformations. Doing so, for considered transformations we provide upper and lower bounds for the tree-width and path-width of the resulting graph in terms of the tree-width and path-width of the initial graphs or argue why such bounds are impossible to specify. Among the studied, unary transformations are vertex addition, vertex deletion, edge addition, edge deletion, subgraphs, vertex identification, edge contraction, edge subdivision, minors, powers of graphs, line graphs, edge complements, local complements, Seidel switching, and Seidel complementation. Among the studied, binary transformations we consider the disjoint union, join, union, substitution, graph product, 1-sum, and corona of two graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_08985 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Behavior of Tree-Width and Path-Width under Graph Operations and Graph Transformations Gurski, Frank Weishaupt, Robin Data Structures and Algorithms 05C76, 68R10 Tree-width and path-width are well-known graph parameters. Many NP-hard graph problems allow polynomial-time solutions, when restricted to graphs of bounded tree-width or bounded path-width. In this work, we study the behavior of tree-width and path-width under various unary and binary graph transformations. Doing so, for considered transformations we provide upper and lower bounds for the tree-width and path-width of the resulting graph in terms of the tree-width and path-width of the initial graphs or argue why such bounds are impossible to specify. Among the studied, unary transformations are vertex addition, vertex deletion, edge addition, edge deletion, subgraphs, vertex identification, edge contraction, edge subdivision, minors, powers of graphs, line graphs, edge complements, local complements, Seidel switching, and Seidel complementation. Among the studied, binary transformations we consider the disjoint union, join, union, substitution, graph product, 1-sum, and corona of two graphs. |
| title | The Behavior of Tree-Width and Path-Width under Graph Operations and Graph Transformations |
| topic | Data Structures and Algorithms 05C76, 68R10 |
| url | https://arxiv.org/abs/2406.08985 |