论文标题
改进的树宽参数化算法
An Improved Parameterized Algorithm for Treewidth
论文作者
论文摘要
我们提供了一种算法，该算法将输入作为$ n $ vertex graph $ g $和一个整数$ k $，在时间上运行$ 2^{o（k^2）} n^{o（1）} $，并输出最多$ k $的$ g $ width $ g $的树木分解。这解决了长期以来的开放问题，即是否有$ 2^{o（k^3）} n^{o（1）} $ time算法。特别是，由于$ 2^{o（k^3）} n^{o（1）} $ time算法，我们的算法是对$ k $ in Treewidth的依赖性的首次改进。 我们还提供了一种算法，该算法给出了$ n $ vertex图$ g $，一个整数$ k $和一个理性$ \ varepsilon \ in（0,1）$，时间$ k^{o（k/\ varepsilon）} n^{o（k/\ varepsilon）} n^{o（o（1）} $ a $ g $ g $ g $ g $ $ $ $ $ $ $ $ $ $（确定$ g $的树宽大于$ k $。在我们的工作之前，众所周知，除了确切的算法之外，近似值均低于$ 2 $的树宽算法均未近似。我们的两种算法在多项式空间中起作用。
We give an algorithm that takes as input an $n$-vertex graph $G$ and an integer $k$, runs in time $2^{O(k^2)} n^{O(1)}$, and outputs a tree decomposition of $G$ of width at most $k$, if such a decomposition exists. This resolves the long-standing open problem of whether there is a $2^{o(k^3)} n^{O(1)}$ time algorithm for treewidth. In particular, our algorithm is the first improvement on the dependency on $k$ in algorithms for treewidth since the $2^{O(k^3)} n^{O(1)}$ time algorithm given by Bodlaender and Kloks [ICALP 1991] and Lagergren and Arnborg [ICALP 1991]. We also give an algorithm that given an $n$-vertex graph $G$, an integer $k$, and a rational $\varepsilon \in (0,1)$, in time $k^{O(k/\varepsilon)} n^{O(1)}$ either outputs a tree decomposition of $G$ of width at most $(1+\varepsilon)k$ or determines that the treewidth of $G$ is larger than $k$. Prior to our work, no approximation algorithms for treewidth with approximation ratio less than $2$, other than the exact algorithms, were known. Both of our algorithms work in polynomial space.
