  The independence number of a tree decomposition is the maximum of the
independence numbers of the subgraphs induced by its bags. The
tree-independence number of a graph is the minimum independence number of a
tree decomposition of it. Several NP-hard graph problems, like maximum weight
independent set, can be solved in time n^{O(k)} if the input n-vertex graph is
given together with a tree decomposition of independence number k. Yolov, in
[SODA 2018], gave an algorithm that, given an n-vertex graph G and an integer
k, in time n^{O(k^3)} either constructs a tree decomposition of G whose
independence number is O(k^3) or correctly reports that the tree-independence
number of G is larger than k.
  In this paper, we first give an algorithm for computing the tree-independence
number with a better approximation ratio and running time and then prove that
our algorithm is, in some sense, the best one can hope for. More precisely, our
algorithm runs in time 2^{O(k^2)} n^{O(k)} and either outputs a tree
decomposition of G with independence number at most $8k$, or determines that
the tree-independence number of G is larger than k. This implies 2^{O(k^2)}
n^{O(k)}-time algorithms for various problems, like maximum weight independent
set, parameterized by the tree-independence number k without needing the
decomposition as an input. Assuming Gap-ETH, an n^{\Omega(k)} factor in the
running time is unavoidable for any approximation algorithm for the
tree-independence number.
  Our second result is that the exact computation of the tree-independence
number is para-NP-hard: We show that for every constant k \ge 4 it is NP-hard
to decide if a given graph has the tree-independence number at most k.
