# A Single-Exponential Time 2-Approximation Algorithm for Treewidth

arXiv: https://arxiv.org/abs/2104.07463 · HTML: https://mlsanity.com/paper/2104.07463/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2021.

## Built on by (most cited first, 8 of 8)

- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton](https://mlsanity.com/paper/2310.04218/) (2023)
- [The Computational Complexity of Concise Hypersphere Classification](https://mlsanity.com/paper/2312.07103/) (2023)
- [Ontology-Mediated Querying on Databases of Bounded Cliquewidth](https://mlsanity.com/paper/2205.02190/) (2022)
- [From Width-Based Model Checking to Width-Based Automated Theorem Proving](https://mlsanity.com/paper/2205.10995/) (2022)
- [Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks](https://mlsanity.com/paper/2305.19659/) (2023)
- [Description Logics with Abstraction and Refinement](https://mlsanity.com/paper/2306.03717/) (2023)
- [Fixed-Parameter Tractability of Private Synthetic Data Generation](https://mlsanity.com/paper/2606.11283/) (2026)

## Abstract (arXiv)

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