  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.
