Computing Tree Decompositions with Small Independence Number

arXiv2207.09993MaRDI QIDQ6405563FDOQ6405563

Clément Dallard, Martin Milanič, Tuukka Korhonen, Petr A. Golovach, Fedor V. Fomin

Publication date: 20 July 2022

Abstract: 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 graph is given with a tree decomposition of independence number at most $k$. However, it was an open problem if tree-independence number could be computed or approximated in $n^{f(k)}$ time, for some function $f$, and in particular it was not known if maximum weight independent set could be solved in polynomial time on graphs of bounded tree-independence number. In this paper, we resolve the main open problems about the computation of tree-independence number. First, we give an algorithm that given an $n$-vertex graph $G$ and an integer $k$, in time $2^{O(k^2)}{n}^{O(k)}$ 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 tree-independence number $k$ without needing the decomposition as an input. Then, we show that the exact computing of tree-independence number is para-NP-hard, in particular, that for every constant $kge4$ it is NP-hard to decide if a given graph has tree-independence number at most $k$.

This page was built for publication: Computing Tree Decompositions with Small Independence Number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405563)