Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
For the vast majority of local problems on graphs of small tree width (where by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c^tw |V|^O(1) time algorithms, where tw is the tree width of the input …