The paper A Single-Exponential Time 2-Approximation Algorithm for Treewidth by Tuukka Korhonen of the Constraint Reasoning and Optimization group has been accepted for publication in the proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), a top conference in theoretical computer science.
A preprint of the paper is available at https://arxiv.org/abs/2104.07463.
Abstract:
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. In particular, our algorithm improves upon both the previous best approximation ratio of 5 in time 2O(k)n and the previous best approximation ratio of 3 in time 2O(k)nO(1), both given by Bodlaender et al. [FOCS 2013, SICOMP 2016]. Our algorithm is based on a local improvement method adapted from a proof of Bellenbaum and Diestel [Comb. Probab. Comput. 2002].