# An Improved Parameterized Algorithm for Treewidth

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2022.

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

- [Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology](https://mlsanity.com/paper/2312.09646/) (2023)
- [Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size](https://mlsanity.com/paper/2505.22384/) (2025)
- [Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks](https://mlsanity.com/paper/2305.19659/) (2023)
- [Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures](https://mlsanity.com/paper/2412.08556/) (2024)
- [Compact Geometric Representations of Hierarchies](https://mlsanity.com/paper/2606.18520/) (2026)
- [Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography](https://mlsanity.com/paper/2609.04165/) (2026)

## Abstract (arXiv)

We give an algorithm that takes as input an n-vertex graph G and an integer k, runs in time 2O(k2) nO(1), and outputs a tree decomposition of G of width at most k, if such a decomposition exists. This resolves the long-standing open problem of whether there is a 2o(k3) nO(1) time algorithm for treewidth. In particular, our algorithm is the first improvement on the dependency on k in algorithms for treewidth since the 2O(k3) nO(1) time algorithm given by Bodlaender and Kloks [ICALP 1991] and Lagergren and Arnborg [ICALP 1991]. We also give an algorithm that given an n-vertex graph G, an integer k, and a rational varepsilon ∈ (0,1), in time kO(k/varepsilon) nO(1) either outputs a tree decomposition of G of width at most (1+varepsilon)k or determines that the treewidth of G is larger than k. Prior to our work, no approximation algorithms for treewidth with approximation ratio less than 2, other than the exact algorithms, were known. Both of our algorithms work in polynomial space.