Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth

It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in \(2^{\mathcal{O}(\mathtt{tw})}n^{\mathcal{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 \(\mathtt{tw}^{\mathcal{O}(\mathtt{tw})}n^{\mathcal{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^{\mathtt{tw}}n^{\mathcal{O}(1)}\) for a small constant c.