In-Person Talk 

We give a 2^O(k^2) n^O(1) time algorithm for determining if the treewidth of a given n-vertex graph is at most k and outputting the corresponding tree decomposition. This is the first improvement on the dependency on k in fixed-parameter algorithms for treewidth since the 2^O(k^3) n^O(1) time algorithm given in 1991 by Bodlaender-Kloks and Lagergren-Arnborg. We also give a k^O(k/eps) n^O(1) time (1+eps)-approximation algorithm for treewidth. Our algorithms are based on introducing a new variant of treewidth called subset treewidth, showing that parameterized algorithms for subset treewidth imply parameterized algorithms for treewidth, and then giving parameterized algorithms for subset treewidth. 

This is joint work with Daniel Lokshtanov.