TY - GEN
T1 - On the Parameterized Complexity of Computing Tree-Partitions
AU - Bodlaender, Hans L.
AU - Groenland, Carla
AU - Jacob, Hugo
PY - 2022
Y1 - 2022
N2 - 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(k7) for G or reports that G has tree-partition width more than k, in time kO(1)n2. 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. Finally, 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.
AB - 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(k7) for G or reports that G has tree-partition width more than k, in time kO(1)n2. 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. Finally, 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.
KW - Approximation Algorithms
KW - Domino Treewidth
KW - Parameterized algorithms
KW - Parameterized Complexity
KW - Tree partitions
KW - tree-partition-width
KW - Treewidth
UR - https://www.scopus.com/pages/publications/85144207387
U2 - 10.4230/LIPIcs.IPEC.2022.7
DO - 10.4230/LIPIcs.IPEC.2022.7
M3 - Conference contribution
AN - SCOPUS:85144207387
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 17th International Symposium on Parameterized and Exact Computation, IPEC 2022
A2 - Dell, Holger
A2 - Nederlof, Jesper
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 17th International Symposium on Parameterized and Exact Computation, IPEC 2022
Y2 - 7 September 2022 through 9 September 2022
ER -