It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2~(O(tw))n~(O(1)) time for graphs with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time it was unknown how to do this faster than tw~(O(tw))n~(O(1)) until recently, when Cygan et al. (FOCS 2011) introduced the Cut&Count technique that gives randomized algorithms for a wide range of connectivity problems running in time c~(tw)n~(O(1)) for a small constant c. In this paper, we show that we can improve upon the Cut&Count technique in multiple ways, with two new techniques. The first technique (rank-based approach) gives deterministic algorithms with O(c~(tw)n) running time for connectivity problems (like Hamiltonian Cycle and Stei-ner Tree) and for weighted variants of these; the second technique (determinant approach) gives deterministic algorithms running in time c~(tw)n~(O(1)) for counting versions, e.g., counting the number of Hamiltonian cycles for graphs of treewidth tw. The rank-based approach introduces a new technique to speed up dynamic programming algorithms which is likely to have more 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.
展开▼
