For the vast majority of local graph problems standard dynamic programming techniques give c^tw |V|^O(1) algorithms, where tw is the treewidth of the input graph, for some constant c. On the other hand, for problems with a global requirement like Hamiltonicity the best-known algorithms were naive dynamic programming schemes running in tw^O(tw) |V|^O(1) time.
We breach this gap by introducing a technique we named Cut&Count that allows to produce c^tw |V|^O(1) Monte Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Feedback Vertex Set and Connected Dominating Set. The constant c we obtain is in all cases small (at most 4 for undirected problems and at most 6 for directed ones). Our results have consequences in various fields, like FPT algorithms, exact and approximate algorithms on planar and H-minor-free graphs and algorithms on graphs of bounded degree. In particular we show 3^k and 2^k parameterized Monte Carlo algorithms for Feedback Vertex Set and Connected Vertex Cover problems respectively, when parameterized by the solution size.
The results are based on joint work with Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M.M. van Rooij and Jakub Onufry Wojtaszczyk. To appear in FOCS 2011.