Solving connectivity problems parameterized by treewidth in single exponential time

Marek Cygan, Jesper Nederlof, Marcin Pilipczuk +3

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. On the other hand,…