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].