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 graph G and an integer k, constructs a tree-partition of width O(k⁷) for G or reports that G has tree-partition-width more than k, in time k^O(1)n². 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¹⁵)) and show XALP-completeness for the special case where vertices and edges have weight 1.