Optimized 2-Approximation of Treewidth

Abstract

This paper presents a linear FPT algorithm to find a tree decomposition with a 2-approximation of the treewidth with a significantly smaller exponential dependence on the treewidth. The algorithm runs in time $O(\text{poly}(k)81^{k}n)$, compared to Korhonen's running time of $O(\text{poly}(k)1782^{k}n)$ = $O(2^{10.8k}n)$.

16 pages