Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Computing tree decompositions with small independence number [Elektronski vir]
    Dallard, Clément Jean ...
    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 nO(k3) either constructs a tree decomposition of G whose independence number is O(k3) 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 2O(k2)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 2O(k2)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-hard to decide if a given graph has the tree-independence number at most k.
    Vir: 51st International Colloquium on Automata, Languages, and Programming [Elektronski vir] : ICALP 2024, July 8-12, 2024, Tallinn, Estonia (Str. 51:1–51:18)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2024
    Jezik - angleški
    COBISS.SI-ID - 206071811

    Povezava(-e):

    https://doi.org/10.4230/LIPIcs.ICALP.2024.51
    https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.51
    DOI

Vnos na polico