An O(c^k n) 5-Approximation Algorithm for Treewidth
An O(c^k n) 5-Approximation Algorithm for Treewidth
We give an algorithm that for an input n-vertex graph G and integer k > 0, in time O(c <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sup> n) either outputs that the tree width of G is larger than k, or gives a tree decomposition of G of width at most 5k + 4. This …