论文标题
计算树的分解，独立数少
Computing Tree Decompositions with Small Independence Number
论文作者
论文摘要
树木分解的独立数是其袋子引起的子图的独立数的最大数量。图形的树独立数是其树分解的最小独立性数。如果输入n-vertex图与独立数字k的树分解一起给出，则可以在时间n^{o（k）}时在时间n^{o（k）}时求解几个NP-硬形图问题。在[Soda 2018]中，Yolov给出了一种算法，在n-vertex graph g和一个整数k中，随着时间的推移，n^{o（k^3）}构建了g的树的树分解，其独立数为o（k^3），或者正确地报告了g的树木独立数大于k。 在本文中，我们首先给出了一种算法，用于以更好的近似比和运行时间计算树独立的数字，然后证明我们的算法在某种意义上是最好的。更确切地说，我们的算法在时间2^{o（k^2）} n^{o（k）}中运行，并且要么输出G的树的树分解，其独立数量最多为$ 8K $，或者确定G的树独立数量G大于k。这意味着2^{o（k^2）} n^{o（k）} - 各种问题的时间算法，例如最大重量独立集，由树独立数字k参数化，而无需分解作为输入。假设Gap-Eth，对于树独立数的任何近似算法，运行时间中的n^{ω（k）}因子是不可避免的。 我们的第二个结果是，树独立数的确切计算是para-np-hard：我们表明，对于每个常数的k \ ge 4，决定给定图是否最多具有k的k \ ge 4。
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^{Ω(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.
