The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations
Tree-width and path-width are well-known graph parameters. Many NP-hard graph problems admit 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 transfor...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-06-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/7/386 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849419203298197504 |
|---|---|
| author | Frank Gurski Robin Weishaupt |
| author_facet | Frank Gurski Robin Weishaupt |
| author_sort | Frank Gurski |
| collection | DOAJ |
| description | Tree-width and path-width are well-known graph parameters. Many NP-hard graph problems admit 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. For considered transformations, we provide upper and lower bounds for the tree-width and path-width of the resulting graph in terms of those 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 | Article |
| id | doaj-art-e22ae4a7946a41b8824506c762030042 |
| institution | Kabale University |
| issn | 1999-4893 |
| language | English |
| publishDate | 2025-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj-art-e22ae4a7946a41b8824506c7620300422025-08-20T03:32:12ZengMDPI AGAlgorithms1999-48932025-06-0118738610.3390/a18070386The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph TransformationsFrank Gurski0Robin Weishaupt1Institute of Computer Science, Heinrich Heine University, 40225 Düsseldorf, GermanyInstitute of Computer Science, Heinrich Heine University, 40225 Düsseldorf, GermanyTree-width and path-width are well-known graph parameters. Many NP-hard graph problems admit 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. For considered transformations, we provide upper and lower bounds for the tree-width and path-width of the resulting graph in terms of those 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.https://www.mdpi.com/1999-4893/18/7/386tree-widthpath-widthgraph operationsgraph transformations |
| spellingShingle | Frank Gurski Robin Weishaupt The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations Algorithms tree-width path-width graph operations graph transformations |
| title | The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations |
| title_full | The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations |
| title_fullStr | The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations |
| title_full_unstemmed | The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations |
| title_short | The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations |
| title_sort | behavior of tree width and path width under graph operations and graph transformations |
| topic | tree-width path-width graph operations graph transformations |
| url | https://www.mdpi.com/1999-4893/18/7/386 |
| work_keys_str_mv | AT frankgurski thebehavioroftreewidthandpathwidthundergraphoperationsandgraphtransformations AT robinweishaupt thebehavioroftreewidthandpathwidthundergraphoperationsandgraphtransformations AT frankgurski behavioroftreewidthandpathwidthundergraphoperationsandgraphtransformations AT robinweishaupt behavioroftreewidthandpathwidthundergraphoperationsandgraphtransformations |