An Improved Parameterized Algorithm for Treewidth

We give an algorithm that takes as input an n-vertex graph G and an integer k, runs in time 2 O(k 2 ) n O(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 2 o(k 3 ) n O(1) time algorithm for treewidth. In particular, our algorithm is the first improvement on the dependency on k in algorithms for treewidth since the 2 O(k 3 ) n O(1) time algorithm given by Bodlaender and Kloks [ICALP 1991] andLagergren and Arnborg [ICALP 1991].

We also give an algorithm that given an n-vertex graph G, an integer k, and a rational ε ∈ (0, 1), in time k O(k/ε) n O(1) either outputs a tree decomposition of G of width at most (1 + ε)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.

The research leading to these results has received funding from the Research Council of Norway via the project BWCA (grant no. 314528).