A $c^k n$ 5-Approximation Algorithm for Treewidth
A $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 $2^{O(k)} n$, either outputs that the treewidth of $G$ is larger than $k$, or gives a tree decomposition of $G$ of width at most $5k+4$. This is the first algorithm providing a constant factor …