  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 $\varepsilon \in (0,1)$, in time $k^{O(k/\varepsilon)} n^{O(1)}$
either outputs a tree decomposition of $G$ of width at most $(1+\varepsilon)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.
