On the parameterized complexity of computing tree-partitions
We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obtain approximations of the tree-partition-width efficiently: we show that there is an algorithm that, given an $n$-vertex...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2025-02-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/12540/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849344656940204032 |
|---|---|
| author | Hans L. Bodlaender Carla Groenland Hugo Jacob |
| author_facet | Hans L. Bodlaender Carla Groenland Hugo Jacob |
| author_sort | Hans L. Bodlaender |
| collection | DOAJ |
| description | We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obtain approximations of the tree-partition-width efficiently: we show that there is an algorithm that, given an $n$-vertex graph $G$ and an integer $k$, constructs a tree-partition of width $O(k^7)$ for $G$ or reports that $G$ has tree-partition-width more than $k$, in time $k^{O(1)}n^2$. We can improve slightly on the approximation factor by sacrificing the dependence on $k$, or on $n$. On the other hand, we show the problem of computing tree-partition-width exactly is XALP-complete, which implies that it is $W[t]$-hard for all $t$. We deduce XALP-completeness of the problem of computing the domino treewidth. Next, we adapt some known results on the parameter tree-partition-width and the topological minor relation, and use them to compare tree-partition-width to tree-cut width. Finally, for the related parameter weighted tree-partition-width, we give a similar approximation algorithm (with ratio now $O(k^{15})$) and show XALP-completeness for the special case where vertices and edges have weight 1. |
| format | Article |
| id | doaj-art-8750a6fe844e48d9b4c5b8dca7a46e5b |
| institution | Kabale University |
| issn | 1365-8050 |
| language | English |
| publishDate | 2025-02-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-8750a6fe844e48d9b4c5b8dca7a46e5b2025-08-20T03:42:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502025-02-01vol. 26:3Discrete Algorithms10.46298/dmtcs.1254012540On the parameterized complexity of computing tree-partitionsHans L. BodlaenderCarla GroenlandHugo JacobWe study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obtain approximations of the tree-partition-width efficiently: we show that there is an algorithm that, given an $n$-vertex graph $G$ and an integer $k$, constructs a tree-partition of width $O(k^7)$ for $G$ or reports that $G$ has tree-partition-width more than $k$, in time $k^{O(1)}n^2$. We can improve slightly on the approximation factor by sacrificing the dependence on $k$, or on $n$. On the other hand, we show the problem of computing tree-partition-width exactly is XALP-complete, which implies that it is $W[t]$-hard for all $t$. We deduce XALP-completeness of the problem of computing the domino treewidth. Next, we adapt some known results on the parameter tree-partition-width and the topological minor relation, and use them to compare tree-partition-width to tree-cut width. Finally, for the related parameter weighted tree-partition-width, we give a similar approximation algorithm (with ratio now $O(k^{15})$) and show XALP-completeness for the special case where vertices and edges have weight 1.http://dmtcs.episciences.org/12540/pdfcomputer science - discrete mathematics |
| spellingShingle | Hans L. Bodlaender Carla Groenland Hugo Jacob On the parameterized complexity of computing tree-partitions Discrete Mathematics & Theoretical Computer Science computer science - discrete mathematics |
| title | On the parameterized complexity of computing tree-partitions |
| title_full | On the parameterized complexity of computing tree-partitions |
| title_fullStr | On the parameterized complexity of computing tree-partitions |
| title_full_unstemmed | On the parameterized complexity of computing tree-partitions |
| title_short | On the parameterized complexity of computing tree-partitions |
| title_sort | on the parameterized complexity of computing tree partitions |
| topic | computer science - discrete mathematics |
| url | http://dmtcs.episciences.org/12540/pdf |
| work_keys_str_mv | AT hanslbodlaender ontheparameterizedcomplexityofcomputingtreepartitions AT carlagroenland ontheparameterizedcomplexityofcomputingtreepartitions AT hugojacob ontheparameterizedcomplexityofcomputingtreepartitions |