A Single-Exponential Time 2-Approximation Algorithm for Treewidth

We give an algorithm that, given an n-vertex graph G and an integer k, in time 2O(k) n either outputs a tree decomposition of G of width at most 2k + 1 or determines that the treewidth of G is larger than k. This is the first 2-approximation algorithm for treewidth that is faster than the known exact algorithms, and in particular improves upon the previous best approximation ratio of 5 in time 2O(k) n given by Bodlaender et al. [SIAM J. Comput., 45 (2016)]. Our algorithm works by applying incremental improvement operations to a tree decomposition, using an approach inspired by a proof of Bellenbaum and Diestel [Comb. Probab. Comput., 11 (2002)].