Computing Tree Decompositions with Small Independence Number

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^ (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 4\) it is NP -complete to decide if a given graph has the tree-independence number at most \ (k\).