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 \(nO(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³)}\) either constructs a tree decomposition of \(G\) whose independence number is \(O(k³)\) 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²)}nO(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²)}nO(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\) .