论文标题
快速算法以加入树木分解的操作
Fast Algorithms for Join Operations on Tree Decompositions
论文作者
论文摘要
树宽是对图的方式的度量。它具有许多重要的算法应用程序，因为当一般图上的许多NP硬性问题限制在有界树宽的图表时。在界图上的问题上的问题算法主要是使用图形分解的结构动态编程算法。这些算法最差的运行时间中的瓶颈通常是对相关的好树分解中所谓的联接节点的计算。 在本文中，我们回顾了有关联接节点计算的文献中出现的两种不同的方法：一种使用快速Zeta和Möbius变换，另一种使用快速的傅立叶变换。我们结合了这些方法，以获取一类称为[σ，ρ]域问题的广泛顶点子集问题的新算法。 我们的主要结果是我们在$ O（s^{t+2} t n^2（t \ log（s）+\ log（n）））$ arithmetic操作中展示了如何求解[σ，ρ]域问题。在这里，t是树宽，s是表示特定[σ，ρ] - 域问题的部分解决方案所需的（固定）状态数，而n是图中的顶点数量。与以前最佳的时间绑定（van rooij，bodlaender，Rossmanith，ESA 2009）相比，这降低了涉及的多项式因素。特别是，这消除了多项式对固定数量〜$ s $的依赖性。
Treewidth is a measure of how tree-like a graph is. It has many important algorithmic applications because many NP-hard problems on general graphs become tractable when restricted to graphs of bounded treewidth. Algorithms for problems on graphs of bounded treewidth mostly are dynamic programming algorithms using the structure of a tree decomposition of the graph. The bottleneck in the worst-case run time of these algorithms often is the computations for the so called join nodes in the associated nice tree decomposition. In this paper, we review two different approaches that have appeared in the literature about computations for the join nodes: one using fast zeta and Möbius transforms and one using fast Fourier transforms. We combine these approaches to obtain new, faster algorithms for a broad class of vertex subset problems known as the [σ,ρ]-domination problems. Our main result is that we show how to solve [σ,ρ]-domination problems in $O(s^{t+2} t n^2 (t\log(s)+\log(n)))$ arithmetic operations. Here, t is the treewidth, s is the (fixed) number of states required to represent partial solutions of the specific [σ,ρ]-domination problem, and n is the number of vertices in the graph. This reduces the polynomial factors involved compared to the previously best time bound (van Rooij, Bodlaender, Rossmanith, ESA 2009) of $O( s^{t+2} (st)^{2(s-2)} n^3 )$ arithmetic operations. In particular, this removes the dependence of the degree of the polynomial on the fixed number of states~$s$.
