@article{Belbasi_Fürer_2022, title={An Improvement of Reed’s Treewidth Approximation}, volume={26}, url={https://jgaa.info/index.php/jgaa/article/view/paper593}, DOI={10.7155/jgaa.00593}, abstractNote={We present a new approximation algorithm for the treewidth problem which finds an upper bound on the treewidth and constructs a corresponding tree decomposition as well. Our algorithm is a faster variation of Reed's classical algorithm. For the benefit of the reader, and to be able to compare these two algorithms, we start with a detailed time analysis of Reed's algorithm. We fill in many details that have been omitted in Reed's paper. Computing tree decompositions parameterized by the treewidth $k$ is fixed parameter tractable (FPT), meaning that there are algorithms running in time $\mathcal{O}(f(k) g(n))$ where $f$ is a computable function, and $g(n)$ is polynomial in $n$, where $n$ is the number of vertices. An analysis of Reed's algorithm shows $f(k) = 2^{\mathcal{O}(k \log k)}$ and $g(n) = n \log n$ for a 5-approximation. Reed simply claims time $\mathcal{O}(n \log n)$ for bounded $k$ for his constant factor approximation algorithm, but the bound of $2^{\Omega(k \log k)} n \log n$ is well known. From a practical point of view, we notice that the time of Reed's algorithm also contains a term of $\mathcal{O}(k^2 2^{24k} n \log n)$, which for small $k$ is much worse than the asymptotically leading term of $2^{\mathcal{O}(k \log k)} n \log n$. We analyze $f(k)$ more precisely, because the purpose of this paper is to improve the running times for all reasonably small values of $k$. Our algorithm runs in $\mathcal{O}(f(k)n\log{n})$ too, but with a much smaller dependence on $k$. In our case, $f(k) = 2^{\mathcal{O}(k)}$. This algorithm is simple and fast, especially for small values of $k$. We should mention that <a href="https://doi.org/10.1137/130947374">Bodlaender et al. [2016]</a> have an algorithm with a linear dependence on $n$, and <a href="https://doi.org/10.1109/FOCS52979.2021.00026">Korhonen [2021]</a> obtains the much better approximation ratio of 2, while the current paper achieves a better dependence on $k$.}, number={2}, journal={Journal of Graph Algorithms and Applications}, author={Belbasi, Mahdi and Fürer, Martin}, year={2022}, month={Jun.}, pages={257–282} }