Positive-instance driven dynamic programming for treewidth
Positive-instance driven dynamic programming for treewidth
复制标题
DOI：
10.1007/s10878-018-0353-z
复制
发表时间：
2019-05-01
影响因子：
1
通讯作者：
Tamaki, Hisao
中科院分区：
文献类型：
--
作者：
Tamaki, Hisao
考虑一个决策问题的动态规划方案，其中涉及的所有子问题也是决策问题。这种方案的实现是正实例驱动(PID)，如果它生成正子问题实例，而不是负的子问题实例，每个都建立在较小的正实例上。我们采用Bouitte和Todinca提出的基于最小分离子和潜在最大团的动态规划方法来计算树宽，并设计了一个变种(用于问题的决策版本)，并给出了自然的PID实现。由此产生的算法执行得非常好：它解决了许多以前未知的最优解的标准基准实例。它结合了用于检测安全分隔符的新启发式算法，还解决了Pace 2017年准确树宽赛道带来的所有100个公共实例，这是算法实现方面的竞争。我们描述了该算法，证明了它的正确性，并给出了一个关于正子问题实例数的运行时间界。我们进行了实验分析，支持了这样一个界限的实际重要性。
Consider a dynamic programming scheme for a decision problem in which all subproblems involved are also decision problems. An implementation of such a scheme is positive-instance driven (PID), if it generates positive subproblem instances, but not negative ones, building each on smaller positive instances. We take the dynamic programming scheme due to Bouchitte and Todinca for treewidth computation, which is based on minimal separators and potential maximal cliques, and design a variant (for the decision version of the problem) with a natural PID implementation. The resulting algorithm performs extremely well: it solves a number of standard benchmark instances for which the optimal solutions have not previously been known. Incorporating a new heuristic algorithm for detecting safe separators, it also solves all of the 100 public instances posed by the exact treewidth track in PACE 2017, a competition on algorithm implementation. We describe the algorithm, prove its correctness, and give a running time bound in terms of the number of positive subproblem instances. We perform an experimental analysis which supports the practical importance of such a bound.