An Improved Parameterized Algorithm for Treewidth

11/14/2022
by   Tuukka Korhonen, et al.
0

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

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset