An Improved Parameterized Algorithm for Treewidth

We give an algorithm that takes as input an n-vertex graph G and an integer k, runs in time 2O(k2) nO(1), and outputs a tree decomposition of G of width at most k, if such a decomposition exists. This resolves the long-standing open problem of whether there is a 2o(k3) nO(1) time algorithm for treewidth. In particular, our algorithm is the first improvement on the dependency on k in algorithms for treewidth since the 2O(k3) nO(1) time algorithm given by Bodlaender and Kloks [ICALP 1991] and Lagergren and Arnborg [ICALP 1991].