论文标题
精确树宽的启发式计算
Heuristic computation of exact treewidth
论文作者
论文摘要
我们有兴趣计算给定图形$ g $的树宽$ \ tw（g）$。我们的方法是设计启发式算法，以计算一系列改善上限和一系列改进下限的顺序，希望从双方收敛到$ \ tw（g）$。上限算法扩展并简化了塔玛基（Tamaki）未发表的作品，以启发性地使用动态编程算法来决定由于Bouchitté和Todinca而决定的树宽。下边界算法是基于以下事实：对于每一个$ g $的$ h $ h $，我们都有$ \ tw（h）\ leq \ tw（g）$。从贪婪计算的次要$ h_0 $ $ g $开始，该算法试图构建一系列未成年人$ h_0 $，$ h_1 $，\ ldots $ h_k $，带有$ \ tw（h_i）<\ tw（h_i）<\ tw（h_ {i + 1}）$ for $ 0 \ leq iq i <k $和tw（tw） 我们已经基于这种方法实现了一个树宽求解器，并根据PACE 2017算法实现挑战的确切树宽轨迹的奖励实例进行了评估。结果表明，我们的方法非常有效地解决对于传统求解器而言难以解决的实例。我们的求解器比常规的求解器具有附加优势，因为它将紧凑的证书附加到其计算的下限。
We are interested in computing the treewidth $\tw(G)$ of a given graph $G$. Our approach is to design heuristic algorithms for computing a sequence of improving upper bounds and a sequence of improving lower bounds, which would hopefully converge to $\tw(G)$ from both sides. The upper bound algorithm extends and simplifies Tamaki's unpublished work on a heuristic use of the dynamic programming algorithm for deciding treewidth due to Bouchitté and Todinca. The lower bound algorithm is based on the well-known fact that, for every minor $H$ of $G$, we have $\tw(H) \leq \tw(G)$. Starting from a greedily computed minor $H_0$ of $G$, the algorithm tries to construct a sequence of minors $H_0$, $H_1$, \ldots $H_k$ with $\tw(H_i) < \tw(H_{i + 1})$ for $0 \leq i < k$ and hopefully $\tw(H_k) = \tw(G)$. We have implemented a treewidth solver based on this approach and have evaluated it on the bonus instances from the exact treewidth track of PACE 2017 algorithm implementation challenge. The results show that our approach is extremely effective in tackling instances that are hard for conventional solvers. Our solver has an additional advantage over conventional ones in that it attaches a compact certificate to the lower bound it computes.
