论文标题
关于计算树的参数复杂性
On the parameterized complexity of computing tree-partitions
论文作者
论文摘要
我们研究了计算树差宽度的参数化复杂性，这是一个等效于界限最大程度图上的treewidth的图参数。 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$.我们可以通过牺牲对$ k $或$ n $的依赖性来稍微改善近似因素。另一方面，我们显示了计算树零宽度的问题，这是Xalp-complete，这意味着对于所有$ t $来说都是$ w [t] $ - 很难。我们推断出计算多米诺树宽的问题的XALP完整性。接下来，我们将一些已知的结果调整在参数树的宽度和拓扑次要的关系上，并使用它们将树零宽度与树切宽度进行比较。最后，对于相关的参数加权树差宽，我们给出了类似的近似算法（现在比率为$ o（k^{15}）$），并显示特殊情况下的XALP-兼容性，在该特殊情况下，顶点和边缘具有权重1。
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.
