Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time
Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time
复制标题
在单指数时间内确定性地解决由树宽参数化的连接问题的加权和计数变体
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Jesper Nederlof
中科院分区：
文献类型：
--
作者：
H. Bodlaender;Marek Cygan;Stefan Kratsch;Jesper Nederlof
众所周知，对于给定宽度为tw的树分解图G=(V，E)，许多局部图问题，如顶点覆盖和支配集，可以在2^{O(tw)}|V|^{O(1)}时间内解决。然而，对于非局部问题，比如连通性问题的基本类，很长一段时间我们都不知道如何比tw^{O(tw)}|V|^{O(1)}更快地做到这一点。最近，Cygan等人（FOCS 2011）提出了蒙特卡罗算法，用于处理时间$c^{tw}|V|^{O(1)}对于一个小常数c，例如哈密顿循环和斯坦纳树。自然地，这就提出了一个问题，即随机化对于实现这一运行时间是否必要；此外，还需要解决计数和加权版本（后者不会在权重方面产生伪多项式代价）。
It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2^{O(tw)}|V|^{O(1)} time for graphs G=(V,E) with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time we did not know how to do this faster than tw^{O(tw)}|V|^{O(1)}. Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time $c^{tw}|V|^{O(1)} for a small constant c, e.g., for Hamiltonian Cycle and Steiner tree. Naturally, this raises the question whether randomization is necessary to achieve this runtime; furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in terms of the weights).
We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic c^{tw}|V|^{O(1)} time algorithms, also for weighted and counting versions. For example, in this time we can solve the traveling salesman problem or count the number of Hamiltonian cycles. The rank-based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying "small" sets of representative partial solutions; we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further applications. The determinant-based approach uses the matrix tree theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.