Current browse context:
cs.DS
Change to browse by:
References & Citations
Computer Science > Data Structures and Algorithms
Title: Computing Tree Decompositions with Small Independence Number
(Submitted on 20 Jul 2022 (v1), last revised 25 Apr 2024 (this version, v3))
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 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.
Submission history
From: Petr Golovach [view email][v1] Wed, 20 Jul 2022 15:53:53 GMT (33kb,D)
[v2] Mon, 22 Apr 2024 20:50:10 GMT (43kb,D)
[v3] Thu, 25 Apr 2024 15:14:12 GMT (40kb,D)
Link back to: arXiv, form interface, contact.