论文标题
Reed的树宽近似的改进
An Improvement of Reed's Treewidth Approximation
论文作者
论文摘要
我们提出了一种针对树宽问题的新近似算法，该算法在树宽上找到了上限，并构建了相应的树分解。我们的算法是Reed经典算法的更快变化。为了读者的好处，并能够比较这两种算法，我们从对Reed算法的详细时间分析开始。我们填写了Reed论文中省略的许多细节。由TreeWidth $ k $参数化的计算树分解是固定的参数可处理（fpt），这意味着在时间$ \ Mathcal {o}（f（k）g（k）g（n））$ f $中有算法运行，$ f $是可计算的函数，而$ g（n）$在$ n $中是$ n $ n $ n $ ns $ ns n n n n n n n n n n n nes nes ness ness nes nes ness ness ness ness nuctice。 Reed算法的分析显示$ f（k）= 2^{\ Mathcal {o}（k \ log k）} $和$ g（n）= n \ log n $用于5个应用。 Reed简单地要求时间$ \ MATHCAL {O}（n \ log n）$ for bounded $ k $用于其常数因子近似算法，但是$ 2^{ω（k \ log k）} n \ log n $的界限是众所周知的。从实际的角度来看，我们注意到里德的算法的时间还包含$ \ nathcal {o}（k^2 2^{24k} n \ log n）$的术语，对于小$ k $而言，它比无非领先的$ 2^{\ nathcal {\ nathcal {o log log n $差得多。我们更精确地分析了$ f（k）$，因为本文的目的是改善所有合理的$ k $值的运行时间。 我们的算法在$ \ Mathcal {o}（f（k）n \ log {n}）$中运行，但对$ k $的依赖性要小得多。在我们的情况下，$ f（k）= 2^{\ mathcal {o}（k）} $。该算法简单快捷，尤其是对于$ k $的少量值。我们应该提到Bodlaender等人。 [2016]具有对$ n $的线性依赖性的算法，而Korhonen [2021]获得了更好的近似值，而当前论文则可以更好地依赖$ K $。
We present a new approximation algorithm for the treewidth problem which finds an upper bound on the treewidth and constructs a corresponding tree decomposition as well. Our algorithm is a faster variation of Reed's classical algorithm. For the benefit of the reader, and to be able to compare these two algorithms, we start with a detailed time analysis of Reed's algorithm. We fill in many details that have been omitted in Reed's paper. Computing tree decompositions parameterized by the treewidth $k$ is fixed parameter tractable (FPT), meaning that there are algorithms running in time $\mathcal{O}(f(k) g(n))$ where $f$ is a computable function, and $g(n)$ is polynomial in $n$, where $n$ is the number of vertices. An analysis of Reed's algorithm shows $f(k) = 2^{\mathcal{O}(k \log k)}$ and $g(n) = n \log n$ for a 5-approximation. Reed simply claims time $\mathcal{O}(n \log n)$ for bounded $k$ for his constant factor approximation algorithm, but the bound of $2^{Ω(k \log k)} n \log n$ is well known. From a practical point of view, we notice that the time of Reed's algorithm also contains a term of $\mathcal{O}(k^2 2^{24k} n \log n)$, which for small $k$ is much worse than the asymptotically leading term of $2^{\mathcal{O}(k \log k)} n \log n$. We analyze $f(k)$ more precisely, because the purpose of this paper is to improve the running times for all reasonably small values of $k$. Our algorithm runs in $\mathcal{O}(f(k)n\log{n})$ too, but with a much smaller dependence on $k$. In our case, $f(k) = 2^{\mathcal{O}(k)}$. This algorithm is simple and fast, especially for small values of $k$. We should mention that Bodlaender et al. [2016] have an algorithm with a linear dependence on $n$, and Korhonen [2021] obtains the much better approximation ratio of 2, while the current paper achieves a better dependence on $k$.
