Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth

Abstract

It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2O(tw)nO(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 twO(tw)nO(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 ctwnO(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 ctwnO(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.