2026-07-23T07:57:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20194 2024-07-02T07:52:50Z ddc:004 open_access

Computing Tree Decompositions with Small Independence Number Dallard, Clément Fomin, Fedor V. Golovach, Petr A. Korhonen, Tuukka Milanič, Martin tree-independence number approximation parameterized algorithms 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^𝒪(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^𝒪(k³) either constructs a tree decomposition of G whose independence number is 𝒪(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^𝒪(k²) n^𝒪(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^𝒪(k²) n^𝒪(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-hard to decide if a given graph has the tree-independence number at most k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Clément Dallard and Fedor V. Fomin and Petr A. Golovach and Tuukka Korhonen and Martin Milanič 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.51 urn:nbn:de:0030-drops-201945 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.51 eng https://creativecommons.org/licenses/by/4.0/legalcode