The treewidth of a graph intuitively resembles how 'treelike' its global structure is. For the vast majority of local graph problems
(local in the sense that a solution can be verified by checking separately the neighbourhood of each vertex) on graphs of small
treewidth, standard dynamic programming techniques give c^t |V|^{O(1)} time algorithms, where tw is the treewidth of the input graph
G=(V,E) and c is a constant.

In this talk we will see that for some non-local graph problems the same can be achieved by transforming them to local graph counting
problems using randomization and the power of modulo 2. In particular we will see how to solve the Steiner Tree problem in 3^tw
randomized time. The approach extends to many other connectivity problems such as for example Hamiltonian Path and Connected
Dominating Set.

Joint work with: Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Johan van Rooij and Jakub Onufry Wojtaszczyk